《语法分析-自底向上分析.ppt》由会员分享，可在线阅读，更多相关《语法分析-自底向上分析.ppt（47页珍藏版）》请在三一办公上搜索。
1、第5章 语法分析自底向上分析,在自底向上的分析方法中，分析过程从输入符号串开始，通过反复查找当前句型的句柄，并使用规则，将找到的句柄归约成相应的非终结符号，直到归约到开始符号。,5.1 规范推导、规范句型和规范归约 规范推导就是最右推导，而通过规范推导能得到的句型就是规范句型。规范归约也称为最左归约，是规范推导的逆过程，即在分析的每一步，将当前句型的句柄归约成相应的非终结符号。,5.1 规范推导、规范句型和规范归约,从符号串开始，向上归约，如果最终能够规约到文法的开始符号S，则同样可以说明该输入符号串是这个文法的句子。其归约过程如图5.1所示。,例 5.1有文法GS：S:=aAcBe A:=b
2、 A:=Ab B:=d分析符号串abbcde是否为该文法的句子。,解：首先，我们从文法的开始符号进行规范推导，依次使用1、4、3、2规则，就可得到符号串abbcde。规范推导过程如下：S=aAcBe=aAcde=aAbcde=abbcde,5.2自底向上分析方法的一般过程,自底向上分析方法，也称为移进归约法，其过程是：设置一个寄存符号的先进后出栈，称为符号栈。在分析进行时，把输入符号逐个按扫描顺序移进栈里，当栈顶符号串形成句柄(即为某条规则的右部)时，就归约，把栈顶构成句柄的那个符号串用相应规则左部的非终结符号来代替。再检查栈顶是否又出现了新的句柄，若有，继续归约；若没有形成新的句柄，则再从输
3、入符号串移进新的符号，如此继续直到整个输入符号串处理完毕。最终如果栈里只有识别符号，则所分析的输入符号串为合法的句子，报告成功；否则，输入串是不合法的符号串，报告错误。,表5.1输入串abbcde的分析过程,上述分析可看出，每次归约的句柄都出现在符号栈的栈顶，不会出现在栈的中间，因为算法是自左向右扫描输入符号串，进行的是最左归约。,例 5.1有文法GS：S:=aAcBe A:=b A:=Ab B:=d分析符号串abbcde是否为该文法的句子。,5.2自底向上分析方法的一般过程,存在着句柄识别问题:例如表5.1中的第5步，栈内符号串为aAb，由于文法中同时有规则A:=Ab和A:=b，那么，符号串
4、Ab和b都是某规则的右部，都可以作为句柄归约。如果选择b作为句柄归约成A，那么，最终就达不到归约到开始符号S的目的。事实上，不能因为规则A:=b就断定b是句柄，因为aAAcde并不是一个句型，即不存在推导过程S=*aAAcde。对句型aAbcde来说，其简单短语是Ab和d，其中Ab是最左简单短语，所以是句柄。,从自底向上分析的一般过程可看出，如何寻找或确定一个句型的句柄，是构造一个自左向右扫描、自底向上分析方法必须要解决的一个关键问题。最常用的自底向上的分析方法有算符优先方法和LR分析方法，算符优先方法仅适用于算符文法，而LR分析方法应用比较普遍。,5.3 LR分析方法,在自底向上的分析中，当
5、一串貌似句柄的符号串出现在栈顶时，用什么方法来判定它是否为一个真正的句柄呢？这里我们介绍LR(K)分析技术。LR(K)分析方法的L表示从左到右扫描所给定的输入串，R表示以相反的方向构造该输入串的最右推导(即规范推导)。K表示为了做出分析决定需要向前看的输入符号的个数。LR分析方法对文法适应性强，分析能力强，对源程序中错误的诊断灵敏，但结构比前面介绍的自顶向下的分析方法复杂，向前查看的符号愈多，相应的分析方法愈复杂。LR(0)分析器是LR分析方法中最简单的一种，在确定分析动作时，不需要向前查看任何符号。这种分析器分析能力较弱，实用性差，但它是构造其它更复杂的LR分析器的基础。,5.3.1 LR分
6、析器逻辑结构,LR分析器有一个给定的输入符号串，一个分析栈和一个有穷的控制系统。如图5.2所示。,输入符号串,分析栈：,有穷的控制系统：分析表(动作、转换)总控程序,其中，输入符号串就是等待分析的符号串。分析栈有两部分：一个是符号栈，另一个是状态栈，它们都是先进后出栈。而控制系统包括一个分析表和一个总控程序。对于不同的文法来说，分析表各有不同，但总控程序都是一样的。LR分析器的工作过程就是在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的符号和状态以及当前的输入符号，查阅分析表并按分析表的指示完成相应的分析动作，直到符号栈中出现开始符号。,图5.2 LR分析器的模型,5.3.2 LR分
7、析表的构成,LR分析表是LR分析器的核心部分，它由两部分组成，一是动作部分ACTION表，二是状态转换部分GOTO表。表中S1、S2、Sn为分析器的各个状态；a1、a2、am为文法的全部终结符号及右界符#；X1、X2、Xk为文法的非终结符号。,表5.2 LR分析表,分析表的动作部分，Si所在行与aj所在列对应单元ACTIONSi，aj表示当分析状态栈的栈顶为Si，输入符号为aj时应执行的动作；而在分析表的状态转换部分，Si行Xj列对应的单元GOTOSi，Xj表示当前状态Si下符号栈顶为非终结符号Xj后应移入状态栈的状态。,5.3.2 LR分析表的构成,分析表的动作有下列四种：移进(Sn)：将输
8、入符号aj移进符号栈，将状态n移进状态栈，输入指针指向下一个输入符号。归约(R)：当栈顶形成句柄时，按照相应的产生式UW进行归约。若产生式右部W的长度为n，则将符号栈栈顶n个符号和状态栈栈顶n个状态出栈，然后将归约后的文法符号U移入符号栈，并根据此时状态栈顶的状态Si及符号栈顶的符号U，查GOTO标，将GOTOSi，U移入状态栈。接受(A)：当输入符号串到达右界符#时，且符号栈只有文法的开始符号时，则分析成功结束，接受输入符号串并结束分析。报错(E)：在状态栈的栈顶状态为Si时，如果输入符号为不应该遇到的符号时，即ACTIONSi，aj=空白，则报错，说明输入符号串有语法错误。,5.3.2 L
9、R分析表的构成,LR分析器的关键是构造分析表。表5.2给出了文法G：0)SA，1)A(A)，2)Aa的分析表。,表5.3 LR分析表,5.3.3 LR分析过程,图5.3 LR的分析流程,分析开始时，栈内的初始状态为0，符号栈为#。当状态栈顶为某个状态p时，当前输入指针指向的符号是a时，查分析动作表的p行、a列。如果得到的动作指示ACTIONp,a是移进Si，则将a压入符号栈，将状态i压入状态栈，然后将输入指针指向输入符号串的下一个符号；如果得到的动作指示是归约Ri，且归约产生式为B，则从符号栈内弹出|个符号，从状态栈内弹出|个状态，,假设此时出栈后的状态栈栈顶为p，查状态转换表的p行、B列，得
10、到下一个状态GOTOp,B=q，并将该后继状态q压入状态栈；如果得到的动作指示是接受，则接受输入的符号串，分析成功结束；,5.3.3 LR分析过程,例5.2，利用表5.3分析表分析符号串(a)。,5.4 LR(0)分析方法,LR(0)分析器是LR分析方法中最简单的一种，在确定分析动作时，不需要向前查看任何符号,它是构造其它更复杂的LR分析器的基础。为了进行LR(0)分析，首先需要对文法进行拓广，目的是使文法只有一个以识别符号作为左部的产生式，从而使构造出来的分析器有唯一的接受状态。拓广后的文法称为拓广文法。,例5.3,对文法G ET|E+T|ET Ti|(E)进行拓广。解：引入一个新的开始符号
11、S，使得文法的开始符号所在的规则唯一，这样得到拓广文法如下：SEET|E+T|ETTi|(E),活前缀和可归前缀,前缀:从任意符号串x的末尾删除0或多个符号后得到的符号串.如u、uni、universi ty都是university的前缀。活前缀:前缀的子集，它是针对规范句型而言的，而可归前缀是一个特殊的活前缀。,活前缀：设t是一个规范句型，即 t是能用最右推导得到的句型，其中表示句柄，tVt*，如果=u1u2ur，那么称符号串u1u2ui(其中1ir)是句型 t的活前缀。从活前缀的定义可知，一个规范句型的活前缀可以有多个，但观察这些活前缀，会发现其中活前缀u1、u1u2、u1u2ur-1不含
12、有完整句柄，只有活前缀u1u2ur含有完整句柄，那么这个含有句柄的活前缀u1u2ur称为可归前缀。活前缀不含句柄右边的任意符号，而可归前缀是含有句柄的活前缀。对一个规范句型来说，活前缀可有多个，可归前缀只有一个。,活前缀和可归前缀,例5.4，有文法GET|E+T|E-T，Ti|(E)，找规范句型E+(i-i)的活前缀和可归前缀。解：首先画出E+(I-i)的语法树，可找出第一个i是句柄，那么=E+(i，t=-i)因此活前缀为：E，E+，E+(，E+(i，其中E+(i是可归前缀。,总结活前缀求法：先画出句型的语法树，找出句柄，然后，从句型的左边第一个符号开始，取长度分别为1、2、的符号串，直到包含
13、句柄在内的长度符号串就是该句型所有的活前缀。而可归前缀就是最长的活前缀。注意：所有活前缀都不包括句柄右边的任何符号(即t中的任何符号)。,LR分析过程中，如果输入符号串没有语法错误，则在分析的每一步，若将符号栈中的全部文法符号与剩余的输入符号串连接起来，得到的一定是所给文法的一个规范句型。也就是说，压入符号栈中的符号串一定是某一规范句型的前缀，而且这种前缀不会含有任何句柄右边的符号，所以都是活前缀。当符号栈形成句柄，即符号栈的内容为可归前缀时，就会立即被归约。所以说，LR分析就是逐步在符号栈中产生可归前缀，再进行归约的过程。,活前缀和可归前缀,5.4.2 LR(0)项目,虽然LR分析器可以识别
14、活前缀，但它的主要目的是要输出为给定的输入串构造逆向最右推导时使用的产生式序列。因此分析器的一个基本功能就是要检测句柄。为了检测句柄，分析器首先必须能够识别出当前句型中含有句柄的可归前缀。在介绍如何构造LR分析器之前，我们还要先了解项目及项目有效性的概念。,5.4.2 LR(0)项目,1、项目的定义对某个文法G来说，如果A12为G的一条规则，那么，对规则的右部加上一个圆点，就成为一个项目。其形式为：A12圆点是表示项目的一种标记，也就是说，如果一条规则的右部标有圆点，那么它就是项目。一般情况下，因为圆点的位置不同。一条规则可以有几个项目。,例如，有文法SE，ET|E+T|E-T，Ti|(E)，
15、对于规则SE右部有一个符号，因圆点位置不同，可有下面两个项目 S.E，SE.对于规则EET，右部有三个符号，可有下面四个项目 EET，EET，EET，EET,项目中点后面的符号称为该项目的后继符号。后继符号可能是终结符号，也可能是非终结符号，如果点在最后，后继符号则为空。,第5章 语法分析自底向上分析,根据项目中点的位置和后继符号，可把项目分成以下几种：移进项目：后继符号为终结符号，如EET。待约项目：后继符号为非终结符号，如EET和S.E归约项目：后继符号为空，即点在最后。如EET和SE.接受项目：文法的开始符号S的归约项目。接受项目是一个特殊的归约项目，它表示该产生式归约后分析将结束。上例
16、中的项目SE.就是接受项目。,2、项目有效性项目就是对规则的右部标记了圆点，而且，圆点位置不同代表不同的项目，那么项目有什么含义呢？这就是项目的有效性。一个项目A12对于某个活前缀 1是有效的，当且仅当存在某个最右推导。S=|*=At=|=12t，其中t是终结符号串。在LR分析过程中，活前缀就是符号栈的内容，是已经读入的符号，它不包含句柄右边的任何符号。活前缀和句柄的关系有三种：活前缀包含句柄、含有句柄的一部分或不含句柄的任何符号。,第5章 语法分析自底向上分析,第5章 语法分析自底向上分析,1)如果活前缀包含句柄，表示符号栈顶形成句柄，则就可以归约。假设归约产生式为A，由于活前缀包含完整的，
17、说明已经识别了的全部，所以说项目A.对活前缀有效。因此，当一个点在最后的项目对活前缀有效时，则可以进行归约，所以把点在最后的项目称为归约项目。2)如果活前缀只包含句柄的部分符号时，正期待着从余流的输入符号中看到句柄的其余符号。假设活前缀含有1，有产生式A12，由于活前缀中有产生式右部12的1部分，所以说A1.2对活前缀有效。同样，如果有另一个产生式B13，那么B1.3对活前缀也有效。3)如果活前缀不含句柄的任何符号，则需将余流的输入符号移进。假设下一步移进的符号可能是的前缀，那么，对于任一产生式A来说，由于活前缀中不含的任何符号，所以说A.对活前缀有效。一个项目指明了在分析过程的某一时刻，已经
18、看到的一个产生式右部的多少。一般来说，活前缀与有效项目是多对多关系。,第5章 语法分析自底向上分析,例5.5，有文法 SE，ET|E+T|E-T，Ti|(E)，列出该文法的所有项目，并找出对活前缀E有效的项目。解：首先列出每条规则对应的多个项目：SE，有项目S.E，SE.ET，有项目E.T，ET.EE+T，有项目E.E+T，EE.+T，EE+.T，EE+T.EE-T，有项目E.E-T，EE.-T，EE-.T，EE-T.Ti，有项目E.i，Ei.T(E)，有项目T.(E)T(.E)T(E.)T(E).,在上面的众多项目中，只有项目EET，Ti和T(E)对活前缀E是有效的，这是因为从S到含有活前缀
19、E的规范句型的规范推导中，能够使用这些项目：,第5章 语法分析自底向上分析,先看推导过程S=E=ET，最后一步推导使用的规则是EET，句柄为ET，该过程推导出的句型ET含有活前缀E，而E是句柄ET的一部分，所以说规则EET的项目EET对E是有效的。接下来看推导过程S=E=ET=Ei，最后一步推导使用的规则是Ti，句柄为i，该过程推导出的句型Ei也含有活前缀E，但由于活前缀E-不含句柄i的任何符号，所以说项目Ti对E也是有效的。同理，对于推导过程S=E=ET=E(E)，可证明项目T(E)对E也是有效的。因此，EET，Ti和T(E)是活前缀E-的有效项目集。,从LR分析过程看，当符号栈内容为E-时
20、，有项目EET、Ti和T(E)对E-有效，则将来形成的句柄一定是EET，Ti和T(E)这几条规则之一的右部。究竟会形成哪条规则的右部取决于下一个读入的符号，如果下一个符号是i，则形成句柄i；如果下一个符号是(，则将等待形成句柄(E)。,5.4.3 构造识别活前缀的有穷自动机,在LR实际分析过程中，并不直接分析符号栈中的符号是否形成句柄。但我们可以把文法中的符号都看成是有穷自动机的输入符号，每当一个符号进栈时表示已经识别了该符号，并进行状态转换；当识别出可归前缀时，相当于在栈中形成句柄，则认为到达了识别句柄的状态。自动机中的每个状态都和无数个活前缀密切相关，每个状态中都包含该状态所能识别的活前缀
21、。因为文法有无穷的句型，所以一个可用文法具有无穷数目的活前缀，因此，根据活前缀集合直接构造对应的自动机状态是不可能的。因为每个活前缀对应的有效项目是有穷的，因此，可以将一个活前缀的可能的无穷集对应到一个有穷的有效项目集上。因此，如果我们能得到对应分析器每个状态的有效项目的有穷集合，那么，也就能得到识别活前缀的有穷自动机。,1、项目集的闭包运算设I为一项目集，I的闭包运算CLOSURE(I)定义如下：I中的每一个项目都属于CLOSURE(I)。如项目A1X2属于CLOSURE(I)，且X为非终结符号，则将形式为X.的项目添加到CLOSURE(I)中。重复(1)和(2)，直到CLOSURE(I)封
22、闭为止。,5.4.3 构造识别活前缀的有穷自动机,5.4.3 构造识别活前缀的有穷自动机,例5.6，有文法：E:=E，E:=E+T，E:=T，T:=T*F，T:=F，F:=(E)，F:=i，设项目集I=E.E，求CLOSURE(I)。解：根据闭包运算的第1条，CLOSURE(I)=E.E 根据第2条，因为E是非终结符号，所以将规则E:=E+T和 E:=T在其右部最前面加点形成E.E+T和E.T，加进CLOSURE(I)中：CLOSURE(I)=E.E，E.E+T，E.T 根据第3条，重复计算，直到CLOSURE(I)封闭为止。因为T是非终结符号，所以将规则T:=T*F和T:=F在其右部最前面加
23、点形成T.T*F和T.F，加进CLOSURE(I)中：CLOSURE(I)=E.E，E.E+T，E.T，T.T*F，T.F 因为F是非终结符号，所以将F.(E)和F.i，加进CLOSURE(I)中：CLOSURE(I)=E.E，E.E+T，E.T，T.T*F，T.F，F.(E)，F.i 至此，CLOSURE(I)封闭。,5.4.3 构造识别活前缀的有穷自动机,2、项目集之间的转换函数GO假设有一项目为A.X，令X是一个字汇表中的符号，则对项目A.X进行读X操作，结果为项目AX.。设I是一个项目集,X是任一文法符号，则项目集之间的转换用GOI,X函数表示，定义为：GOI,X=CLOSURE(J)
24、其中J=任何具有A X.的项目|A.X I，即对项目集I中所有的项目进行读X操作的结果。CLOSURE(J)为对J进行了闭包运算得到的项目集，称为I的后继项目集。令状态I代表项目集I，状态J代表后继项目集CLOSURE(J)，用状态图表示则为：,例5.7，有文法：E:=E，E:=E+T，E:=T，T:=T*F，T:=F，F:=(E)，F:=i有项目集I=E E.,E E.+T,求GOI,+解：在I中挑出点后是+的项目有：E E.+T,将点移到+后面得J=E E+.T对J进行闭包运算得 CLOSURE(J)=E E+.T，T.F，T.T*F,F.(E),F.i GO(I,+)=E E+.T，T.
25、F，T.T*F,F.(E),F.i用状态图表示为：,5.4.3 构造识别活前缀的有穷自动机,5.4.3 构造识别活前缀的有穷自动机,3、举例说识别活前缀的有穷自动机的构造方法 假设有拓广文法为：0)SA，1)A(A)，2)Aa 从文法的开始符号所在的规则SA开始，项目S.A将作为有穷自动机的开始状态。项目S.A反映了此时分析器还没有识别任何(非空)活前缀。对例中的文法，开始符号所在的规则为SA，所以开始状态0的项目集有C0=S.A，且项目S.A称为基本项目。然后，需要对项目集中的各成员进行闭包(closure)运算，也就是看项目中的点后面的符号是否是非终结符号。如果是非终结符号，则将该非终结符
26、号为左部的规则，在其右部最前面加点构成项目，并填加到该项目集中。对于C0=S.A，由于S.A点后面是非终结符号A，那么就对文法中所有左部符号为A的规则，在右部最前面加点，并添加到项目集C0中。这样就可获得开始状态0对应得项目集为：C0=S.A,A.(A)，A.a,接下来构造C0的后继项目集。观察状态0的项目集C0的每个项目，发现点后的符号即后继符号为A、(、a，说明项目集C0有3个后继项目集C1(GO0，A)、C2(GO0，()、C3(GO0，a)，即状态0有3条弧线指向状态1、2、3，弧线上分别标记符号A、(、a。下面介绍项目集C1、C2、C3的构造：,5.4.3 构造识别活前缀的有穷自动机
27、,1)首先将C0中后继符号为A的项目挑选出来，可得项目集S.A，将点移到A的后面，得到C1的基本项目集为SA.，然后对此项目集进行闭包运算。由于在该项目集只有一个项目中，且点位于最右，所以闭包运算没有添加任何项目，最终C1=SA.，即GO0，A=1。,5.4.3 构造识别活前缀的有穷自动机,2)看C0中的项目 A.(A)，后继符号是(，将点移到(的后面，得到C2的基本项目集为 A(.A)。由于点后面是非终结符号A，所以将A.(A)，A.a加入项 目集，最终C2=A(.A)，A.(A)，A.a，即GO0，(=2。3)看C0中的项目 A.a，最终得C3=Aa.，即GO0，a=3。到此、我们构造好了
28、状态0、1、2、3。如图5.7所示。,5.4.3 构造识别活前缀的有穷自动机,继续上述的后继项目构造过程,直到再没有新的项目集产生。C2的基本项目集为 A(.A)，最终C2=A(.A)，A.(A)，A.a。分析状态2的项目：A(.A)：后继项目集C4=A(A.)A.(A)：后继项目集仍是C2本身A.a：后继项目集为C3 Aa.对状态4的项目A(A.)后继项目集C5=A(A).。至此，我们得到的所有项目集如表5.8所示。,因为每个项目集是有穷的，因此最终产生的状态数目肯定是有限的。最终产生的识别活前缀的有穷自动机如图5.8所示。,5.4.3 构造识别活前缀的有穷自动机,5.4.3 构造识别活前缀
29、的有穷自动机,4、识别活前缀的有穷自动机构造算法给定一文法G，该文法的开始符号为S，下面算法为给定文法G生成识别活前缀的有穷自动机。该自动机包含有下列项目集集合 C=C0,C1,Cn,其中C0是开始项目集，C称为LR(0)项目集规范族。该自动机的状态是0,1,n,其中每个状态j是由项目集Cj得到的。,1)生成开始项目集：赋给开始项目集一个下标0，然后将项目S.放入集合C0，对应的状态为0。对该项目集执行闭包运算，即找到在圆点之后的非终结符X，将形式为X.的项目放置到集合中，其中X是文法G的一个产生式。该闭包运算也要对所有导出的新项目进行。2)生成LR(0)的所有项目集C：重复第3到第4步，直到
30、再没有新的项目集出现。3)对一个项目集Ci求后继项目集Cj，构造项目集的转换：对项目集Ci中的每个后继符号X进行读操作，生成一个新的项目集Cj，且 GOCi,X=Cj。如果该项目集已经存在，则Cj就是已经存在的项目集；否则，得到一个新的基本项目集Cj；4)对新的项目集进行闭包运算。,5.4.3 构造识别活前缀的有穷自动机,5.4.3 构造识别活前缀的有穷自动机,如果LR(0)项目集规范族中的每个项目集看做有穷自动机的一个状态，则项目集规范族的GO函数把这些项目集连接成一个DFA。令C0为DFA的初态，则该 DFA就是恰好识别文法所有活前缀的有限自动机。因此得结论：对于任一文法G,关于该文法的L
31、R(0)项目集规范族的GO函数定义了一个识别文法所有活前缀的DFA。实际上，一个活前缀w的有效项目集，正是由识别文法所有活前缀的DFA的初态出发，经由标记为w的路径所到达的那个项目集。在LR分析过程中，符号栈中的活前缀的有效项目集就是栈顶的状态所代表的那个项目集。,5.4.4 LR(0)分析表的构造,构造出了识别活前缀的有穷自动机后，就可以构造分析表。分析表分两部分，动作表每列的开头是文法的终结符号以及右界符#，每行的开头为状态号。假设已经构造出LR(0)项目集规范族：C=C0，C1，Cn，其中Ci为项目集的名字，对应的状态为i。假设S是文法开始符号所在的规则，令包含项目S.的项目集Ci对应的
32、状态i为开始状态，那么，分析表的动作表和状态转换表的构造方法为：,1)若项目A.aCi且GOCi,a=Cj,其中a为终结符，置ACTIONi,a=“把状态j和符号a移进栈”，简记为“Sj”;2)若项目A.Ci,则对于任何输入符号a或结束符#，置ACTIONi,a=“用产生式A进行归约”，简记为“Rj”(假定A是文法G的第j条产生式);3)若项目S.Ci,则置ACTIONi,#=“接收”，简记为A；4)若GOi,A=Cj,A为非终结符，则置GOTOi,A=j 5)分析表中凡不能用规则-添入信息的单元为空或均置上ERROR，表示有错。,5.4.4 LR(0)分析表的构造,例5.8，对拓广文法：0)
33、SA、1)A(A)、2)Aa，根据表5.5项目集构造分析表。解：因为文法有3个终结符号，除开始符号外有一个非终结符号A，所以，分析动作表有4列，分别为(、)、a和#，GOTO表有1列A。前面已经求出该文法的项目集规范族为：C0=S.A,A.(A)，A.a C1=SA.C2=A(.A)，A.(A)，A.a C3=Aa.C4=A(A.)C5=A(A).,5.4.4 LR(0)分析表的构造,表5.6 LR(0)分析表,因此，分析表应有6行，分别为0、1、2、3、4和5。,5.4.4 LR(0)分析表的构造,观察项目集C0=S.A,A.(A)，A.a，因为S是开始符号，S.A在C0中，因此0为开始状态
34、。对于C0的项目A.(A)，将点从(前移到(后，产生项目集C2，因为(是终结符，因此，按照分析表构造方法的第1条，在ACTION得0行(列填入S2，即ACTION0,(=S2。对项目A.a，将点从a前移到a后，产生项目集C3，因此，置ACTION0,a=S3。对项目S.A，将点从A前移到A后，产生项目集C1，因为A是非终结符，因此，按照分析表构造方法的第4条，则置GOTOi,A=j。,观察C1=SA.，因为S是开始符号，SA.在C1中，符合分析表构造方法的第3条，因此，置ACTION1,#=A，即接受。,观察C3=Aa.，符合分析表构造方法的第2条，因Aa是文法的第2条规则，因此对ACTION
35、表的3行的所有单元填写R2。,观察C2=A(.A)，A.(A)，A.a、C4=A(A.)和C5=A(A).，我们可填写分析表的其它内容，最后可得分析表如表5.6所示。,5.4.5 LR(0)分析器的工作过程,分析表是LR分析的关键，有了分析表后就可以在总控程序的控制下对输入符号串进行分析，其分析方法如下：,若ACTIONS，a=Sj，a为终结符，则把a移入符号栈，状态j移入状态栈。若ACTIONS，a=Rj，a为终结符或#号，则用第j个产生式归约。设k为第j个产生式右部的符号串长度，将符号栈和状态栈顶的k个元素出栈，将产生式左部符号入符号栈。若ACTIONS，a=A，a为#号，则为接受，表示分
36、析成功。若GOTOS，A=j，A为非终结符号并且是符号栈的栈顶，表示前一个动作是归约，A是归约后移入符号栈的非终结符，则将状态j移入状态栈。若ACTIONS，a=空白，则转入错误处理。,例5.9，利用表5.6的LR(0)分析表分析符号串“(a)”。文法为：0)SA，1)A(A)，2)Aa解：按照LR(0)分析器的工作过程，表5.7列出符号串“(a)”的分析过程。,5.4.5 LR(0)分析器的工作过程,5.4.6 LR(0)文法,项目分成4类：移进项目、归约项目、待约项目和接受项目。一个项目集中可能包含不同类型的项目，但必须满住下面两个条件：1)不能有移进项目和归约项目并存，2)不能有多个归约
37、项目并存。如果某一项目集出现移进项目和归约项目并存，我们说该项目集存在“移进-归约冲突”；如果某一项目集出现多个归约项目并存，我们说该项目集存在“归约-归约冲突”。,例如，某项目集为 S E.,E E.+T，因S E.是归约项目，而E E.+T是移进项目，所以该项目集存在“移进-归约冲突”。如果一个文法的项目集规范族不存在“移进-归约冲突”或“归约-归约冲突”的项目集，那么，称该文法为LR(0)文法，所构造的分析表为LR(0)分析表。,5.4.6 LR(0)文法,观察上例中的项目集规范族，C0=S.A,A.(A)，A.a，移进项目和待约项目共存。C1=SA.，只有接受项目。C2=A(.A)，A
38、.(A)，A.a，移进项目和待约项目共存。C3=Aa.，只有归约项目。C4=A(A.)，只有移进项目。C5=A(A).，只有归约项目。,在这六个项目集中，均不存在“移进-归约冲突”和“归约-归约冲突”，因此，文法SA,A(A)，Aa是LR(0)文法。,只有LR(0)文法才能构造LR(0)分析表，否则，构造的分析表会出现多重定义。LR(0)文法是一种非常简单的文法，在这种文法的识别活前缀的自动机中，每一个状态对应的项目集都不含冲突项目。然而，很多文法都不是LR(0)文法，如在上一章我们使用的表达式文法就不是LR(0)文法。实际上，LR(0)文法并不能充分表达当前程序设计语言中的各种结构。对这些语
39、言为了确定分析动作，至少要向前查看一个符号。这就是我们接下来要介绍的SLR(1)分析器。LR(0)机器的生成是其他LR分析器的基础，掌握了LR(0)，也就不难掌握其它LR分析方法。,5.4.6 LR(0)文法,5.8 语法分析程序的自动生成工具YACC,YACC是美国Bell实验室开发的unix环境下的一个软件开发工具,其含义为：Yet Another CompilerCompiler。YACC是语法分析程序自动生成器。其输入是某个语言的语法规则,输出该语言的语法分析器。目前YACC生成的是一个LALR(1)分析器。使用YAC的流程如图5.11所示。,YACC源程序,YACC,Y_tab.c,Y_tab.c,C编译器,Y_tab.EXE,字符串源程序,Y_tab.EXE,分析结果,图5.11 YACC使用流程,习题,5.1 考虑以下的文法：S S；T|T T a1)为这个文法构造L R(0)的项目集规范族。2)这个文法是不是L R(0)文法？如果是,则构造L R(0)分析表。3)对输入串a；a进行分析。,
