LR分析法.ppt

LRLR分析法分析法含义：含义：L—L—自左向右处理输入串；自左向右处理输入串；R—R—最右推导的逆过程最右推导的逆过程；；n LRLR分析法的基本思想：规范归约过程中，记住分析法的基本思想：规范归约过程中，记住““历史历史””，对未来，对未来 “ “展望展望””，结合，结合““现实现实””n LRLR分析器分析器——一个带栈的一个带栈的DFADFA即：将即：将““历史历史””和和 “ “展望展望””材料综合地抽象为某些材料综合地抽象为某些““状态状态””任何时候，栈顶的状任何时候，栈顶的状态都代表了整个历史和已推测出的展望态都代表了整个历史和已推测出的展望nLRLR分析器的每一步工作都是由分析器的每一步工作都是由栈顶状态栈顶状态和和现行输入符号现行输入符号所所唯一唯一确定；确定；nP100 LRP100 LR分析器模型分析器模型nLRLR分析器的工作过程分析器的工作过程 P100~101P100~101（（三元式）三元式）nLRLR分析分析优点优点：大多数上下文无关文法描述的程序语言都：大多数上下文无关文法描述的程序语言都可用可用LRLR分析器识别，且比算符优先分析更广泛，效率也可分析器识别，且比算符优先分析更广泛，效率也可以。

以缺点：缺点：手工工作量大，要借助自动产生分析程序的工手工工作量大，要借助自动产生分析程序的工具LRLR分析法分析法根据构造分析表的具体方法的不同：根据构造分析表的具体方法的不同：nLRLR(1)(1)分析表分析表：自左向右处理输入；：自左向右处理输入；R R表示生成了最表示生成了最右推导；右推导；1 1表示先行表示先行1 1个符号nLRLR（（0 0））分析表分析表：：先行符号出现在分析栈顶之后再检先行符号出现在分析栈顶之后再检查它查它, ,不算作先行不算作先行nSLR(1)SLR(1) 分析表分析表：对：对LRLR（（1 1））的改进nLALRLALR（（1 1））分析表分析表：比：比SLRSLR（（1 1））强，比强，比LRLR（（1 1））简单LRLR分析法分类分析法分类LRLR分析表分析表 状态状态 ACTION GOTO a ( ) # E L 0 S3 S2 1 1 acc 2 S3 S2 5 4 3 r2 r2 r2 r2 4 S6 5 S3 S2 r4 5 7 6 r1 r1 r1 r1 7 r3 r3 r3 r3LRLR分析法的分析过程分析法的分析过程状状态态ACTION（（动作）动作）GOTO（（转换）转换）i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5状态状态符号栈符号栈输入串输入串1 10#i1 * i2 + i3 #2 205# i1 * i2 + i3 #3 303# F * i2 + i3 #4 402# T* i2 + i3 #5 5027# T * i2 +i3 #6 60275# T * i2 +i3 #7 702710# T * F +i3 #8 802# T+ i3 #9 901# E+ i3 #1010016# E +i3 #11110165# E + i3#12120163# E + F#13130169# E + T#141401# E#例子：例子：利用利用P101的的LR分析表分析输入串分析表分析输入串i 1* i 2+i3ETi3F+ETF*Ti1i2FLR文法文法定义：定义：对于一个文法，如果能构造一张分析表，对于一个文法，如果能构造一张分析表，使得它的每个入口均是唯一确定的，就称该文使得它的每个入口均是唯一确定的，就称该文法为法为LR文法文法。

特点：特点：对于一个对于一个LR文法，当分析器对输入串进文法，当分析器对输入串进行自左至右扫描时，一旦句柄呈现于栈顶，就行自左至右扫描时，一旦句柄呈现于栈顶，就能及时对其进行规约能及时对其进行规约LR（（k））文法定义：文法定义：对于一个对于一个LR文法，如果能文法，如果能用一个每步顶多向前检查用一个每步顶多向前检查k个输入符号的个输入符号的LR 分分析器进行分析，就称该文法为析器进行分析，就称该文法为LR（（k））文法文法多数程序设计语言，多数程序设计语言，k=0或或1就足够了就足够了活前缀活前缀字的前缀：字的前缀：该字的任意首部该字的任意首部活前缀：活前缀：规范句型的一个前缀，它不含句柄之规范句型的一个前缀，它不含句柄之后的任意符号在活前缀右边添加一些终结后的任意符号在活前缀右边添加一些终结符后就成为一个规范句型了符后就成为一个规范句型了 在在LR分析工作过程中的任意时候，栈里的文法符号分析工作过程中的任意时候，栈里的文法符号（自栈底而上）（自栈底而上）X1X2…Xm应该构成活前缀，把输入串的应该构成活前缀，把输入串的剩余部分配上之后构成规范句型剩余部分配上之后构成规范句型。

只要输入串的已扫描部分保持可归约成一个活前缀，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描的部分没有错那就意味着所扫描的部分没有错 只要知道文法，就能构造出可以识别该文法所有活只要知道文法，就能构造出可以识别该文法所有活前缀的前缀的NFALR（（0））项目项目LR（（0））项目项目——文法文法G的每一个产生式的右部的每一个产生式的右部添加一个圆点称为添加一个圆点称为G的一个的一个LR（（0））项目 一个项目指明了在分析过程的某个时刻我们看到的一个项目指明了在分析过程的某个时刻我们看到的产生式的多大一部分产生式的多大一部分例如：例如：文法文法5.7的的所有所有LR（（0））项目为：项目为：文法：S’ →E E → aA |bB A → cA |d B → cB |d⑴ ⑴ S’ →.E ⑵ ⑵ S’ →E . . ⑶ ⑶ E →. aA ⑷ ⑷ E → a.A ⑸ ⑸ E → aA . ⑹ ⑹ A → . cA ⑺ ⑺ A → c.A ⑻ ⑻ A → cA . ⑼ ⑼ A →. d ⑽ ⑽ A → d. ⑾ E⑾ E → .bB ⑿ E⑿ E → b. B ⒀ E⒀ E → b B. 1414））B →. cB 1515））B → c.B 1616））B → cB. 1717））B →. d 18 18））B → d. LR（（0））项目的分类项目的分类1、归约项目：、归约项目： A →   .例如：例如：5、、8、、10、、18等等2、接收项目：、接收项目： S’ →   .例如：例如： 23、移进项目：、移进项目： A →   . a 例如：例如：3、、11、、14 、、 64、待约项目：、待约项目： A →   . B 例如：例如：4、、12、、15⑴ ⑴ S’ →.E ⑵ ⑵ S’ →E . . ⑶ ⑶ E →. aA ⑷ ⑷ E → a. A ⑸ ⑸ E → aA . ⑹ ⑹ A → . cA ⑺ ⑺ A → c.A ⑻ ⑻ A → cA . ⑼ ⑼ A →. d ⑽ ⑽ A → d. ⑾ E⑾ E → .bB ⑿ E⑿ E → b. B ⒀ E⒀ E → b B. 1414））B →. cB 1515））B → c.B 1616））B → cB. 1717））B →. d 18 18））B → d.  对于一个文法，我们可以把其所有项对于一个文法，我们可以把其所有项目表示的状态构造为一个目表示的状态构造为一个NFA，，该该NFA用用来识别该文法所有的来识别该文法所有的活前缀。

活前缀 用词法分析中采用的用词法分析中采用的子集法子集法可以将可以将NFA确定化确定化DFA，，该该DFA的每个状态是一的每个状态是一个个项目集合，项目集合，这些集合的全体就构成了该这些集合的全体就构成了该文法的文法的LR（（0））项目集规范族项目集规范族LR分析表的构造分析表的构造文法文法拓广文法拓广文法LR（（0））项目项目NFADFAI={S’ →.E }构造构造GO（（I，，X））=CLOSURE（（J））LR（（0））项目集项目集规范族规范族由由具体的算法具体的算法得到最终的得到最终的某种某种LR分析表分析表1、拓广：、拓广：为了使为了使“接受接受”状态易于识别，总把文法状态易于识别，总把文法G进进行拓广目的是不让文法的开始符号出现在产生式的右边目的是不让文法的开始符号出现在产生式的右边拓广的方法拓广的方法：引入文法中没有的非终结符：引入文法中没有的非终结符S’，，加入加入 S’ →S （（1）拓广）拓广（（2）根据）根据LR（（0））项目画项目画NFAijXi X→ X1 1X2 2 … … Xi-1 i-1 Xi i …… Xn n X→ X1 1X2 2 … … Xi-1 i-1 Xi i …… Xn nij X →   A 从从 画画 弧到所有弧到所有 A →  状态状态ii规定规定““⑴ ⑴ S’ →.E”为唯一初态为唯一初态最终得到文法最终得到文法5.6的的NFA图图 P106⑴ ⑴ S’ →.E ⑵ ⑵ S’ →E . . ⑶ ⑶ E →. aA ⑷ ⑷ E → a.A ⑸ ⑸ E → aA . ⑹ ⑹ A → . cA ⑺ ⑺ A → c.A ⑻ ⑻ A → cA . ⑼ ⑼ A →. d ⑽ ⑽ A → d. ⑾ E⑾ E → .bB ⑿ E⑿ E → b.B ⒀ E⒀ E → b B. 1414））B →. cB 1515））B → c.B 1616））B → cB. 1717））B →. d 18 18））B → d . 13 11 2E5A12b4a13B14 17 6 9 ⑴ ⑴ S’ →.E ⑵ ⑵ S’ →E . . ⑶ ⑶ E →. aA ⑷ ⑷ E → a.A ⑸ ⑸ E → aA . ⑹ ⑹ A → . cA ⑺ ⑺ A → c.A ⑻ ⑻ A → cA . ⑼ ⑼ A →. d ⑽ ⑽ A → d. ⑾ E⑾ E → .bB ⑿ E⑿ E → b. B ⒀ E⒀ E → b B. 1414））B →. cB 1515））B → c.B 1616））B → cB. 1717））B →. d 18 18））B → d. NFADFA由由子集法得到该子集法得到该NFA所对应的所对应的DFAI0IEIAIBIaIbIcId{1,3,11}{2}//{4,6,9}{12,14,17}//…//………………//..……………//..…………结果为结果为P106图图5.7（（3））d0:8:10:c3:1:2:aEb4:6:cAd5:9:11:7:ccddBB能识别文法能识别文法5.7前缀的前缀的DFA P106图图5.7A(0) S’ →E(1) E → aA (2) E → bB(3) A → cA (4) A → d(5) B → cB (6) B → d项目集规范族项目集规范族C={I0,I1,I2 …I10,I11}（（4）构造）构造LR（（0））分析表分析表构造构造LR（（0））分析表的算法分析表的算法P109项目集规范族项目集规范族C={I0,I1,I2 … ,In}（（1））Sj （（4））j（（2）） rj （（5））报错报错（（3））acc（（0）） S’ → E （（1）） E → aA （（2）） E → Bb（（3）） A → cA （（4）） A → d （（5））B → cB （（6）） B → d 状状态态ACTION（（动作）动作）GOTOabcd#EAB01234567891011d0:8:10:c3:1:2:aEb4:6:cAd5:9:11:7:ccddBBA状状态态ACTION（（动作）动作）GOTOabcd#EAB0s2s311acc2s4s1063s5s1174s4s1085s5s1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6P109 LR（（0））分析表分析表状态状态符号栈符号栈输入串输入串ACTIONGOTO1 10#bccd #s32 2035# bccd #s53 3035# bc cd #s54 40355# bccd #s115 5035511# bccd d #r696 603559# bccB #r597 70359# bcB #r578 8037# bB #r519 901# E#acc例子：例子：利用利用P109的的LR（（0））分析表分析表 分析输入串分析输入串bccd文法文法拓广文法拓广文法LR（（0））项目项目NFADFAI={S’ →.E }构造构造GO（（I，，X））=CLOSURE（（J））LR（（0））项目集项目集规范族规范族由由具体的算法具体的算法得到最终的得到最终的某种某种LR分析表分析表LR分析表的构造分析表的构造LR（（0））项目集规范族的构造项目集规范族的构造LR（（0））项目集规范族的构造方法项目集规范族的构造方法（类比（类比P50））对文法对文法G的每一个项目集的每一个项目集I构造其构造其CLOSURE（（I））（（1））I的任何项目都属于的任何项目都属于CLOSURE（（I））（（2）若）若A →   . B 属于属于CLOSURE（（I），），那么，对于任那么，对于任何关于何关于B的产生式的产生式B → ，，项目项目B →.  也也属于属于CLOSURE（（I）。

3））反复执行上述反复执行上述2步直到步直到CLOSURE（（I））不再增加不再增加例子：例子：I={S’ →.E }对文法对文法G的每一个项目集的每一个项目集I构造其构造其CLOSURE（（I））（（1））I的任何项目都属于的任何项目都属于CLOSURE（（I））（（2）若）若A →   . B 属于属于CLOSURE（（I），），那么，对于任那么，对于任何关于何关于B的产生式的产生式B → ，，项目项目B →.  也也属于属于CLOSURE（（I）CLOSURE（（I））={S’ →.E，，E →. aA E →. bB}=I0• 以以I0为开始，逐步构造为开始，逐步构造GO（（I，，X））= CLOSURE（（J））文法符号文法符号状态集状态集J={任何形如任何形如A →   X .  的项目的项目| A →   .X 属于属于I}例：例：GO（（I0，，a））={E →a.A}先先考察考察I0中圆点之后跟着中圆点之后跟着a的项目，然后将圆点后移一个文法符号的项目，然后将圆点后移一个文法符号CLOSURE（（ ））={E →a.A,A→.cA,A→.d}d0:8:10:c3:1:2:aEb4:6:cAd5:9:11:7:ccddBBA由由GOGO（（I I，，X X））得到文法的得到文法的LRLR（（0 0））项目集规范族项目集规范族C={IC={I0 0，，I I1,1,I I2,2,I I3 3 … , ,I I1111} }GO（（I2 ,c））=I4GO（（I2 ,A））=I6GO（（I2 ,d））=I10I={ S’ →.E } CLOSURE（（I））=I0GO（（I0 ,E））=I1GO（（I0 ,a））=I2GO（（I0 ,b））=I3GO（（I3 ,c））=I5GO（（I3 ,B））=I7GO（（I3 ,d））=I9…………0:8:9:11:4:c2:ac5:cc6:A1:Ed3:bd10:ddB7:B构造构造 LR（（0））分析表的算法：分析表的算法：P109前提：前提：项目集规范族项目集规范族C={I0，，I1，，,I2，，,I3 … ,In}，含，含S’ →S的项目集为初态的项目集为初态 （（1）若）若项目项目A →   . a 属于属于Ik且且GO（（ Ik ,a））= Ij a为终结为终结符符，，则置则置ACTION[k,a]=sj ,表示把状态表示把状态(j,a)移进栈移进栈;（（2）若）若项目项目A →   . 属于属于Ik则对任何终结符则对任何终结符a(包括包括#)置置ACTION[k,a]=rj,表示用第表示用第j个产生式个产生式A →   进行归约进行归约;（（3）若）若项目项目S’ →S . 则置则置ACTION[k,#]= acc,表示表示“接受接受”;（（4）若）若GO（（ Ik ,A））= Ij ,A为非终结符，为非终结符，则置则置GOTO[k,A]=j;（（5））分析表中凡不能用分析表中凡不能用1至至4填入信息的空白个均置上填入信息的空白个均置上“报错报错”(通常我们就空在那里通常我们就空在那里)状状态态ACTION（（动作）动作）GOTOabcd#EAB0s2s311acc2s4s1063s5s1174s4s1085s5s1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6P109 LR（（0））分析表分析表作业：作业：P134 5 文法文法：： S → AS| b A → SA|a2、、LR（（0））项目：项目：1 1）） S’ → .S 2 2）） S’ → S. 3 3）） S → . AS 4 4）） S → A . S 5 5）） S → AS . 6 6）） S→ .b 7 7））S S → b . 8 8）） A → . SA9 9）） A → S . A 1010）） A → SA . 11）） A →. a 12）） A → a .1、拓广：、拓广： （（0）） S’ → S （（1）） S → AS （（2）） S → b （（3）） A → SA （（4）） A → aLR（（0））项目项目NFADFALR（（0））项目集项目集规范族规范族IISIAIaIb{1,3,6,8,11}{2,3,6,8,9,11}{3,4,6,8,11}{12}{7}{2,3,6,8,9,11}{3,6,8,9,11}{3,4,6,8,10,11}{12}{7}{3,4,6,8,11}{3,5,6,8,9,11}{3,4,6,8,11}{12}{7}{3, 6,8,9,11}{3, 6,8,9,11}{3,4,6,8,10,11}{12}{7}{3,4,6,8,10,11} {3,5,6,8,9,11}{3,4,6,8,11}{12}{7}{3,5,6,8,9,11}{3,6,8,9,11}{3,4,6,8,10,11}{12}{7}{12}////{7}////1 1）） S’ → .S 2 2）） S’ → S. 3 3）） S → . AS 4 4）） S → A . S 5 5）） S → AS . 6 6）） S→ .b 7 7））S S → b . 8 8）） A → . SA9 9）） A → S . A 1010）） A → SA . 11）） A →. a 12）） A → a .ISAab0126713467252673346745267534676////7////重命名后：重命名后：I0 = {1,3,6,8,11}I1 = {2,3,6,8,9,11}I2 = {3,4,6,8,11} I3 = {3, 6,8,9,11}I4 = {3,4,6,8,10,11}I5 = {3,5,6,8,9,11} I6 = {12}I7 = {7}3、用、用CLOSURE（（I））求出求出LR（（0））项目集规范族项目集规范族CCLOSURE（（{S’→.S}））={S’→ .S，，S →. AS，，S→.b，， A→. SA，， A→. a} =I0GO（（I0 ,S））= CLOSURE（（{S’→S. ，，A→ S. A}）） = {S’→S. ，， A→ S. A，， A→. SA，， A→. a，，S →. AS，，S→.b} = I1GO（（I0 ,A））= CLOSURE（（{S →A. S}）） = {S →A. S，，S →. AS，，S→.b，， A→. SA，， A→. a}= I2GO（（I0 ,a））= CLOSURE（（{A→ a . }））= {A → a . } = I3 （（归约项）归约项）GO（（I0 ,b））= CLOSURE（（{S→b.}））= {S → b.}= I4 （（归约项）归约项）GO（（I1 ,S））= CLOSURE（（{A→S. A}）） = {A→S. A ，，A→.SA，， A→. a，， S→.AS，，S→.b}= I5 GO（（I1 , A））= CLOSURE（（{A→ SA . , S →A.S}）） = {A→ SA . , S →A .S, A→. SA，， S →. AS，，S→.b, A→. a}= I6 GO（（I1 ,a））= CLOSURE（（ {A→ a . } ））= I3 （（归约项）归约项）GO（（I1 ,b））= CLOSURE（（ {S→b.} ））= I4 （（归约项）归约项）GO（（I2 ,S））= CLOSURE（（{S → AS.，， A→ S. A}）） = {S → AS.，， A→ S.A，， A→. SA，， A→. a，， S →. AS，，S→.b}= I7GO（（I2 , A））= CLOSURE({S →A .S} )=I2 GO(I2 , a)= I3 GO(I2 ,b)= I4GO（（I5 , A））= CLOSURE（（{S →A .S，， A→ SA .}）） = I7 GO（（I5 , S））= CLOSURE（（{A→ S . A }））= I5 GO（（I5 ,a））= I3 GO（（I5 ,b））= I4 GO（（I6 ,S））= CLOSURE（（{S →AS. , A→S. A}））= I7 GO（（I6 ,A））= CLOSURE（（{S →A .S}））= I2 GO（（I6 ,a））= I3 GO（（I6 ,b））= I4 GO（（I7 ,A））= CLOSURE（（{S →A .S, A→ SA .}））= I6GO（（I7 ,S））= CLOSURE（（{A→S. A}）） = I5GO（（I7 ,a））= I3 GO（（I7 ,b））= I4 LR（（0））项目集规范族项目集规范族C:C={I0 , I1 , I2 , I3 , I4 , I5 , I6 , I7 }，，其中其中I0 ={S’→ .S，，S →. AS，，S→.b，， A→. SA，， A→. a}I1 = {S’→S. ，， A→ S. A，， A→. SA，， A→. a，，S →. AS，，S→.b}I2 = {S →A . S，，S →. AS，，S→.b，， A→. SA，， A→. a}I3 = {A → a . } （（归约项）归约项）I4 = {S → b . } （（归约项）归约项）I5 = {A→ S.A , A→. SA，， A→.a , S →. AS，，S→.b ，，}I6 = {A→ SA . , S →A .S, A→. SA，， S →. AS，，S→.b}I7 = {S → AS.，， A→ S.A，， A→. SA，， A→. a，， S →. AS，，S→.b}所以，不存在冲突，是所以，不存在冲突，是LR（（0））文法。

文法LR（（0））文法定义：文法定义：如果如果DFA中的每个状态不存在中的每个状态不存在（（1）即含移进项目又含归约项目；）即含移进项目又含归约项目；（（2）或者含有多个归约项目，）或者含有多个归约项目，就称该文法为就称该文法为LR（（0））文法LR（（0））项目项目规范族规范族中中的每个项目集不包含任何冲的每个项目集不包含任何冲突项目LR（（0））文法定义文法定义 对于对于LR（（0））文法，可直接根据其文法，可直接根据其项目集规范族项目集规范族和活和活前缀识别自动机的前缀识别自动机的状态转换函数状态转换函数构造出构造出LR（（0））分析表例子：见例子：见P107~109v构造构造LR（（0））分析表的算法分析表的算法P109项目集规范族项目集规范族C={I1,I2,I3 … ,In}（（1））Sj （（2）） rj （（3））acc（（4））j（（5））报错报错文法文法I={S’→.E}GO（（I，，X））CLOSURE（（J））LR（（0））项目集项目集规范族规范族LR（（0））项目项目拓广拓广文法文法LR（（0））分析表分析表v由由I={S’ →.E}开始求得开始求得CLOSURE（（I））=I0对文法对文法G的每一个项目集的每一个项目集I构造其构造其CLOSURE（（I））（（1））I的任何项目都属于的任何项目都属于CLOSURE（（I））（（2）若）若A →  .B 属于属于CLOSURE（（I），），则对任何关于则对任何关于B的的项目项目B →.  也也属于属于CLOSURE（（I）。

v由由GO（（I，，X））得到文法的得到文法的LR（（0））项目集规范族项目集规范族C={I0 , I1,I2,I3 … ,I11}练习练习:求拓广文法求拓广文法G的的LR（（0））项目集规范族项目集规范族C (P111)（（0）） S’ → E （（1）） E → E+T （（2）） E →T（（3）） T → T * F （（4）） T → F（（5）） F → (E) （（6）） F → iCLOSURE(I)={S’→.E, ,E→.E+T,E →.T,T →.T * F ,F→.(E) ,F →. i, T → . F}=I0GO(I0 , E)=CLOSURE({S’→E. , ,E→E . +T}) = {S’→E. , ,E→E . +T} = I1GO(I0 , T)=CLOSURE({E →T .,T →T . * F }) = {E →T .,T →T . * F } = I2GO(I0 , F)=CLOSURE({T → F . }) = {T → F . }= I3GO(I0 , ( )=CLOSURE({F→ (. E) }) ={F→ (. E) , ,E→.E+T,E →.T,T →.T * F , T →.F,F→.(E) ,F →. i}= I4GO(I0 , i)=CLOSURE({F → i .}) = {F → i .}= I5 开始：开始：I={ S’ →.E } 存在的问题存在的问题I1 = {S’→E. , , E→E . +T}I2 = {E →T . , , T →T . * F }I9 = {E→E+T . , , T →T .* F}归约项归约项移进项移进项“移进移进--归约归约”冲突冲突SLR（（1））解决办法解决办法v冲突冲突 ：：I={X →   .b ，，A →   . ，，B →   .} 归约项归约项归约项归约项移进项移进项例如：例如：I1 = {S’→E . , , E→E . +T}，，I2 = {E →T . , , T →T . * F }v推广到一般情况：一个推广到一般情况：一个LR（（0））项目集项目集I：：{移进项：移进项： A1→   .a1 1，，A2→   .a2 2 ，，… ，，Am→   .am m ，， 归约项：归约项： B1 →   . ，，B2 →   . ，，… ，，Bn →   . } v解决解决——SLR（（1））解决办法：解决办法：（（1））{a1，， a2 … ，， am} （（2）） FOLLOW（（Bi））是否两两不相交是否两两不相交检查现行输入符号检查现行输入符号a与上述与上述n+1个集合：个集合：1）若）若a=ai，则，则移进；移进；2）若）若a 属于属于FOLLOW（（Bi），则用），则用Bi→  归约；归约；(P111) 例子例子5.11:（（0）） S’ → E （（1）） E → E+T （（2）） E →T（（3）） T → T * F （（4）） T → F（（5）） F → (E) （（6）） F → i因为：对于因为：对于I2 = {E →T .,T →T . * F }E →T .是是归约项，且归约项，且FOLLOW（（E））={#，），，），+}所以：所以：当状态当状态I2面临输入符号为面临输入符号为#，），）或或+时，应用时，应用产生式产生式E →T归约，当面临输入符号为归约，当面临输入符号为*时，则时，则移进移进。

构造构造SLR分析表分析表v对于任何一个文法对于任何一个文法G，，用如下办法构造其用如下办法构造其SLR（（1））分析表分析表文法文法GO（（I，，X））CLOSURE（（J））LR（（0））项目集项目集规范族规范族拓广拓广文法文法 SLR（（1））分析表分析表冲突可用冲突可用SLR（（1））方法解决方法解决是否存在是否存在冲突冲突（（1））sj ,表示把状态表示把状态(j,a)移进栈移进栈;（（2）若项目）若项目A→   . 属于属于Ik，，对任何终结符对任何终结符a  FOLLOW（（A），），置置ACTION[k,a]=rj,表示用第表示用第j个产生式个产生式A→  归约归约;（注意：在（注意：在LR（（0））分析表中是分析表中是对任何终结符对任何终结符a(包括包括#)置置Ik 行均为行均为rj, ））（（3）若）若项目项目S’ →S . 则置则置ACTION[k,#]= acc,表示表示“接受接受”;（（4）若）若GO（（ Ik ,A））= Ij ,A为非终结符，为非终结符，则置则置GOTO[k,A]=j;（（5）） “报错报错”例子：构造文法例子：构造文法5.8的的SLR（（1））分析表分析表P101图图5.5P112 图图5.8 识别活前缀的识别活前缀的自动机自动机状状态态ACTION（（动作）动作）GOTO（（转换）转换）i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5I1 = {S’→E. , , E→E . +T}I2 = {E →T . , , T →T . * F }I9 = {E→E+T . , , T →T .* F}FOLLOW（（T））FOLLOW（（F））FOLLOW（（E））vSLR（（1））文法文法——具有具有SLR（（1））分析表的文法；数字分析表的文法；数字1的含义是，在分析过程中，顶多只要向前看一个符号。

的含义是，在分析过程中，顶多只要向前看一个符号v 使用使用SLR（（1））分析表的分析器叫分析表的分析器叫SLR分析器v 每个每个SLR（（1））文法都是无二义的，但无二义的文法不一定文法都是无二义的，但无二义的文法不一定就是就是SLR（（1））文法文法;SLR（（1））文法文法v如何判断一个文法是否为如何判断一个文法是否为SLR（（1））文法？文法？文法文法GO（（I，，X））CLOSURE（（J））LR（（0））项目集项目集规范族规范族拓广拓广文法文法冲突是否能冲突是否能用用SLR（（1））方法解决方法解决是否存在是否存在冲突冲突文法文法GO（（I，，X））CLOSURE（（J））LR（（0））项目集项目集规范族规范族拓广拓广文法文法冲突是否能冲突是否能用用SLR（（1））方法解决方法解决是否存在是否存在冲突冲突例子：判断文法例子：判断文法5.9是否为是否为SLR（（1））文法文法（P113图5.5）1、拓广：、拓广：（（0）） S’ → S （（1）） S → L=R （（2）） S → R （（3）） L → *R （（4）） L → i （（5）） R →L2、、 LR（（0））项目集规范族：图项目集规范族：图5.93、判断是否存在冲突：、判断是否存在冲突：因为：对于因为：对于I2 = {S → L . =R , R →L.} S → L . =R 是移进项是移进项，，R →L .是归约项，而是归约项，而FOLLOW（（R））={#，，=}所以：所以：当状态当状态I2面临输入符号为面临输入符号为=时，无法确定是用产生式时，无法确定是用产生式R →L. 归约，还是该归约，还是该移进移进=，因此该文法不是，因此该文法不是SLR（（1））文法文法。

例子：判断文法例子：判断文法G是否为是否为SLR（（1））文法文法? 并说明理由并说明理由文法文法G（（S）：）：S → BB B → aB|b2、、LR（（0））项目项目1 1）） S’ → .S 2 2）） S’ → S. 3 3）） S → .BB 4 4）） S → B.B 5 5）） S → BB . 6 6）） B → .aB 7 7）） B → a.B 8 8）） B → aB. 9 9）） B → .b 1010）） B → b .1、拓广：、拓广： （（0）） S’ → S （（1）） S → BB （（2）） B → aB （（3）） B → b3、用、用CLOSURE（（I））求出求出LR（（0））项目集规范族项目集规范族CCLOSURE（（{S’→.S}））={S’→ .S，，S→ .BB，，B→ .aB，，B→.b}=I0 GO（（I0 ,S））= CLOSURE（（{S’→S.}））= {S’→ S.}= I1 （（归约项）归约项）GO（（I0 ,B））= CLOSURE（（{S→B.B}））= {S→B.B，，B→.aB，，B→.b}= I2GO（（I0 ,a））= CLOSURE（（{B→a.B}））= {B→a.B ，，B→.aB，，B→.b}= I3GO（（I0 ,b））= CLOSURE（（{B→b.}））= {B→b.}= I4 （（归约项）归约项）GO（（I2 ,B））= CLOSURE（（{S→BB.}））= {S→BB.}= I5 （（归约项）归约项）GO（（I2 ,a））= CLOSURE（（{B→a.B}））= {B→a.B，，B→.aB，， B→.b}= I3GO（（I2 ,b））= CLOSURE（（ {B→b.}））= {B→b.}= I4 （（归约项）归约项）GO（（I3 ,B））= CLOSURE（（{B→aB.}））= I6 ；；GO（（I3 ,a））= I3 ；；GO（（I3 ,b））= I44、判断是否存在冲突：、判断是否存在冲突：LR（（0））项目集规范族项目集规范族C={I0 , I1 , I2 , I3 , I4 , I5 , I6 }I0 ={S’→ .S，，S→ .BB，，B →.aB，，B →.b}I1 = {S’→ S.} （（归约项）归约项）I2 = {S →B.B，，B →.aB，，B →.b}I3 = {B →a.B ，，B →.aB，，B →.b}I4 = {B →b.} （（归约项）归约项）I5= {S →BB.} （（归约项）归约项）I6 ={B →aB.}）） （（归约项）归约项）结论：结论：不存在冲突，所以该文法不存在冲突，所以该文法是是LR（（0））文法，不是文法，不是SLR（（1））文法。

文法I0:I6:aI3:aI2:I5:BSI1:BI4:bbBab作业：作业：P1345.（（1）（）（2）（）（3））7、、。