首页 理论教育 编译原理与实践中的LR分析:确定、规范的自下而上技术

编译原理与实践中的LR分析:确定、规范的自下而上技术

时间:2023-11-17 理论教育 版权反馈
【摘要】:LR分析是一种确定的、符合规范归约的自下而上语法分析技术。LR分析可应用于一大类上下文无关文法的语法分析,并且识别效率良好。图5-3LR分析器模型1.LR分析表LR分析表是LR分析器的核心部分。例5.3 利用分析表5-2对输入串i+i*i进行LR分析。表5-3输入串i+i*i的LR分析过程有时,LR分析器需要向前查看k个输入符号才能决定移进还是归约,这样的分析器称为LR分析器。

编译原理与实践中的LR分析:确定、规范的自下而上技术

LR分析是一种确定的、符合规范归约的自下而上语法分析技术。其中,L表示从左到右扫描输入串,R表示构造一个最右推导的逆过程。LR分析可应用于一大类上下文无关文法的语法分析,并且识别效率良好。然而,LR分析的一个主要缺点是手工构造分析程序的工作量巨大,通常需要借助于5.5节介绍的YACC等工具来自动生成LR分析器。

规范归约的关键在于寻找句柄。LR分析法的思想是将句型的识别过程划分为一系列状态,若干个状态可以识别句型左端的一部分符号,这部分符号正是分析栈中呈现特定句型的句柄时的情形。

LR分析器结构

LR分析器由分析程序、分析表和分析栈组成,如图5-3所示。分析栈包括文法符号栈和状态栈两部分。LR分析程序是用于控制分析器动作的总控程序,其任何一步动作都是根据分析栈的栈顶状态,以及输入符号串,通过查找分析表,唯一确定分析动作是移进下一个输入符号,或是栈顶已经呈现出某个句型的句柄,需要进行归约。

图5-3 LR分析器模型

1.LR分析表

LR分析表是LR分析器的核心部分。如果能为文法G构造一个LR分析表,则称G为LR文法。虽然并非所有上下文无关文法都是LR文法,但是大多数程序语言都可以使用LR文法进行描述。5.4节将详细介绍四种LR分析表的构造方法。

LR分析表是一张二维表,由ACTION表(动作表)和GOTO表(状态转换表)两部分构成。例如,下述表达式文法的LR分析表如表5-2所示。文法为每一条产生式进行编号,对应于分析表中具有下标的r。识别过程中的各个状态由状态的编号表示,其中0号状态是分析的初始状态。

表5-2 LR分析表

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→(E)

(6)F→i

分析表中,ACTION[S,a]表示状态S面对输入符号a时应采取的动作。ACTION[S,a]规定的动作包括下述四种之一。

①移进:Si表示将状态i移入状态栈,输入符号a移入文法符号栈,下一输入符号成为当前输入符号。

②归约:rj表示按产生式(j)A→β进行归约。并将A移入符号栈,GOTO[Si,A]中的状态移入状态栈。分析表中的GOTO[S,X]表示状态S面对文法符号X(终结符或非终结符)时识别应进入的下一状态。为了减少分析表的占用空间,将X为终结符号的GOTO表与ACTION表进行了合并。

③接受:acc表示分析成功,分析器停止工作。

④报错:空白表示发现源程序含有错误,调用出错处理程序。(www.xing528.com)

2.分析栈和分析过程

分析栈包括文法符号栈和相应的状态栈两部分。栈里的每个状态概括了从分析开始直到某一识别阶段的全部分析情形,分析时只需根据栈顶状态和现行输入符号就可以唯一确定下一个动作,确定句柄是否出现在栈顶。

LR分析过程可以看作是由状态栈、符号栈和输入符号串所构成的三元式的变化过程。与图5-3对应,S0和#是分析初始化时移入栈里的开始状态和句子左端标识。初始时,三元式为

经过多步分析动作之后,当前栈顶状态为Sm,符号串X1X2…Xm是已移进-归约出的文法符号串。分析过程中的每步结果可以表示为

分析器任何一步动作都是由栈顶状态Sm和输入符号ai所唯一决定的,也就是执行ACTION[Sm,ai]所规定的动作。任何动作都将引起三元式的变化,达到特定的分析状态,分析器将通过一步一步地变换三元式,直到执行到“接受”或“报错”动作为止。分析器的移进和归约动作的执行方式如下。

(1)移进

将ACTION[Sm,ai]中的状态Snext移入状态栈,将输入符号ai移入符号栈,下一输入符号ai+1成为当前输入符号。此时三元式变为

LR()控制器设计

(S0S1…SmSnext,#X1 X2…Xmai,ai+1…an#)

(2)归约

依据产生式A→β进行归约,如果产生式的右端长度为r,则状态栈和符号栈栈顶的r个元素同时出栈。将GOTO[Sm-r,A]中的状态Snext移入状态栈,将归约后的符号A移入符号栈。此时三元式变为

(S0S1…Sm-rSnext,#X1X2…Xm-rA,aiai+1…an#)

注意,归约动作不改变当前输入符号,执行归约意味着β(即Xm-r+1…Xm)是当前句型中相对于A的句柄,而且呈现于栈顶。

例5.3 利用分析表5-2对输入串i+i*i进行LR分析。

输入串i+i*i的分析过程如表5-3所示。状态栈中的数字表示状态的编号。由分析过程可以发现,文法符号栈实际上是多余的,因为相关信息已经概括到状态栈里了,保留在这里可以更加明确归约过程。

表5-3 输入串i+i*i的LR分析过程

有时,LR分析器需要向前查看k个输入符号才能决定移进还是归约,这样的分析器称为LR(k)分析器。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈