编译原理语法分析精选文档.ppt

《编译原理语法分析精选文档.ppt》由会员分享，可在线阅读，更多相关《编译原理语法分析精选文档.ppt（108页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理语法分析本讲稿第一页，共一百零八页自下而上分析法是一种移进移进-归约归约法。分析过程中采用了一个FIFO分析栈。分析开始后，把输入符号自左至右逐个移进移进分析栈，边边移入边分析移入边分析，一旦栈顶符号串形成句柄句柄就进行一次归约归约，再继续查看栈顶是否形成新的句柄，若仍为句柄，则再归约再归约，如此重复直至栈顶不是句柄。此时再继续向栈中移移进进后续输入符号。重复该过程，直到将整个输入串处理完毕。若此时分析栈只有文法开始符，则输入串是一个句子，否则输入串有错。本讲稿第二页，共一百零八页下面通过例子说明这种分析过程。文法GS：SaAbBAcAcBd试对输入串accbd进行分析，检查该符号串是

2、否是GS的一个句子。假设“#”为输入串界符，将输入串前的“#”放入分析栈，接着将输入串的符号依次进栈，具体分析过程如下:本讲稿第三页，共一百零八页步骤分析栈句柄输入串动作1#accbd#移进2#accbd#移进3#accbd#移进4#aAccbd#归约(用Ac)5#aAcbd#移进6#aAAcbd#归约(用AAc)7#aAbd#移进8#aAbd#移进9#aAbBd#归约(Bd)10#SaAbB#归约(SaAbB)本讲稿第四页，共一百零八页Sa c c b dABA(d)a c c b dABA(c)a c cAA(b)a cA(a)在自下而上分析过程中，每一步归归约约都可画出一棵子树，随着归约

3、的完成，这些子树连成一棵完整的分析树。上述分析过程可用分析树分析树表示如下:本讲稿第五页，共一百零八页由上述建树过程知，自下而上分析过程的每一步归约都是对当前句型的句句柄柄进行归约，即句柄一旦形成总是出现在分析栈栈顶。由于每一步归约都把栈顶符号串用某产生式左部符号替换，故把栈顶的这样一串符号称为可归约串可归约串。上述第6步若不选AAc而选Ac进行归约，则无法归约到S。如何确知栈顶的Ac是可归约串而c不是呢？这需精确定义“可归约串”的概念。本讲稿第六页，共一百零八页若文法GS是无二义文法，则规范推导的逆过程必是规范归约规范归约(最左归约)。对于移进-归约过程，句柄的最最左左性性和分析栈栈栈顶顶相

4、关。对于规范推导所得句型(规范句型)，句柄后面不会出现非终结符，故可用句句柄柄刻画“可归约串”，规规范范归归约约的实质是在移进过程中当栈顶呈现句柄时进行归约。本讲稿第七页，共一百零八页为加深对句柄句柄和归约归约等概念的理解，用修剪语法树修剪语法树方法进一步阐明自下而上分析过程。语法树的一个子树子树由该树的某结点及其所有子孙组成，子树的所有叶结点的自所有叶结点的自左至右排列左至右排列形成一个相对于子树根的短语短语。一个句型的句柄句柄是该句型对应的语法树中最左简单子树最左简单子树的所有树叶的自左至右排列。本讲稿第八页，共一百零八页可采用修修剪剪语语法法树树方法实现归约，即寻找当前语法树的句柄，将句

5、柄中的树叶剪去(归约)，不断修剪直到只剩根结点，完成整个归约过程：Sa A b BA cdcSa A b BA cdSa A b BdSa A b BS本讲稿第九页，共一百零八页至此讨论了句柄和规范归约这两个基本概念，但并没有解决规范归约的问题，因为没有给出寻找句柄的算法。事实上，规范归约的中心问题就是如如何何寻寻找找句句柄柄。寻找句句柄柄的不同算法对应不同的规范归约方法，这一点将在LR分析器中讨论。本讲稿第十页，共一百零八页算符优先分析法是一种简单直观、广为使用的自下而上分析法，特别适合于表表达达式式分析且宜于手工实现。它实际上是依照表达式四则运算过程来进行语法分析。所谓算算符符优优先先分分

6、析析，就是预先规定运算符(确切地说是终结符)之间的优优先先关关系系和结合性质，借助于这种优先关系来比较相邻运算符的优先级，以确定句型的可可归归约约串串并进行归约。注意：算符优先分析不是规范归约算符优先分析不是规范归约。3.4.2算符优先分析法算符优先分析法本讲稿第十一页，共一百零八页1.算符优先文法算符优先文法算符文法算符文法:若一个文法的任一产生式的右部都不含两个相继的非终结符，即不含QR这样的右部，则称该文法为算符文法。算符优先文法算符优先文法:算符优先文法首先应是算符算符文法,其次还要定义任意两个可能可能相继出现的终结符的优先关系。具体定义如下:本讲稿第十二页，共一百零八页假定G是一个不

7、含产生式的算符文法算符文法,对任一对终结符a,b,定义(1)a=b当且仅当文法G中含有形如Pab或PaQb的产生式;(2)ab当且仅当G中含有形如PRb的产生式，而Ra或RaQ。+本讲稿第十三页，共一百零八页若一个算符文法G中任一终结符对任一终结符对(a,b)至多满足至多满足下述三种关系之一:a=b，ab则称文法G是一个算符优先文法算符优先文法。例例3.10试说明下述文法G是算符文法，但不是算符优先文法。EE+EE*E(E)i解:由于文法G的任一产生式右部都不含两个相邻的非终结符，故文法G是是算符文法。本讲稿第十四页，共一百零八页(1)由于存在EE+E，而E+E中第二个E可推出E*E，故有+*

8、可见,运算符+和*之间同时存在两种不同的优先关系，故文法G不是算符优先文法。本讲稿第十五页，共一百零八页2.算符优先关系表的构造算符优先关系表的构造通过检查文法的每个产生式的各个侯选式,可找出所有满足a=b的终结符对。为找出所有满足关系“”的终结符对,需先对文法的每个非终结符每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):FIRSTVT(P)=a|Pa或PQa,aVT而QVNLASTVT(P)=a|Pa或PaQ,aVT而QVN+本讲稿第十六页，共一百零八页FIRSTVT集的构造方法集的构造方法：(1)若有产生式Pa或PQa，则aFIRSTVT(P)；(2)若有产生式PQ,且

9、aFIRSTVT(Q),则aFIRSTVT(P)。本讲稿第十七页，共一百零八页例如例如试构造文法GE的FIRSTVT集。GE:EE+TTTT*FFF(E)i解:根据规则(1)知：由EE+得,FIRSTVT(E)=+；由TT*得,FIRSTVT(T)=*；由F(和Fi得,FIRSTVT(F)=(,i根据规则(2)知：由TF和FIRSTVT(F)=(,i得,FIRSTVT(T)=*,(,i；由ET和FIRSTVT(T)得,FIRSTVT(E)=+,*,(,i本讲稿第十八页，共一百零八页LASTVT集构造方法集构造方法：(1)若有产生式Pa或PaQ，则aLASTVT(P)；(2)若有产生式PQ,且a

10、LASTVT(Q),则aLASTVT(P)。本讲稿第十九页，共一百零八页例如例如试构造文法GE的LASTVT集。GE:EE+TTTT*FFF(E)i解:根据规则(1)知：由E+T得,LASTVT(E)=+由T*F得,LASTVT(T)=*由F)和Fi得,LASTVT(F)=),i根据规则(2)知：由TF和LASTVT(F)得,LASTVT(T)=*,),i;由ET和LASTVT(T)得,LASTVT(E)=+,*,),i。本讲稿第二十页，共一百零八页构造优先关系表的方法构造优先关系表的方法：(1)对形如Pab或PaQb的产生式,有a=b；(2)对形如PaR的产生式,若bFIRSTVT(R),则

11、ab。(4)对于语句括号#,有#=#本讲稿第二十一页，共一百零八页例例3.11构造文法GE的算符优先关系表。GE:EE+TTTT*FFF(E)i解:构造构造FIRSTVT集集根据规则(1)知：由EE+得,FIRSTVT(E)=+；由TT*得,FIRSTVT(T)=*；由F(和Fi得,FIRSTVT(F)=(,i根据规则(2)知：由TF和FIRSTVT(F)=(,i得,FIRSTVT(T)=*,(,i；由ET和FIRSTVT(T)得,FIRSTVT(E)=+,*,(,i本讲稿第二十二页，共一百零八页构造构造LASTVT集集根据规则(1)知：由E+T得,LASTVT(E)=+；由T*F得,LAST

12、VT(T)=*；由F)和Fi得,LASTVT(F)=),i。根据规则(2)知：由TF和LASTVT(F)得,LASTVT(T)=*,),i;由ET和LASTVT(T)得,LASTVT(E)=+,*,),i。本讲稿第二十三页，共一百零八页构造优先关系表构造优先关系表根据规则(1),由“(E)”知,(=)。根据规则(2),由E+T知,+FIRSTVT(T),即+*,+(,+i由T*F知,*FIRSTVT(F),即*(,*i由F(E知,(FIRSTVT(E),即(+,(*,(,(+，即+，*+，)+，i+由TT*知,LASTVT(T)*，即*，)*，i*由FE)知,LASTVT(E)，即+)，*)，

13、)，i)由#E#知,#=#；#FIRSTVT(E),即#+,#*,#(,#,即+#,*#,)#,i#本讲稿第二十五页，共一百零八页故算术表达式文法的优先关系表优先关系表如下:+*i()#+*i(#=本讲稿第二十六页，共一百零八页3.算符优先分析算法的设计算符优先分析算法的设计由于算符优先分析法仅在终结符之间终结符之间定义了优先关系而未对非终结符非终结符定义优先关系，这就无法使用优先关系表去识别由单个非终结符组成的可归约串，因此算符优先分析法不是用句柄而是用最左素短语最左素短语来刻画“可归约串”。所谓句型的素短语素短语是指这样一种短语,它至少包含至少包含一个终结符且除自身外不再包含其它更小的素短

14、语。最左素短语最左素短语是处于句型最左边的那个素短语。本讲稿第二十七页，共一百零八页如何让计算机寻找最左素短语？算符优先文法的句型句型的一般形式为#N1a1N2a2NnanNn+1#其中,ai是终结符,Ni是可有可无的非终结符。算符优先文法任一句型的最左素短语最左素短语是满足下述条件的最左子串:NjajNj+1aj+1NiaiNi+1aj-1ai+1本讲稿第二十八页，共一百零八页查找最左素短语的方法查找最左素短语的方法：(1)最左子串法最左子串法先找出句句型型中终结符由左至右满足aj-1ai+1的最左子串。再检查文法的每个候选式,看其是否满足:所 有 终 结 符 由 左 至 右 的 排 列 恰

15、 为ajaj+1ai,即终结符对应相等而非终结符仅对应位置相同。若存在这样的候选式,则用该候选式进行归约。本讲稿第二十九页，共一百零八页(2)语法树法语法树法先先画出句型的语法树,再再找语法树中所有所有相邻相邻终结符终结符间的优先关系。确定相邻终结符间优先关系的原则:语法树中同层的优先关系为“=”;不同层时,层次在下的优先级高,层次在上的优先级低;在句型两侧加上语句括号“#”,则有#。最后最后按最左素短语必须具备的条件确定最左素短语。本讲稿第三十页，共一百零八页例例3.12文法GE:EE+T|TTT*F|FF(E)|i试确定F+T*i的最左素短语。解:画句型F+T*i的语法树,根据语法树确定相

16、邻终结符间优先关系如图,故最左素短语为i。注意:最左直接短语为FEEE*TFTiF#*i#本讲稿第三十一页，共一百零八页算符优先分析算法算符优先分析算法:k=1;Sk=#;/k代表栈S的使用深度doa=下一个输入符;if(SkVT)j=k;elsej=k1;/j指栈顶终结符while(Sja)/找最左SjadoQ=Sj;/j从最左素短语末逐步移向首if(Sj1VT)j=j1;elsej=j2;while(Sj=Q);把Sj+1Sk归约为某个N;k=j+1;Sk=N;/把N置于原Sj+1位置if(Sja)|(Sj=a)k=k+1;Sk=a;elseerror();/若栈顶Sja或=a则将a压栈w

17、hile(a!=#);本讲稿第三十二页，共一百零八页上述算法工作过程中,若出现j减1后其值小于等于0,则意味着输入串有错。正确情况下,算法工作完毕时符号栈将呈现#S#。例例3.13文法GE及其优先关系如例3.12所示,试给出输入串i+i*i的算符优先分析过程。解:输入串i+i*i的算符优先分析过程如下:本讲稿第三十三页，共一百零八页符号栈符号栈输入串输入串动动作作#i+i*i#i#i+i*i#+,用用Fi归约归约#F+i*i#+#F+i*i#+i#F+i*i#+*,用用Fi归约归约#F+F*i#+*#F+F*i#+*i#F+F*i#*#,用用Fi归约归约#F+F*F#+#,用用TT*F归约归约

18、#F+T#,用用EE+T归约归约#E#E#结束结束本讲稿第三十四页，共一百零八页算符优先分析的归归约约只关心句型中由左至右终终结结符符序序列列的优先关系,不涉及非终结符。再以i+i为例,给出其算符优先分析过程和规范归约过程。算符优先分析比规范归约要快得多。这既是算符优先分析的优点,也是它的缺点,因为这可能把本来不成句子的输入串误认为是句子,这种缺点易于弥补。本讲稿第三十五页，共一百零八页例例3.14试设计下述文法的算符优先分析表:GS:SiBtSiBtAeSaAiBtAeSaBb解:首先构造构造FIRSTVT集集和和LASTVT集集FIRSTVT(S)=i,a;FIRSTVT(A)=i,a;F

19、IRSTVT(B)=b;LASTVT(S)=t,e,a;LASTVT(A)=e,a;LASTVT(B)=b;由由AS知,LASTVT(S)LASTVT(A)即LASTVT(A)=t,e,a本讲稿第三十六页，共一百零八页然后构造优先关系表构造优先关系表:(1)由产生式SiBtAeS和SiBtS可知:由SiB得,it；由StA得,te；由SeS得,eFIRSTVT(S)；由SiBt得,i=t；由StAe得,t=e；由StS得,te和t=e,由iBtAeS知,此时应将iBtAeS同时归约为S或A,即取t=e。本讲稿第三十七页，共一百零八页最后得到优先关系表如下:iteabiteb=本讲稿第三十八页，

20、共一百零八页4.优先函数优先函数用优先关系表表示终结符间的优先关系时,存存储储量量大大,查查找找费费时时。若给终结符赋一个值,值的大小反映其优先关系,则终结符间的优先关系比较就转为值的比较。一个终结符在栈中与在输入串中的优先值不同,例如,既存在+),又存在)+。因此,对一个终结符a而言,它应该有一个左左优优先先数数f(a)和一个右优先数右优先数g(a)。本讲稿第三十九页，共一百零八页若根据一个文法的算符优先关系表,使得文法中每个终结符a和b满足下述条件:(1)若存在a=b，则有f(a)=g(b)；(2)若存在ab，则有f(a)g(b)；(3)若存在ab=本讲稿第四十一页，共一百零八页根据优先关

21、系表构造优先函数f和g的方法有两种:关系图法、直接构造法(1)用关系图法关系图法构造优先函数的步骤对每个终结符a(包括“#”),令其对应两个符号fa和ga,画一张以所有fa和ga为结点的方向图：若ab或a=b,画一条从fa到gb的有向边;若ab而f(a)g(b),则令f(a)=g(b)+1；若a*i(#=本讲稿第四十五页，共一百零八页解:(1)用关系图法构造的优先关系图如下:ff*fif)gg*gig(g)f(本讲稿第四十六页，共一百零八页+*i()f46626g35772由上图求得优先函数如下:本讲稿第四十七页，共一百零八页迭代函数迭代函数函数函数+*i()0(初值初值)f11111g111

22、111f24414g235512f35515g246613f35515g24661(2)由定义直接计算优先函数的过程如下:本讲稿第四十八页，共一百零八页3.5 LR分分 析析 法法LR分析法是一种自下而上进行规规范范归归约约的语法分析方法,L指自左向右扫描输入串,R指最右推导(规范归约)。LR分析法比递归下降分析法、LL(1)分析法对文法的限制要少得多,大多数无二义性CFG语言都可用LR分析器识别,且速度快,并能准确、指出输入串的语法错误及出错位置。LR分析法的主要缺点:手工构造工作量相当大,必须求助自动产生工具。本讲稿第四十九页，共一百零八页3.5.1LR分析器的工作原理分析器的工作原理规范

23、归约(最右推导逆过程)的关键是寻寻找找句句柄柄。LR分析法的基本思想:在规范归约过程中,一方面记住已移进和归约出的符号串,即记住“历史”;另一方面根据所用产生式推测未来可能遇到的输入符,即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈栈顶时,希望能根据所记载的“历史”、“展望”及“现实”材料来确定栈顶符号是否构成句柄。本讲稿第五十页，共一百零八页LR分析器的结构示意如下所示,它由分析栈、分析表分析表和总控程序三部分组成:a1a2aian#LR分析表总控程序输入串：栈顶#x1xm输出s0s1sm分析栈本讲稿第五十一页，共一百零八页LR分析器实质上是一个带先进后出栈的DFA。“历史”和“展

24、望”材料被抽象成某些“状态”,而分分析析栈栈用来存放这些状态,栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候,栈顶的状态都代表了整个“历史”和已推测出的“展望”。本讲稿第五十二页，共一百零八页LR分析器的每一步工作都由栈栈顶顶状状态态和现现行行输输入入符符唯一决定。为了易于归约,把已归约出的文法符号也放在栈中。栈的每一项内容包括状态s和文法符号X两部分。(s0,#)为分析开始前预先放入栈里的初始状态和句子括号。栈顶状态为sm,符号串X1X2Xm是已移进归约出的文法符号串。本讲稿第五十三页，共一百零八页LR分分析析表表是LR分析器的核心,它包括两部分:动作表

25、(ACTION表)(二维数组)状态转换表(GOTO表)(二维数组)ACTIONs,a规定了状态s面临输入符a时应采取的动作。GOTOs,X规定了状态s面对文法符号X(终结符或非终结符)时的下一状态。显然,GOTOs,X定义了一个以文法符号为字母表的DFA。本讲稿第五十四页，共一百零八页ACTIONs,a的动作:(1)移进移进:使(s,a)的下一状态s=GOTOs,a和输入符a进栈,下一输入符变现行输入符。注:对终结符a,下一状态s的值GOTOs,a实际上放在ACTIONs,a中(2)归约归约:用某一产生式A进行归约。若的长度为,则归约动作是去掉栈顶的个项,使状态sm-变成栈顶状态,然后使(sm

26、-,A)的下一状态s=GOTOsm-,A和文法符号A进栈。归约不改变现行输入符。执行归约意味着栈顶符号串Xm-+1Xm是句柄。本讲稿第五十五页，共一百零八页(3)接受接受:宣布分析成功,分析器停止工作。(4)报错报错:报告发现源程序有错,调用出错处理程序。LR分析器总总控控程程序序的工作十分简单,它的任一步只需按分析栈栈栈顶顶状状态态s和现现行行输输入入符符a执行ACTIONs,a所规定的动作。LR分分析析器器的的工工作作过过程程可看成是栈中状态序列、已归约串和输入串构成的三元式的变化过程。本讲稿第五十六页，共一百零八页例如例如,算术表达式文法GE如下:GE:(1)EE+T(2)ET(3)TT

27、*F(4)TF(5)F(E)(6)Fi文法GE的LR分析表见表3.13,试给出语句i+i*i的LR分析过程。本讲稿第五十七页，共一百零八页表3.13算术表达式文法的LR分析表状态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5本讲稿第五十八页，共一百零八页步骤步骤状态栈状态栈符号栈符号栈输入串输入串动动作作说说明明10#i+i*i#ACTION0,i=s5,状态5入栈205#i+i*i#r6:Fi归约,GOTO

28、(0,F)=3入栈303#F+i*i#r4:TF归约,GOTO(0,T)=2入栈402#T+i*i#r2:ET归约,GOTO(0,E)=1入栈501#E+i*i#ACTION1,+=s6,状态6入栈6016#E+i*i#ACTION6,i=s5,状态5入栈表3.14i+i*i的LR分析过程本讲稿第五十九页，共一百零八页70165#E+i*i#r6:Fi归约,GOTO(6,F)=3入栈80163#E+F*i#r4:TF归约,GOTO(6,T)=9入栈90169#E+T*i#ACTION9,*=s7,状态7入栈1001697#E+T*i#ACTION7,i=s5,状态5入栈11016975#E+T

29、*i#r6:Fi归约,GOTO(7,F)=10入栈120169710#E+T*F#r3:TT*F归,GOTO(6,T)=9入栈130169#E+T#r1:EE+T,GOTO(0,E)=1入栈1401#E#Acc:分析成功本讲稿第六十页，共一百零八页如何由文法构造如何由文法构造LR分析表分析表?LR文文法法:对于一个文法,如果能够构造一张LR分析表使得它的每个入口均是唯一确定的,则称该文法为LR文法文法。对于LR文法,当分析器对输入串进行自左至右扫描时,一旦句柄呈现于栈顶,能及时对它实行归约。有些情况下LR分析器需“展望”和实际检查未来的k个输入符才能决定应采取什么样的“移进-归约”决策。本讲稿

30、第六十一页，共一百零八页LR(k)文文法法:一个文法如果能用一个每步最多向前检查k个输入符的LR分析器进行分析,则称该文法为LR(k)文法文法。若一个文法的任何“移进-归约”分析器都存在下述情况:尽管栈的内容和下一输入符都已了解,但仍无法确定是“移进”还是“归约”,或无法从几种可能的归约中确定其一,则该文法为非LR(1)文法。注意:(1)LR文法肯定是无二义的,一个二义文法不会是LR文法。(2)LR分析技术可适当修改以适于一定的二义文法。本讲稿第六十二页，共一百零八页四种四种LR分析表的构造方法分析表的构造方法:(1)LR(0)表的构造方法:该法局限性很大,但它是建立一般LR分析表的基础。(2

31、)SLR(1)表(简单LR表)的构造方法:该法较易实现又极有使用价值。(3)LR(1)表(规范LR表)的构造方法:该法适用于大多数CFG文法,但分析表体积庞大。(4)LALR表(向前LR表)的构造方法:该法介于SLR(1)和LR(1)之间。本讲稿第六十三页，共一百零八页3.5.2LR(0)分析表的构造分析表的构造希望仅由一种只概括“历史”资料而不包含推测性“展望”材料的简单状态就能识别呈现在栈顶的某些句柄，LR(0)项目集就是这样一种简单状态。讨论LR分析法时,需要定义一个重要概念,这就是文法规范句型的活活前前缀缀。字的前前缀缀是指该字的任意首部,例如,字abc的前缀有、a、ab或abc。所谓

32、活活前前缀缀是指规范句型的一个前缀,这种前缀不含句柄之后的任何符号。本讲稿第六十四页，共一百零八页在LR分析过程中的任何时候，栈里的文法符号X1X2Xm应构成活前缀。把输入串的剩余部分匹配于其后应成为规范句型(如果整个输入串确为一个句子的话)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，就意味着所扫描的部分没有错误。本讲稿第六十五页，共一百零八页对于文法GS,首先要构造一个NFA,它能识别GS的所有活前缀,这个NFA的每个状态称为一个项目项目。项项目目:文法GS中每一产生式的右部添加一个圆点,称为文法GS的一个LR(0)项目,简称项目。例如,产生式AXYZ对应四个项目：AXYZAXYZ

33、AXYZAXYZ注意,产生式A只对应一个项目A本讲稿第六十六页，共一百零八页一个项目指明了在分析过程的某个时刻看到产生式的多大一部分。通过使用文法的项目可构造一个NFA来识别文法的所有活前缀，再用子集法把识别活前缀的NFA确定化，使之成为一个以项目集合为状态的DFA，这个DFA就是建立LR分析算法的基础。本讲稿第六十七页，共一百零八页识别一个文法活前缀的DFA的项目集的全体称为这个文法的LR(0)项项目目集集规规范范族族。这 个 规 范 族 提 供 了 建 立 一 类 LR(0)和SLR(1)分析器的基础。圆点在最右端的项目,如A,称为一个归归约约项项目目;对文法的开始符号S的归约项目,如S,

34、称为接接受受项项目目;形如Aa的项目(a为终结符),称为移移进进项项目目;形如AB的项目(B为非终结符)，称为待待约约项目项目。本讲稿第六十八页，共一百零八页1.LR(0)项目集规范族的构造项目集规范族的构造可用_CLOSURE构造一个文法的LR(0)项目集规范族。首先构造文法GS的拓拓广广文文法法GS，它包含整个GS并引进一个不出现在GS中的非终结符S，同时加进了一个新产生式SS。这样，仅含项目SS的状态是唯一的接受状态。本讲稿第六十九页，共一百零八页假定I是文法GS的任一项目集,定义和构造CLOSURE(I)的方法:(1)I的任何项目都属于CLOSURE(I)；(2)若AB属于CLOSUR

35、E(I)，则对任何关于B的产生式B,其项目B属于CLOSURE(I)。(3)重复(1)(2)直至CLOSURE(I)不再增大为止。本讲稿第七十页，共一百零八页假定I是文法GS的任一项目集,X是一个文法符号(终结符或非终结符),则状态转换函数GO(I,X)的定义的定义为GO(I,X)=CLOSURE(J)其 中J=任 何 形 如 AX的 项 目|AX属于I。若I是对某个活前缀有效的项目集(状态),则GO(I,X)是对X有效的项目集(状态)。本讲稿第七十一页，共一百零八页通过CLOSURE(I)和GO(I,X)构造拓广文法GS的LR(0)项目集规范族的方法:(1)求出I的闭包CLOSURE(I)(

36、2)先 用 GO(I,X)求 出J,再 对 J求 其 闭 包CLOSURE(J)。以此类推,最终可构造出拓广文法GS的LR(0)项目集规范族。本讲稿第七十二页，共一百零八页2.LR(0)分析表的构造分析表的构造若文法GS的拓广文法GS的活前缀活前缀识别自动机识别自动机中的每个状态(项目集)不存在下述情况：既含移进项目又含归约项目或含有多个归约项目,则GS是一个LR(0)文法文法。换言之,LR(0)文法的项目集规范族中任一项目集均不包含冲突项。对于LR(0)文法,可直接从它的项目集规范族C和状态转换函数GO(I,X)构造出其LR(0)分析表。本讲稿第七十三页，共一百零八页假定C=I0,I1,In

37、,令每个项目集Ik的下标k作为分析器的状态,并令包含项目SS的集合Ik的下标k为分析器的初态,则LR(0)分析表的构造算法如下:(1)若项目Aa属于Ik且GO(Ik,a)=Ij,a为终结符,则置ACTIONk,a为“将(j,a)移进栈”,简记为sj。本讲稿第七十四页，共一百零八页(2)若项目A属于Ik,则对任何终结符a或#,置ACTIONk,a为“用A归约”,简记为rj(其中j是第j个产生式。(3)若项目SS属于Ik,则置ACTIONk,#为接受,简记acc。(4)若GO(Ik,A)=Ij,A为非终结符,则置GOTOk,A=j。(5)分析表中凡不能用规则(1)(4)填入的空白格均置为“出错标志

38、”。本讲稿第七十五页，共一百零八页例例3.16试构造文法GS的LR(0)分析表:GS:SBBBaBb解:将文法GS拓广为文法GS：GS:(0)SS(1)SBB(2)BaB(3)Bb本讲稿第七十六页，共一百零八页该文法的LR(0)项目集规范族项目集规范族为:I0:SSSBBBaBBbI1:SSI2:SBBBaBBbI3:BaBBaBBbI4:BbI5:SBB I6:BaB本讲稿第七十七页，共一百零八页SI0:SSSBBBaBBbI1:SSSI2:SBBBaBBbI5:SBBBI4:BbbbI3:BaBBaBBbabI6:BaBBaa识别该文法活前缀的DFA为:本讲稿第七十八页，共一百零八页该文法

39、的LR(0)分析表为:状态状态ACTIONGOTOab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2本讲稿第七十九页，共一百零八页3.5.3SLR(1)分析表的构造分析表的构造LR(0)文法是一类非常简单的文法,其特点是该文法的活前缀识别自动机的每一状态都不含冲突项。但即使是算术表达式文法也不是LR(0)的,因此需要研究一种简单“展望”材料的LR分析法,即SLR(1)法法。实际上,许多冲突性的动作都可以通过考察有关非终结符的FOLLOW集而获得解决。本讲稿第八十页，共一百零八页SLR(1)冲突解决办法冲突解决办法如下：假定LR(0)规范族的任一项

40、目集I中含有m个移进项目:A1a11,A2a22,Amamm同时含有n个归约项目:B1,B2,Bn若集合a1,am,FOLLOW(B1),FOLLOW(Bn)两两不相交,则隐含在I中的动作冲突可通过检查现行输入符a属于上述n+1个集合中的哪个集合而获得解决,即:本讲稿第八十一页，共一百零八页(1)若a是某个ai,i=1,2,m,则移进;(2)若aFOLLOW(Bi),i=1,2,n,则用产生式Bi进行归约;(3)对(1)(2)以外的情况,报错。冲突性动作的这种解决办法叫做SLR(1)冲突解决办法冲突解决办法。本讲稿第八十二页，共一百零八页文法GS的SLR(1)分析表的构造方法分析表的构造方法:

41、先把GS拓广为GS，对GS构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO，然后再使用C和GO按下面的算法构造GS的SLR(1)分析表:假定C=I0,I1,In,令每个项目集Ik的下标k为分析器的一个状态,并令含项目SS的Ik的下标k为初态,则SLR(1)分分析表析表可按如下方法构造:本讲稿第八十三页，共一百零八页(1)若项目Aa属于Ik且GO(Ik,a)=Ij,a为终结符,则置ACTIONk,a为“将状态j和符号a移进栈”,即sj。(2)若项目A属于Ik,则对任何输入符a,aFOLLOW(A),置ACTIONk,a为“用产生式A进行归约”,即rj。(3)若项目SS属于Ik,则

42、置ACTIONk,#为接受,即acc。(4)若GO(Ik,A)=Ij,A为非终结符,则置GOTOk,A=j。本讲稿第八十四页，共一百零八页(5)凡不能用规则(1)(4)填入信息的空白格均置“出错标志”。若按上法构造的ACTION表和GOTO表不含多重入口,则称它为文法GS的SLR(1)表表。具有SLR(1)表的文法称为一个SLR(1)文文法法。使用SLR(1)表的分析器叫做SLR(1)分分析器析器。若按上述算法构造的分析表存在多重入口,则不能用上述算法构造分析器。本讲稿第八十五页，共一百零八页例例3.18构造例3.16文法SLR(1)分析表。解:先拓广文法,再求文法的LR(0)项目集规范族及D

43、FA,求所有形如A的项目的FOLLOW(A),即对SBB,BaB,Bb求FOLLOW集:由FOLLOW集的构造方法得：FOLLOW(S)=#；FIRST(B)FOLLOW(B),即FOLLOW(B)=a,b；由SS,FOLLOW(S)FOLLOW(S),即FOLLOW(S)=#；由SBB,FOLLOW(S)FOLLOW(B),即FOLLOW(B)=a,b,#。本讲稿第八十六页，共一百零八页最后求GS的SLR(1)分析表如下:状状态态ACTIONGOTOab#SB0s3s4121acc2s3s453s3s464r3r3r35r16r2r2r2本讲稿第八十七页，共一百零八页*3.5.4LR(1)分

44、析表的构造分析表的构造在SLR(1)方法中，若项目集Ik含有A，那么在状态k时，只要当前输入符aFOLLOW(A)，就采取“用A归约”的动作。但在某种情况下，当状态k呈现于栈顶时，栈里的符号串所构成的活前缀未必允许把归约为A，因为可能没有一个规范句型含有前缀Aa。因此，在这种情况下，用A进行归约未必有效。本讲稿第八十八页，共一百零八页可设想让每个状态含有更多的展望信息,这些信息将有助于克服动作冲突和排除无效归约,必要时对状态进行分裂,使得LR分析器的每个状态能确切指出当后跟哪些终结符时才允许把归约为A。为此,需重新定义项目,使得每个项目都附带有k个终结符。现在每个项目的一般形式为A,a1a2a

45、k此处,A是一个LR(0)项目,ai是终结符,这种项目称为LR(k)项目,其中,a1a2ak称为向前搜索串(或展望串)。本讲稿第八十九页，共一百零八页向 前 搜 索 串 仅 对 归 约 项 目A,a1a2ak有意义,对移进或待约项目不起作用。归约项目A,a1a2ak意味着当它所属状态呈现在栈顶且后续的k个输入符为a1a2ak时,才把栈顶的归约为A。这里只对k1的情形感兴趣。构造有效的LR(1)项目集族的方法和构造LR(0)项目集规范族的方法本质上一样,也需两个函数:CLOSURE(I)和GO(I,X)。本讲稿第九十页，共一百零八页项目集I的闭包可按如下方式构造：(1)I的任何项目都属于CLOS

46、URE(I)。(2)若项目AB,a属于CLOSURE(I),B是一产生式,则对于FIRST(a)中的每个终结符b,若B,b原来不在CLOSURE(I)中,把它加进去。(3)重复(2)直到CLOSURE(I)不再增大。函数GO(I,X)定义为:GO(I,X)=CLOSURE(J)其中J=形如AX,a的项目|AX,a属于I本讲稿第九十一页，共一百零八页构造构造LR(1)分析表的算法分析表的算法:假定C=I0,I1,In,令每个Ik的下标k为分析表的状态,令含有SS,#的Ik的k为分析器的初态。LR(1)分析表可按如下方法构造：(1)若项目Aa,b属于Ik且GO(Ik,a)=Ij,a为终结符,则置A

47、CTIONk,a为“将状态j和符号a移进栈”,简记为sj；本讲稿第九十二页，共一百零八页(2)若项目A,a属于Ik,则置ACTIONk,a为“用产生式A归约”,简记为rj,其中j是产生式的编号;(3)若项目SS,#属于Ik,则置ACTIONk,#为接受,简记为acc;(4)若GO(Ik,A)=Ij,A为非终结符,则置GOTO(Ik,A)=j;(5)分析表中凡不能用规则(1)(4)填入信息的空白栏均填“出错标志”。本讲稿第九十三页，共一百零八页对于LR(1),有些状态(项目集)除向前搜索符不同外,其核心部分都相同,即LR(1)比SLR(1)和LR(0)存在更多的状态。因此,LR(1)的构造比LR

48、(0)和SLR(1)更复杂,占用的存储空间也更多。本讲稿第九十四页，共一百零八页3.5.5LALR分析表的构造自学对LR(1)来说,存在着某些状态(项目集),这些状态除向前搜索符不同外,其核心部分都相同,能否将核心部分相同的诸状态合并为一个状态,这种合并是否会产生冲突?下面将对此进行讨论。两两个个LR(1)项项目目集集具具有有相相同同的的心心是指除去搜索符之后这两个集合是相同的。如果把所有同心的LR(1)项目集合并为一,将看到这个心就是一个LR(0)项目集,这种LR分析法称为LALR方法。本讲稿第九十五页，共一百零八页对于同一个文法,LALR分析表和LR(0)以及SLR分析表永远具有相同数目的

49、状态。LALR方法本质上是一种折中方法，LALR分析表比LR(1)分析表要小得多，能力也差一点，但它却能对付一些SLR(1)所不能对付的情况。本讲稿第九十六页，共一百零八页由于GO(I,X)的心仅仅依赖于I的心，因此LR(1)项目集合并之后的转换函数GO可通过GO(I,X)自身的合并而得到，因而在合并项目集时无需考虑修改转换函数问题(假定I1与I2的心相同，即项目集相同，则GO(I1,X)=GO(I2,X)，但这里的项目集是不包括搜索符的)。但是，动作ACTION必须进行修改，使之能够反映被合并的集合的既定动作。本讲稿第九十七页，共一百零八页假定有一个LR(1)文法,它的LR(1)项目集不存在

50、动作冲突,但如果把同心集合并为一,就可能导致产生冲突。这种冲突不会是移进/归约的冲突,因为若存在这种冲突,则意味着面对当前的输入符号a,有一个项目A,a要求采取归约动作,而同时有另一项目Ba,b要求把a移进;这两个项目同处于(合并前的)某一个集合中,则意味着合并前必有某个c使得A,a和Ba,c同处于(合并前的)某一集合,这意味着原来的LR(1)项目集已存在移进/归约冲突。本讲稿第九十八页，共一百零八页因此,同同心心集集的的合合并并不不会会产产生生新新的的移移进进/归归约约冲冲突突(因是同心合并,故只改变搜索符,不改变移进或归约操作,故不可能存在移进/归约冲突)。同时说明,若原LR(1)存在着移