自下而上语法分析

1、4/23/15 S - (L)|aL - L,S|S 只有直接左递归S - (L)|aL - SLL- ,SL| first(S)=(,a first(L)=(,a, first(L)=, follow(S)=(first(L)-) + follow(L) + follow(L) + $ = $,) follow(L)=) follow(L)=)4/23/15(),a$SS - (L)S - aLL - SLL - SLLL - L- ,SL4/23/15 下面文法是否LL(1)文法？说明理由S - AB|PQxA - xyB - bcP - dP| Q - aQ|4/23/15 不是LL(1

2、)文法 LL(1)文法：对于产生式A-|本题中，FIRST(AB)=x, FIRST(PQx)=d,a,x不满足条件(1)语法分析自下而上分析自下而上分析基本问题移进归约分析法(Shift-reduce parsing)一般的移进归约法LR parsingLR(0)SLRLR(1)LALR自下而上分析法从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；一、自下而上分析基本问题1 、归约利用栈，输入符号移进栈，当栈顶形成P的候选式时，就归约为它的左P符号文法文法G2:SaAcBe AbAAb Bd输入串：输入串：abbcde自下而上法，即“移进-归约”法最右推导：最右推导：aabaAaA

3、baAaAcaAcdaAcBaAcBeS12345678910栈栈S= aAcBe = aAcde=aAbcde= a b b c d eSaAcBe输入串：输入串：abbcdeAAbBdAbSaAcBeAbdb分 析 树最左归约：= S= aAcBe= aAcde= aAbcdea b b c d e SaAcBe输入串：abbcdeAAbBdAb2 规范归约规范归约短语短语:若若G是一个文法，是一个文法，S是文法的开始符是文法的开始符号，若号，若是文法是文法G的一个句型，如果有的一个句型，如果有S A且且 A ，则称，则称是句型是句型相对于相对于非终结符非终结符A的短语。的短语。句柄：句柄

4、：一个句型的一个句型的最左直接短语最左直接短语称为该句型的称为该句型的句柄。句柄。直接短语：直接短语：如果有如果有A ，则称，则称是句型是句型相相对于规则对于规则A 的的直接短语直接短语规范推导：规范推导：即即最右推导最右推导；规范句型：规范句型：由规范推导所得的句型称为规范句由规范推导所得的句型称为规范句型；型；规范归约：规范归约：是关于句型是关于句型的一个的一个最右推导最右推导的逆的逆过程，也称过程，也称最左归约最左归约。例：最右推导和归约考虑文法S aABe A Abc | bB d句子abbcde的归约步骤如下：abbcde aAbcdeaAdeaABeS 对应最右推导的逆过程：对应最

5、右推导的逆过程：S rm aABe rm aAde rm aAbcde rm abbcdeSa A B edA b cb14短语和句柄设有上下文无关文法G = (VT, VN, S, P)，串是文法G的句型，若有A+，且串A也是文法G的句型，则称是句型中关于非终结符号A的短语。 若A ，则称为直接短语。最左直接短语称为句柄(handle)。句柄(handles)句柄是最左直接短语。句柄的右边仅含终结符。SAw161718例考虑文法S aABe A Abc | bB dIt follows that:A b is a handle of abbcde in location 2.S aABe a

6、Ade aAbcde abbcdermrmrmrmSa A B edA b cb20例It follows that: A Abc is a handle of aAbcde in location 2.Sa A B edA b c考虑文法S aABe A Abc | bB dS aABe aAde aAbcde abbcdermrmrmrm21例It follows that: B d is a handle of aAde in location 3.Sa A B ed考虑文法S aABe A Abc | bB dS aABe aAde aAbcde abbcdermrmrmrm22例It

7、 follows that: S aABe is a handle of aABe in location 1.Sa A B e考虑文法S aABe A Abc | bB dS aABe aAde aAbcde abbcdermrmrmrm23S CbBAA Aab|abB C|DbC aD a2425句柄剪枝 (Handle Pruning)从被分析的终结符号串w开始，如果w是文法的句子，那么记w = n，其中n是最右推导的第n步句型：构造最右推导的逆过程，在n中找句柄进行归约得到右句型n-1。26E E + E | E * E | (E ) | id如果文法二义，那么句柄可能不唯一。在句型

8、E + E * id3中，句柄不唯一。E rm E + E rm E + E * E rm E + E * id3 rm E + id2 * id3 rm id1 + id2 * id3E rm E * E rm E * id3 rm E + E * id3 rm E + id2 * id3 rm id1 + id2 * id3 27分析过程的特点从输入串的开头依次读入(移进)单词。一旦发现可归约串(句柄)就立即归约。根据句柄对分析树进行修剪子树，剪去子树的叶子。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串替换成非终结符号，该归约方法通常得到是最右推导的逆过程。右

9、句型句柄归约产生式id1 id2 * id3E id2 * id3E E * id3E E * E E EEid1id2id3E * EE + E E id E id E id E E * E E E + E问题：规范归约用来作语法分析需要解决的规范归约用来作语法分析需要解决的问题：问题：如何在句型中找出句柄如何在句型中找出句柄?在相同的右部有不止一个产生式时在相同的右部有不止一个产生式时,选哪一个选哪一个?LR分析法LR分析程序分析程序(器器)：自左向右自左向右扫描，识别句柄，扫描，识别句柄，自下而上自下而上归约的归约的语法分析程序语法分析程序。LR分析程序生成器：自动生成分析程序生成器：自

10、动生成LR分析程序的程分析程序的程序。序。LR分析器的模型状状态态符符号号S0S1Sm$X1XmLR分析程序分析程序分析表分析表actiongoto输出输出输入串栈栈$anaia132LR语法分析器的行为 为描述LR语法分析的行为，引入概念 格局(Configuration) 用二元组表示 (s0X1s1X2s2Xmsm, aiai+1an$) 栈的内容 尚未处理的输入 Xi代表文法符号，si表示状态 代表右句型X1X2Xmaiai+1an 在分析栈中增加了状态LR分析算法的动作语法分析器的下一动作由当前输入符号ai和栈顶状态sm查询分析表actionsm, ai 决定移进归约接受出错格局初始

11、状态格局栈输入$w$接受状态格局栈输入$S $句柄总会出现在栈顶，而不会在栈的里面。考察任意最右推导中连续两步的可能形式：假设当前状态格局为：栈输入$yz$把句柄归约为B，达到状态格局：栈输入$B yz$移进y入栈中，达到格局：栈输入$By z$栈顶形成句柄By，归约为A，达到状态格局：栈输入$A z$SAz B y假设当前状态格局为：栈输入$xyz$把句柄归约为B，达到状态格局：栈输入$B xyz$移进x, y入栈中，达到格局：栈输入$Bxy z$栈顶句柄y归约为A，达到状态格局：栈输入 $BxA z$SzB x Ay38初始格局LR分析程序输出 Actions, aGotos0a1ai a

12、n$输入栈39移进之前 (s0X1s1X2s2Xmsm, aiai+1an$) 输入LR分析程序输出 Actionsm, ai= “shift s”GotosmXmsm-1Xm-1s0a1ai an$栈40移进之后 (s0X1s1X2s2Xmsmais , ai+1an$) LR分析程序输出 Actionsm, ai= “shift s”GotosmXmsm-1Xm-1s0a1ai an$ais输入栈41LR分析程序输出 栈Actionsm, ai= “r A ”smXmsm-rXm-rs0a1ai an$Gotosm-r, A= s 输入归约之前 (s0X1s1X2s2Xmsm, aiai+

13、1an$) 42归约 从栈中弹出2| 个符号LR分析程序输出 Actionsm, ai= “r A ”sm-rXm-rs0a1ai an$Gotosm-r, A= s 2|输入栈43归约 从栈中弹出2| 个符号，再进栈LR分析程序输出 Actionsm, ai= “r A ”ssm-rXm-rs0a1ai an$Gotosm-r, A= s 2|输入栈归约之后 (s0X1s1X2s2Xmsm-rs, aiai+1an$) 44接受LR分析程序输出 Actions, $= “accept”sX1s0a1ai an$Goto输入栈45报错LR分析程序输出 Actions, a未定义未定义a1ai

14、an$GotosmXmsm-rXm-rs0输入栈冲突 (Conflicts)如果形成这样的格局： 根据栈中的内容和下一个输入符号不能决定是移进还是归约（移进归约冲突），或不能决定用那一条产生式进行归约（归约归约冲突）。47移进归约冲突 stmt if expr then stmt | if expr then stmt else stmt | other存在移进-归约冲突。一般地，任何二义性文法都不是LR(k)文法。假设当前状态格局为：栈输入 if expr then stmtelse $48用栈实现移进归约分析必须解决两个问题确定右句型中将要归约的子串（句柄）如何确定选择哪一个产生式一般方法

15、用栈保存文法符号输入缓冲区存放待分析的串移进(shift)输入符号入栈，直至栈顶出现句柄归约(reduce)句柄，用产生式左部的非终结符替代栈中的句柄1、 LR分析程序A、LR分析程序的分析程序的实质实质：分析栈：分析栈DFA状状态态符符号号S0S1Sm$X1XmLR分析程序分析程序分析表分析表actiongoto输出输出输入串栈栈$anaia1注意注意: 可归约的串在栈顶可归约的串在栈顶,不会在内部不会在内部实现移进实现移进-归约分析的一个方便途径是用一个栈和一个归约分析的一个方便途径是用一个栈和一个输入缓冲区输入缓冲区,用用$表示栈底和输入的结束表示栈底和输入的结束栈输 入$w$B、LR分

16、析的核心分析的核心分析表分析表分析表由分析表由ACTION表表和和GOTO表表两部分组成。两部分组成。ACTIONs,a：表示当状态：表示当状态s面临输入面临输入a时的动作时的动作GOTOs,x：表示面对文法符号：表示面对文法符号x的下一状态的下一状态ACTIONs，a表中的动作种类：C、给出下述文法、给出下述文法G的的LR分析表分析表 分析程序的动作移进: 下一输入符号移进栈顶归约: 把句柄按产生式的左部进行归约，然后根据当前状态和当前的非终结符执行GOTO接收: 分析程序报告成功出错: 发现了一个语法错,调用出错处理程序 文法G (1)EE+T (2) ET (3)TT *F (4) TF

17、 (5)F(E) (6) Fi 分析表 分析表中记号的含义sj： 把下一状态把下一状态 j 和现行输入符号和现行输入符号 a 移进栈；移进栈；rj： 按第按第 j 个产生式进行归约；个产生式进行归约；然后根据当前状态和当前的非终结符执行GOTOacc： 接受；接受；空白格：出错标志，报错空白格：出错标志，报错分析表的使用分析表的使用状态ACTION(动作)GOTO(转换)i+*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5LL(k)与

18、LR(k)分析LL(k):在看到一个产生式右部推出的前k个符号，就要确定所用的产生式LR(k):在看产生式左部的所有符号，并再向后看k个符号，才决定是否使用该产生式55例 5.8 利用上述分析表，假定输入串为 i * i + i ，描述LR分析器的工作过程。（1） 0$i * i + i $（2） 05$i * i + i $（3） 03$F * i + i $（4） 02$T * i + i $（5） 027$T* i + i $（6） 0275$T*i + i $（7） 02710$T*F + i $（8） 02$T + i $（9） 01$E + i $ACTION 0, i =s5移进

19、 5 和 iACTION 5, * =r6按第6个产生式进行归约，即：(6) FiGOTO0,F=3移进状态3ACTION 10, + =r3按第3个产生式进行归约，即(3) TT *FGOTO0,T=2移进状态2例5.8 利用上述分析表，假定输入串为 i * i + i ，描述LR分析器的工作过程。(续)（10） 016$E+ i $（11） 0165$E+i $（12） 0163$E+F $（13） 0169$E+T $（14） 01$E $ACTION1,$=acc接受输入串！分析表的构造方法分析表的构造方法D、LR文法文法定义：对于一个文法，如果能够依步骤构造一张分析表，使得它的每个入

20、口均是唯一确定的，则我们把这个文法称为LR文法。 LR（k）文法：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。2、LR(0)分析表的构造 A、LR(0)分析表的构造步骤 确定确定G的的LR(0)项目项目 以以LR(0)项目为状态项目为状态,构造一个能识别文法构造一个能识别文法G的所有活的所有活前缀的前缀的NFA 利用子集法利用子集法,将将NFA确定化确定化,成为以项目集合为状态的成为以项目集合为状态的DFA根据根据 上述上述DFA可直接构造出可直接构造出LR分析表分析表B、LR(0)项目（简称项目）定义：定义：文法文法G每一个产生式的

21、右部添加一个圆点，称为每一个产生式的右部添加一个圆点，称为 G的一个的一个LR(0)项目。项目。 如：如：AXY对应三个项目：对应三个项目： AXY AXY AXY 而而: A的项目的项目 A 项目的意义：项目的意义：指明在分析过程的某时刻，我们看到指明在分析过程的某时刻，我们看到产产生式多大一部分生式多大一部分项目在计算机中的表示：项目在计算机中的表示：（m，n） int m，n m：代表产生式编号：代表产生式编号 n：指出圆点的位置：指出圆点的位置 定义：定义：文法文法G每一个产生式的右部添加一个圆点，称为每一个产生式的右部添加一个圆点，称为 G的一个的一个LR(0)项目。项目。 如：如：

22、AXY对应三个项目：对应三个项目： AXY AXY AXY 而而: A的项目的项目 A 如：abc前缀：，a，ab，abc活前缀：规范句型的一个前缀，该前缀是不含句柄之后 的任何符号。 C、字的前缀：指该字的任意首部D、对文法G，构造能识别G的所有活前缀的NFANFA的状态：是一个LR(0)项目构造方法： a. 文法开始符号的形如文法开始符号的形如SS的项目为的项目为NFA的唯一初态；的唯一初态； b. 若状态若状态i和和j出自同一个产生式，而且出自同一个产生式，而且j的圆点只落后于的圆点只落后于I 的圆点一个位置，就从的圆点一个位置，就从i画一条标志为画一条标志为Xi的弧到的弧到j。 （即，

23、（即，i：XX1Xi-1XiXn j：XX1 Xi-1XiXn） c. 若状态若状态i的圆点之后的符号为非终结符，如的圆点之后的符号为非终结符，如I为为 XA，其中，其中A属于属于VN，就从状态，就从状态i画画弧到所有弧到所有 A状态。状态。例2.构造以下文法的拓广文法 文法G的所有LR(0)项目 文法文法 G SE EaA|bB AcA|d BcB|d 1.S E 2. S E 3. E aA 4. E a A 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d 11. E bB 12. E b B 13. E bB 14. B cB 15. B

24、c B 16. B cB 17. B d 18. B d 文法文法 G SE EaA|bB AcA|d BcB|d 利用上述规则a，b，c构造NFA，如图所示： 13A1379111214151764510821618acbdcdBAB 利用CLOSURE方法构造LR(0)项目集规范族 拓广文法 CLOSURE(I)算法(其中I为G的任一项目集)I的任何项目都属于的任何项目都属于CLOSURE(I);若若AB属于属于CLOSURE(I)，那么，对任何关于，那么，对任何关于B的产的产生式生式B，项目，项目B也属于也属于CLOSURE(I);重复执行上述两步骤直至重复执行上述两步骤直至CLOSUR

25、E(I)不再增大为止。不再增大为止。 步骤一步骤一:初态为初态为I,求其求其CLOSURE(I),得到初态项目集。即得到初态项目集。即: 求求CLOSURE（SS) 步骤二步骤二:对所得项目集对所得项目集I和文法和文法G的每个文法符号的每个文法符号X(包括包括VT和和VN) 计算计算GOTO(I,X) =CLOSURE(J)，得到新的项目，得到新的项目集集。 其中其中J=任何形如任何形如A X 的项目的项目| A X 属于属于I 步骤三步骤三:重复步骤二，直至没有新的项目集出现。重复步骤二，直至没有新的项目集出现。 经过以上步骤构造出的项目集的全体即为LR(0)项目集规范族。 利用LR(0)项

26、目集规范族和GOTO函数画出DFA构造项目集规范族方法例例3.构造该文法的构造该文法的LR(0)分析表。假定这个文法的各个产分析表。假定这个文法的各个产生式的编号如下：生式的编号如下： 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d DFA构造：（部分）CLOSURE ( SE ) = SE, EaA, EbB 此即为此即为DFA的状态的状态0令I = SE, EaA, EbB GO( I, a ) = CLOSURE( EaA ) /即即I中所有圆点之后紧跟中所有圆点之后紧跟a的的 = EaA, AcA, Ad GO( I, b ) = CLOSU

27、RE( EbB ) = EbB, BcB, Bd GO( I, E ) = CLOSURE( SE ) = SE 同上步骤，依次对各项目集进行计算0:SE E aA E bB5:BcB B cB B d3:E bB B cB B d2:E aA A cA A d4:AcA A cA A d1:SE 10:Ad 8:AcA 6:EaA7:EbB11:Bd 9:BcBcacccbdddAdABBE$acc LR(0)分析表构造 文法文法 G SE EaA|bB AcA|d BcB|d LR(0)项目。 相关定义： LR(0)项目集规范族：构成识别一个文法活前缀的项目集规范族：构成识别一个文法活前缀

28、的DFA的项的项目集（状态）的全体。目集（状态）的全体。 归约项目：归约项目：A 接受项目：接受项目：S（S文法的开始符号）文法的开始符号） 移进项目：移进项目：Aa（a终结符）终结符） 待约项目：待约项目：AB(B非终结符非终结符) F、LR（0）分析表的构造 相关定义： LR(0)文法：不存在以下两种冲突的文法 移进归约冲突移进归约冲突 归约归约冲突归约归约冲突 LR(0)表：由LR(0)文法得到的分析表 LR(0)分析器：使用LR(0)表的分析器LR(0)分析表的构造方法 如下：a、若项目、若项目Aa属于属于Ik且且GOTO(Ik,a) Ij，a为终结符，置为终结符，置ACTIONk,a

29、为为“把（把（j，a）移进栈）移进栈”，简记为，简记为“sj”；b、若项目、若项目A属于属于Ik，那么，对任何输入符号，那么，对任何输入符号a（或者结束（或者结束符）置符）置ACTIONk,a为为“用产生式用产生式A进行归约进行归约”，简记，简记为为“rj”；其中，假定；其中，假定A为文法为文法G的第的第j个产生式；个产生式；c、若项目、若项目SS属于属于Ik，则置，则置ACTIONk,为为“接受接受”，简记，简记为为“acc”；d、若、若GOTO(Ik,A)Ij，A为非终结符，则置为非终结符，则置GOTOk,Aj；e、分析表中凡不能使用规则、分析表中凡不能使用规则1至至4填入信息的空白格均置

30、填入信息的空白格均置上上“出错标出错标志”。状态ACTION(动作)GOTO(转换)abcd$EAB0s2s311acc2s4s1063s5s1174s4s1085s5s116r1r1r1r1r19 7r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6 该文法的LR(0)分析表如下所示： A、若LR(0)规范族中含有冲突项目,采用向前展望方法解决 例例4. 若若I=Xb，A，B 若当前输入符号为若当前输入符号为b，则含有移进，则含有移进归约冲突；归约冲突； 而而A和和B，又含有归约，又含有归约归约冲突。归约冲突。 解决办法：解决办法

31、： 考察考察FOLLOW（A）和）和FOLLOW（B） （设（设FOLLOW（A）FOLLOW（B）为空，且均不含）为空，且均不含b）3、SLR表的构造方法 则当 I 面临任何输入符号a时，可做出如下“移进归约 决策： 若a=b，移进； 若a属于FOLLOW（A），则用A归约； 若a属于FOLLOW（B），则用B归约； 此外，报错。 B、回顾FOLLOW（A）的计算。（其中A是非终结符） 注：FIRST集是针对终结符、非终结符和产生式构造的； FOLLOW集仅对非终结符构造。C、SLR表的构造方法表的构造方法 若项目若项目Aa属于属于Ik且且GO(Ik,a) Ij，a为终结符，且置为终结符，且

32、置 ACTIONk,a为为“把状态把状态j和符号和符号a移进栈移进栈”，简为，简为“sj”； 若项目若项目A属于属于Ik，那么，对任何输入符号，那么，对任何输入符号a， aFOLLOW(A)，置，置ACTIONk,a为为“用产生式用产生式A进行归约进行归约”，简记为简记为“rj”；其中，假定；其中，假定A为文法为文法G的第的第j个个产生式；产生式；若项目若项目SS属于属于Ik，则置，则置ACTIONk,为为“接受接受”，为为“acc”；若若GOTO(Ik，A)=Ij，A为非终结符，则置为非终结符，则置GOTOk，A= j；分析表中凡不能使用规则分析表中凡不能使用规则1至至4填入信息的空白格均置

33、上填入信息的空白格均置上“出出错标志错标志”。只在归约展望时，即已到产生式末尾，则判断FOLLOW(A)例4：对如下文法构造其SLR分析表。文法文法 G： (0) SE(1) EE+T(2) ET (3) TT*F(4) TF (5) F(E)(6) Fi 该文法的该文法的LR(0)项目集规范族项目集规范族由这些项目集的转换函数由这些项目集的转换函数GO表示成的表示成的DFA文法文法G的非终结符的的非终结符的FOLLOW集如下：集如下：FOLLOW(S) = $ FOLLOW(E) = +, ), $ FOLLOW(T) = +, * , ) , $ FOLLOW(F) = +, * , )

34、, $ SLR分析表分析表LR分析方法：把历史及展望综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作 LR分析程 序状态符号分析栈 action goto LR分析表a1a2ai an$输入串 输出状态ACTION(动作)GOTO(转换)i+*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5文法 G 的SLR分析表如下所示： 考察i1+i2 与 i1i2LR分析本质规范归约的关键问题是寻找句柄.“历史”：已移入符号栈的内容

35、“展望”：根据产生式推测未来可能遇到的输入符号“现实”：当前的输入符号19E + T *是活前缀，读完它后，DFA处于状态I7 I7: TT *F, F ( E ), F id对应了所有可能的三种最右推导形式:E E E+T E+T * FE E E+T E+T * F E+T * (E )E E E+T E+T * F E+T *id规范LR分析表的构造问题：问题：有些无二义文法会产生“移进/归约”冲突 或“归约/归约”冲突产生原因：产生原因：SLR分析法未包含足够多的“展望”信息解决办法：解决办法：让每个状态含有更多的“展望”信息 例3.29 例 I2有两个项目SV =E和EV 移进归约冲

36、突 扩充项目的定义！方法：重新定义项目，使得每个项目都附带有k个终结符；即每个项目的形式为：A , a1a2ak向前搜索符串仅对归约项目A, a有意义；归约项目A, a意味着：当它所属的状态呈现在栈顶且后续的k个输入符号为a1a2ak 时，才可以把栈顶上的归约为A只研究k1的情形定义：如上形式的项目称为一个LR(k)项目。说明：LR(1)项目 重新定义项目，让它带上搜索符(向前看符号)，成为如下形式 LR(1)项目: 由LR(0)项目和一个lookahead符号组成 A., a 对于项目 A, a ，搜索符a表示只有当下一个输入符号是a时，才能进行归约。 这样的a的集合一定是FOLLOW(A)

37、的一个子集，可能是真子集。 LR(1)项目A, a对可行前缀有效，如果存在着推导S *rm Aw rm w，其中：1. = ，且2. a是w的第一个符号，或者w为且a是$。考虑文法：S BBB aB | b从最右推导S *rm aaBab rm aaaBab看出：Ba B, a对可行前缀 = aaa是有效的；从最右推导S *rm BaB rm BaaB看出：Ba B, $对可行前缀 = Baa是有效的。这个文法生成的语言是什么？a*ba*b构造有效的LR(1)项目集 考虑对可行前缀有效的项目A B, a，必定存在最右推导S *rm Aax rm Bax，其中 = 。 假设ax能推出by，那么，

38、 B , b对有效，b是从 能推出的第一个终结符，或当 可空时，b就是a。bFIRST(a)。LR(1)项目集的构造输入：拓广文法G。输出： LR(1)项目集规范族，是对G 的一个或多个可行前缀有效的项目集。方法：如图319所示。function closure(I)begin repeat for I中的每个 A B, a for G中的每个产生式 B for FIRST(a)的每个终结符 b if B. , b 不在 I 中 do 把 B , b 加入 I until 在一次重复中没有项目加入 I return Iend构造项目集function goto(I, X)begin 置置J为空

39、集为空集; for (I中的每个项目中的每个项目 A X, a ) 把项目把项目 A X , a 加入到加入到J中中 return closure(J)endgoto函数procedure items(G )begin C := closure(S S, $); repeat for C 每个项目集 I for 每个文法符号 X if goto(I, X) 非空且不在C 中 把goto(I, X) 加入到 C中 until 在一次重复中没有项目集加入到 C中end主例程计算S.S,$的闭包I0：S.S, $ S.CC, $ C.cC, c/d C.d, c/d 构造文法S S S C CC c

40、 C | d的LR(1)和SLR分析表。c/d FIRST(C$)SC.C,$C.cC,$C.d,$ I2CS.S,$S.CC,$C.cC,c/dC.d,c/d I0SS.,$ I1SCc.C, c/dC.cC, c/dC.d, c/d I3cCd.,c/d I4dSCC.,$ I5CCc.C,$C.cC,$C.d,$ I6CcC.,$ I9CcCd.,$ I7dcCcC.,c/d I8Ccdd$acc规范LR(1)语法分析表的构造输入：拓广文法G。输出：文法G的规范LR语法分析表函数action和goto。方法：1. 构造G 的LR(1)项目集规范族C=I0, I1, , In。2. 从Ii

41、构造分析器的状态i，状态i的action函数确定如下： 若A a, b在Ii中，且goto(Ii, a) = Ij，则置actioni, a为“shift j”； 若A , a在Ii中，且A S，则置actioni, a为“reduce j”，j是产生式A 的序号；若SS, $在Ii中，则置actioni, $为“accept”。规范LR(1)语法分析表的构造3. 状态i的goto函数确定如下：若goto(Ii, A) = Ij，则gotoi, A = j4. 用上面规则未能定义的所有条目都置为error。5. 语法分析器的初始状态是包含SS, $的项目集对应的状态。LR(1)分析表 每个SL

42、R(1)文法都是LR(1)文法。 有的文法是LR(1)但不是SLR(1)的。 LR(1)语法分析器的状态数目比SLR(1)分析器的状态数目多。5/7/66 一个非LR(1)的文法如下：L - MLb | aM - 给出所有有移进-规约冲突的规范LR(1)项目集1025/7/67 拓广文法：L - LL - MLb | aM - I0103I0L - L, $L - MLb, $L - a, $M - , a5/7/68104I0L - L, $L - MLb, $L - a, $M - , aI1L - L , $LI2L - M Lb, $L - MLb, bL - a, bM - , aM

43、I3L - a , $aI4L - M L b, $LI5L - M Lb, bL - MLb, bL - a, bM - , aMI6L - a , baI7L - M L b , $bI8L - ML b, baLMI9L - ML b , bbS L = RS R L * RL id R L I0 : S S， $S L = R, $S R, $L * R, =L id, =R L, $I2 : S L = R, $R L , $L 构造文法的LR(1)分析表不存在移进归约冲突SSI0S S， $S L = R, $S R, $L * R, =L id, = R L, $I6S L =

44、R, $R L, $L * R, $L id, $=I7L *R , =R I8R L , =L * S I1 SS., $ I2S L = R, $R L , $L I3S R , $R I4L * R, =R L, =L * R, =L id, =* I5L id , =id id I9S L= R, $R L I10R L , $I12L id , $id I11L * R, $R L, $L * R, $L id, $* * I13L *R , $R id L 5、LALR分析表的构造问题：问题：对于一般的语言，规范LR分析表要用几千个状态，无法实际应用分析：分析：由例6中可以看到，有

45、些状态集除了搜索符不同外是两两相同的解决办法：解决办法：合并同心集，构造LALR分析表 我们称两个LR(1)项目集具有相同的心，如果除去搜索符之后，这两个集合是相同的。将所有同心的LR(1)项目集合并后，得到一个心就是一个LR(0)项目集。说明：合并同心集不会产生新的移进-归约冲突，但有可能产生新的“归约-归约”冲突。对于同一个文法，LALR分析表和SLR分析表永远具有相同数目的状态，却能处理一些SLR所不能对付的事情。合并项目集时不用修改转换函数，即GOTO(I,X)；动作ACTION应进行修改，使得能够反映各被合并的集合的既定动作。A、构造LALR分析表的第一个算法步骤：构造文法G的LR(

46、1)项目集族C=I0,I1,In把所有的同心集合并在一起，记C=J0,J1,Jm为合并后的新族。那个含有项目SS,$的Jk为分析表的初态从C构造ACTION表构造GOTO表分析表中凡不能用3、4填入信息的空白格均填上“出错标志” a、若项目、若项目Aa,b属于属于Jk且且GO(Jk,a) Jj，a为终结符，则置为终结符，则置ACTIONk，a为为 “sj”； b、若项目、若项目A,a属于属于Jk，则置，则置ACTIONk，a为为“用产生式用产生式A归约归约”，简记为，简记为“rj”；其中，假定；其中，假定A为文法为文法G的第的第j个产个产生式；生式； c、若项目、若项目SS,$属于属于Jk，则

47、置，则置ACTIONk，为为“接受接受”，简，简记为记为“acc”；从C构造ACTION表 例7 拓广文法 的LALR分析表 (0)SS(2) BaB (1) SBB(3) Bb把状态3，6、4，7和8，9分别合并成I36: BaB,a /b/$BaB,a /b/$Bb,a /b/$I47: Bb,a /b/$I89:BaB,a /b/$由合并后的集族所构成的LALR分析表状态ACTION(动作)GOTO(转换)ab$SB0s36s47121acc2s36s47536s36r478947r3r3r35r189r2r2r2B、构造LALR分析表的另一算法问题：问题：对任何文法G，通过构造它的LR

48、(1)项目集，合并同心集，最后形成LALR(1)项目集 ，该算法太费存储空间。解决办法：解决办法：注意到各种项目集都是以一定项目为核的闭包。若用核代替闭包，则不论哪一种项目集都将大大缩小它的存储空间 相关定义使用核构造分析表 任何项目集的核是由此集中所有那些圆点不在最左端的项目组成的。初态项目集的核含有（而且只含有）项目SS,$ 通过核构造GOTO表：若GO(I,X)=J，I的核为K，J的核为L。显然，若A- X,a属于K，则A- X,aA- X,a属于L。 对每对非终结符C和A都预先计算出它们是否有关系:C A 通过核构造ACTION表：令I是一个项目集，K是它的核。若ACTIONI,a为用

49、“A归约”。那么，若，则项目 A必属于K；若=，则K中必有某个项目BC,b，其中C A，且a属于FIRST（b）。为每个LR(0)集核的每个项目都配上一个搜索符集，使得这个核成为一个LALR(1)集的核SPONSOR算法LR(0)初态集核的唯一项目 SS 具有搜索符$；应用SPONSOR算法从初态集核开始计算每个核各个项目的全部自生搜索符。 LALR(1)项目集（核）的构造算法利用三元式(I,A ,a)栈来跟踪由前述算法产生的自生搜索符的传播；构造G的所有LR(0)集的核；从CLOSURE(SS,$)开始，利用SPONSOR算每个状态的核的自生搜索符；利用LALR(1)项目集核构造算法逐个进行

50、传播计算。 综上，构造拓广文法的LALR(1)项目集（核）的步骤如下： 例8 拓广文法的LALR(1)集核计算 (0)SS(2) SR(4) Li (1) SL=R (3) L*R (5) RL从初态开始：I0：CLOSURE SS,$ = SS,$ SL=R,$ SR,$ L*R,= Li,= RL,$ L*R,$ Li,$ 初态中具有搜索符初态中具有搜索符$的的 SS 进栈；进栈；即：即：( I0, SS, $ ) 入栈入栈由由SPONSOR算法：算法：=是是I4的的L*R和和I5的的Li, 的一个自生的一个自生搜 索 符 ， 将搜 索 符 ， 将 I4, L * R , = I5,Li,

51、= 入栈入栈I0：CLOSURE SS,$ = SS,$ SL=R,$ SR,$ L*R,= Li,= RL,$ L*R,$ Li,$ ( I0, SS, $ )( I4, L*R, = )( I5, Li, = )( I7, L*R, = )( I8, RL, = )( I2,SL=R, $ )( I3, SR, $ )( I2,RL, $ )( I4, L*R, $ )( I5, Li, $ )( I1, SS, $ )( I8,RL, $ )( I9, SL=R, $ )栈的变化状态( I6,SL=R, $ )I4：CLOSURE L*R, = = L*R, = RL,= L*R,= L

52、i,= I2：CLOSURE SL=R, $ = SL=R, $ I6：CLOSURE SL=R, $ = SL=R, $ RL,$ L*R,$ Li,$ I4：CLOSURE L*R, $ = L*R, $ RL,$ L*R,$ Li,$ ( I7, L*R, $ )I0: SS, $ I1：SS, $ I2：SL=R, $ RL, $I3： SR, $ I4：L*R, =/$ I5： Li, =/$I6：SL=R, $ I7： L*R, =/$I8：RL, =/$ I9：SL=R, $ 最终得到该文法的LALR(1)集核为： 直观算符优先分析法 1 定义: 任二个相继出现的终结符a与b(可

53、能中间有VN),可能有以下优先关系:a b a的优先性低于ba b a的优先性等于ba b a的优先性高于b文法G:E E + E | E * E | EE | ( E ) | i 的终结符的的终结符的优先关系见下表。优先关系见下表。 + * i （ ） $ + * i（ ） $优 先 表E E+E | E*E | EE |( E )| i3 使用如上分析表，构造分析算法（直观算符优先分析法）记号使用说明：$：语句括号（栈底 w后）：现行栈顶符 a：刚读入字符OPTR：运算符栈OPND：操作符栈aOPTROPND$E （1） E （2）E（3）=分析算法步骤：下一个输入符号读至a中；若a为i，

54、则aOPND，转第一步；若 a，则调用关于的处理程序（语义程序），处理子表达式 : E（1）E（2） ；然后重新进入第3步；（其中， E（1） 、E（2）分别为OPND栈的次栈顶和栈顶）)OPTROPND$(E （1） E （2）a$成功！成功！若 a，则 若=(,a=),则逐出OPTR栈顶的(,放弃a中的 ),转第 1步; 若=a=$,分析成功结束；若 a，aOPTR栈，转第1步；与a不存在优先关系，则输入串错误，调出错处理 由文法G: E E + E | E * E | EE | ( E ) | i的终结符的优先关系表及上述分析算法的终结符的优先关系表及上述分析算法分析算术表达式分析算术表

55、达式 i1 + i2 * i3 $ 的过程。的过程。OPTROPND分析过程 OPND栈为空， $ OPTR栈 i1OPND $ + ，+OPTR i2OPND$+i1i2i3*te输入串 :i1 + i2 * i3 $(3)+$ ， *弹出OPTR栈； i2 * i3 = t OPND + $ ， +弹出OPTR栈； t + i1 = e OPND $ =$ ， 分析成功； e 为整个表达式的结果a分析文法比较LR(1)LL(1)算法优先方法算法优先方法建立分析树的建立分析树的方法方法自下而上自下而上自上而下自上而下自下而上，仅得到分自下而上，仅得到分析树的骨架析树的骨架归约还是推导归约还是

56、推导规范归约规范归约最左推导最左推导不规范规约不规范规约使用产生式的使用产生式的时机时机看见产生式整个右部推看见产生式整个右部推出的内容后，决定用哪出的内容后，决定用哪个产生式进行归约个产生式进行归约看见产生右部推出的看见产生右部推出的第一个终结符便确定第一个终结符便确定用哪个产生式进行推用哪个产生式进行推导导看见产生式整个右部看见产生式整个右部推出的内容后才决定推出的内容后才决定用哪个产生式归约用哪个产生式归约对文法的限制对文法的限制对文法没有限制对文法没有限制无左递归，无公共左无左递归，无公共左因子因子必须是算符文法必须是算符文法分析表分析表状态状态文法符号文法符号 大大非终结符非终结符终

57、结符终结符 小小终结符终结符终结符终结符 小小分析栈比较分析栈比较状态栈状态栈文法符号栈文法符号栈终结符栈终结符栈确定句柄确定句柄根据栈顶状态和下一个根据栈顶状态和下一个符号确定句柄和归约用符号确定句柄和归约用的产生式的产生式无句柄概念无句柄概念在分析栈顶查找满足在分析栈顶查找满足符号序列符号序列已知规则，如何解决问题本质本质自下而上自下而上自上而下自上而下数据结构数据结构(直观直观)栈栈树树算法思路算法思路局部优先局部优先递归递归语法分析方法语法分析方法LR(1)LL(1)分析核心分析核心状态转换（动作）表状态转换（动作）表预测分析表预测分析表参考资料陈火旺，程序设计语言编译原理（第三版）,

58、国防工业出版社，冯博琴译，现代编译程序设计，邮电出版社，Kenneth C. Louden,冯博琴 等译，编译原理与实践，机械工业出版社例3.20 判断下述文法GS是哪类LR文法。GS: (1) SL=R(2) SR(3) L*R(4) Li(5) RL131解答 首先将文法GS拓广为GS：GS:(0) SS(1) SL=R(2) SR(3) L*R(4) Li(5) RL132构造文法GS的LR(0)项目集规范族如下： I0: SS I2: SL=R I5: SRSL=R RL I6: SL=RSR I3: L*R RLL*R RL L*RLi L*R LiRL Li I7: SL=RI1:

59、 SS I4: Li I8: L*RGS(0) SS (1) SL=R (2) SR (3) L*R (4) Li (5) RL我们知道，如果每个项目集中不存在既含移进项目又含归约项目或者含有多个归约项目的情况，则该文法是一个LR(0)文法。检查上面的项目集规范族，发现I2存在既含移进项目SL=R又含归约项目RL的情况，故文法GS不是LR(0)文法。假定LR(0)规范族的一个项目集I中含有m个移进项目，即A1a11, A2a22, , Amamm同时I中含有n个归约项目，即B1, B2, , Bn如果集合a1,am、FOLLOW(B1)、FOLLOW(Bn)任何两个出现相交的情况(包括存在两个

60、FOLLOW集含有“$”)，则该文法不是SLR(1)文法。134因此，构造文法GS的FOLLOW集如下：(1) FOLLOW(S)=$；(2)由SL= 得FIRST(=) FOLLOW(L),即FOLLOW(L)=；(3) 由SS得FOLLOW(S) FOLLOW(S)，即FOLLOW(S)=$；由SR得FOLLOW(S) FOLLOW(R)，即FOLLOW(R)=$；由LR得FOLLOW(L) FOLLOW(R)，即FOLLOW(R)=,$；由RL得FOLLOW(R) FOLLOW(L)，即FOLLOW(L)=,$。135由I2的移进项目SL=R和归约项目RL得 =FOLLOW(L)=,$=