编译原理张晶LR分析法图文学习教案

1、会计学1编译编译(biny)原理张晶原理张晶 LR分析法图文分析法图文第一页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3 3）第1页/共113页第二页，共113页。 总控程序总控程序(chngx)(chngx) 分析表分析表输出输出(shch)带带输入带输入带下推栈下推栈第六章第六章 LRLR分析法及分析程序自动构造（分析法及分析程序自动构造（4 4）第2页/共113页第三页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5 5）第3页/共113页第四页，共

2、113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6 6）第4页/共113页第五页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7 7）第5页/共113页第六页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8 8）第6页/共113页第七页，共113页。 总控程序总控程序(chngx) 分析表分析表输出输出(shch)带带输入输入(sh(shr)r)带带下推栈下推栈二、二、LRLR分析器分析器一个一个L

3、RLR分析器实际上是带有下推栈的确定的有限状态分析器实际上是带有下推栈的确定的有限状态自动机。可将一个自动机。可将一个“历史历史”与这个与这个“历史历史”下的展望信息下的展望信息综合为抽象的一个状态综合为抽象的一个状态第六章第六章 LRLR分析法及分析程序自动构造（分析法及分析程序自动构造（9 9）第7页/共113页第八页，共113页。下符号唯一确定下符号唯一确定第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1010）第8页/共113页第九页，共113页。s sm ms s0 0 x xm m# #状态状态(zhun(zhungti)gti

4、)栈栈符号符号(fho)(fho)栈栈下推栈下推栈栈顶指针栈顶指针(zhzh(zhzhn)n)把一个把一个“历史历史”和这个和这个“历史历史”下的下的“展望展望”信息信息综合为抽象的一个状态，下推栈用于存放在对输入串综合为抽象的一个状态，下推栈用于存放在对输入串进行分析的过程中这些状态，由于每个状态都概括了进行分析的过程中这些状态，由于每个状态都概括了从分析开始到归约阶段的全部从分析开始到归约阶段的全部“历史历史”和和 “展望展望”信信息，所以栈顶的状态就可用于决定当前的动作息，所以栈顶的状态就可用于决定当前的动作第六章第六章 LRLR分析法及分析程序自动构造（分析法及分析程序自动构造（111

5、1）第9页/共113页第十页，共113页。s sm ms s0 0 x xm m# #状态状态(zhu(zhungti)ngti)栈栈符号符号(fho(fho) )栈栈下推栈下推栈栈顶指针栈顶指针(zh(zhzhzhn)n)为了便于了解栈顶状态对正规分析过程的作用，我为了便于了解栈顶状态对正规分析过程的作用，我们把栈分为两栏：状态栏和符号栏。符号栈仅用于记们把栈分为两栏：状态栏和符号栏。符号栈仅用于记录迄今移进录迄今移进-归约所得到的文法符号，由于它们已经被概归约所得到的文法符号，由于它们已经被概括在括在“状态状态”里了，所以对语法分析不起作用。里了，所以对语法分析不起作用。初始时，状态栈放初

6、始时，状态栈放S S0 0（初态），符号栈放（初态），符号栈放“# #”（栈底符（栈底符）；栈顶）；栈顶SmSm代表符号栈内的符号串代表符号栈内的符号串XmXm-1XmXm-1X X1 1及其展望信及其展望信息息第六章第六章 LRLR分析法及分析程序自动构造（分析法及分析程序自动构造（1212）第10页/共113页第十一页，共113页。a1a2ana1a2an A1A2AnS0.Sk这张分析表包含两部分：动作表（这张分析表包含两部分：动作表（Action)Action)和转向表和转向表(GoTo)(GoTo)，它们都，它们都是二维数组是二维数组SiSi表示表示(biosh)(biosh)状态，

7、状态，aiai表示表示(biosh)(biosh)终结符，终结符，AiAi表示表示(biosh)(biosh)非终结符非终结符ActionActiongotogoto第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1313）第11页/共113页第十二页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1414）第12页/共113页第十三页，共113页。状态状态ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r

8、6r6r6r66S5S4937S5S4108S6S119r1r1r110r3r3r3r311r5r5r5r5第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1515）第13页/共113页第十四页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1616）第14页/共113页第十五页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1717）第15页/共113页第十六页，共113页。第六章第六章 LR LR分析法及分析

9、程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1818）第16页/共113页第十七页，共113页。状态状态ACTIONACTIONGOTOGOTOi i+ +* *( () )# #E ET TF F0 0S S5 5S S4 41 12 23 31 1S S6 6accacc2 2r r2 2S S7 7r r2 2r r2 23 3r r4 4r r4 4r r4 4r r4 44 4S S5 5S S4 48 82 23 35 5r r6 6r r6 6r r6 6r r6 66 6S S5 5S S4 49 93 37 7S S5 5S S4 410108 8S S6

10、 6S S11119 9r r1 1r r1 1r r1 11010r r3 3r r3 3r r3 3r r3 31111r r5 5r r5 5r r5 5r r5 5第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（1919）第17页/共113页第十八页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈符号栈i i* *i+i #i+i #E E+TE TT T*FT FF (E)F i第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（2020）第18页/共11

11、3页第十九页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈、符号栈* *i+i #i+i #E E+TE TT T*FT FF (E)F i5 5i i5 i5 i第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（2121）第19页/共113页第二十页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈、符号栈* *i+i #i+i #E E+TE TT T*FT FF (E)F i3 3F F第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（

12、构造（2222）第20页/共113页第二十一页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈符号栈* *i+i #i+i #E E+TE TT T*FT FF (E)F i3 F3 F第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（2323）第21页/共113页第二十二页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈符号栈* *i+i #i+i #E E+TE TT T*FT FF (E)F i2 2T T第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng

13、)(zdng)构造（构造（2424）第22页/共113页第二十三页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈、符号栈i+i #i+i #E E+TE TT T*FT FF (E)F i2 2T T7 7* *第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（2525）第23页/共113页第二十四页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈、符号栈+i #+i #E E+TE TT T*FT FF (E)F i2 2T T5 5i i第六章第六章 LR LR分析法及分析程序自

14、动分析法及分析程序自动(zdng)(zdng)构造（构造（2626）第24页/共113页第二十五页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈、符号栈+i #+i #E E+TE TT T*FT FF (E)F i2 2T T7 7* * 5 i 5 i第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（2727）第25页/共113页第二十六页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈、符号栈+i #+i #E E+TE TT T*FT FF (E)F i2 2T T7 7*

15、*10 F10 F第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（2828）第26页/共113页第二十七页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈符号栈+i #+i #E E+TE TT T*FT FF (E)F i1010 F F7 7 * *2 T 2 T 第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（2929）第27页/共113页第二十八页，共113页。0 0# #状态状态(zhungti)(zhungti)、符号栈符号栈+i#+i#E E+TE

16、 TT T*FT FF (E)F i2 2T T第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3030）第28页/共113页第二十九页，共113页。状态栈状态栈符号栈符号栈输入串输入串动作动作0#i*i+i#05#i*i+i#移进移进03#F*i+i#R6R6归约归约02#T*i+i#R4R4归约归约027#T*i+i#移进移进0275#T*i+i#移进移进02710#T*F+i#R6R6归约归约02#T+i#R3R3归约归约01#E+i#R2R2归约归约016#E+i#移进移进0165#E+i#移进移进0163#E+F#R6R6归约归约0

17、169#E+T#R4R4归约归约01#E#accacc分析成功分析成功第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3131）第29页/共113页第三十页，共113页。分析法适应的文法范围要广一些分析法适应的文法范围要广一些第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3232）第30页/共113页第三十一页，共113页。(suyu)(suyu)活前缀活前缀第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3333）第31页/共113页第

18、三十二页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3434）第32页/共113页第三十三页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3535）第33页/共113页第三十四页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3636）第34页/共113页第三十五页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3737）第35

19、页/共113页第三十六页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3838）第36页/共113页第三十七页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（3939）第37页/共113页第三十八页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4141）第38页/共113页第三十九页，共113页。S S称为接受项目；称为接受项目；第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(

20、zdng)(zdng)构造（构造（4040）第39页/共113页第四十页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4242）第40页/共113页第四十一页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4343）第41页/共113页第四十二页，共113页。 6 6）手工构造文法的项目集规）手工构造文法的项目集规范簇很困难范簇很困难第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4444）第42页/共113页

21、第四十三页，共113页。例如：有一拓广的文法例如：有一拓广的文法G6.1G6.1构造识别构造识别(shbi)(shbi)活前缀的活前缀的NFANFAS E E aA|bB A cA|d B cB|dS E E aA|bB A cA|d B cB|d解：解：1 1、这个文法的项目有：、这个文法的项目有：1.S 1.S E 2.S EE 2.S E 3.E 3.E aAaA4.E a4.E aA 5.E aAA 5.E aA 6.A 6.A cAcA7.A c7.A cA 8.A cAA 8.A cA 9.A 9.A d d10.A d10.A d 11.E 11.E bB 12.E bbB 12

22、.E bB B13.E bB13.E bB 14.B 14.B cB 15.B ccB 15.B cB B16.B cB16.B cB 17.B 17.B d 18.B dd 18.B d第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4545）第43页/共113页第四十四页，共113页。3 38 86 67 74 49 91 10 01 15 52 21 11 11 15 51 14 41 12 21 16 61 13 31 18 81 17 7e ea aE Ee ec ce eA Ab be ed dB Be ec cB Bd de e

23、e ee ee eA Ae e第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4646）第44页/共113页第四十五页，共113页。确定确定(qud(qudng)ng)化后化后1:S E1:S E0:S E0:S E E aA E aA E bB E bB5:A cA5:A cA A cA A cA E d E d2: E aA2: E aA A cA A cA A d A d3:E bB3:E bB B cB B cB B d B d8:B cB8:B cB B cB B cB B d B d4:E aA4:E aA6: A d6: A d

24、10:A cA10:A cA7:E bB7:E bB9: B d9: B d11:B cB11:B cBc cc cb bE Ec cca aB Bd dd dB BA Ad dAd d第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4747）第45页/共113页第四十六页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4848）第46页/共113页第四十七页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（494

25、9）第47页/共113页第四十八页，共113页。aXaXb b项目，表示识别活前缀又移项目，表示识别活前缀又移进一个符号进一个符号X X第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5050）第48页/共113页第四十九页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5151）第49页/共113页第五十页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5252）第50页/共113页第五十一页，共113页。确定

26、确定(qud(qudng)ng)化后化后1:S E1:S E0:S E0:S E E aA E aA E bB E bB5:A cA5:A cA A cA A cA A d A d2: E aA2: E aA A cA A cA A d A d3:E bB3:E bB B cB B cB B d B d8:B cB8:B cB B cB B cB B d B d4:E aA4:E aA6: A d6: A d10:A cA10:A cA7:E bB7:E bB9: B d9: B d11:B cB11:B cBc cc cb bE Ec cca aB Bd dd dB BA Ad dAd d第

27、六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（4747）第51页/共113页第五十二页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5454）第52页/共113页第五十三页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5555）第53页/共113页第五十四页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5656）第54页/共113页第五十五页

28、，共113页。例如：下面例如：下面(xi mian)(xi mian)的文法是的文法是LR(0)LR(0)文法，但对文法，但对这个文法的各个产生式给予编号并写成：这个文法的各个产生式给予编号并写成：0.S E 1.E aA 2.E bB0.S E 1.E aA 2.E bB3.A cA 4.A d 5.B cB 3.A cA 4.A d 5.B cB 6.B d6.B d第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5757）第55页/共113页第五十六页，共113页。状态状态ACTIONGOTOabcd#EAB0S2S311acc2S5S

29、643S8S974r1r1r1r1r15S5S6106r4r4r4r4r47r2r2r2r2r28S8S9119r6r6r6r6r610r3r3r3r3r311r5r5r5r5r5第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5858）第56页/共113页第五十七页，共113页。第57页/共113页第五十八页，共113页。例如：下面文法例如：下面文法G G的的LR(0)LR(0)项目集规范项目集规范(gufn)(gufn)族中含族中含有如下一个项目集（状态）有如下一个项目集（状态）I0 :I0 :I0=X a bb /I0=X a bb /

30、* *移进项目移进项目* */ / A a / A a /* *归约项目归约项目* */ / B a / B a /* *归约项目归约项目* */ / 第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（5959）这三个项目告诉这三个项目告诉(o s)(o s)我们应做的动作各不相同，出我们应做的动作各不相同，出现了移进现了移进归约冲突和归约归约冲突。这个文法一定归约冲突和归约归约冲突。这个文法一定不是不是LR(0)LR(0)文法。文法。SLR分析法的引入分析法的引入第58页/共113页第五十九页，共113页。第六章第六章 LR LR分析法及分析

31、程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6060）SLR是是LR(0)的一种改进，它在归约时除了考虑历史情况之的一种改进，它在归约时除了考虑历史情况之外还考虑了一点现实。外还考虑了一点现实。一、消除冲突一、消除冲突v1、一个有冲突的项目集、一个有冲突的项目集, ,可以根据读头下符号的不可以根据读头下符号的不同来消除冲突。同来消除冲突。第59页/共113页第六十页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6161）设设C=I0, I1, . InC=I0, I1, . In以各项目集以各项目集Ik(k

32、=0,.n)Ik(k=0,.n)作的作的k k为状态序号，并以为状态序号，并以S SS S包含的项目集作包含的项目集作为为(zuwi)(zuwi)初始状态，同时将产生式进行编号，然后初始状态，同时将产生式进行编号，然后按下列步骤填写按下列步骤填写ACTIONACTION表和表和GOTOGOTO表：表：第60页/共113页第六十一页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6262）注：注：1）若文法按上面算法构造出来的分析表不包含若文法按上面算法构造出来的分析表不包含多重定义项，则该文法多重定义项，则该文法G是是SLR文法

33、。文法。 2）二义文法决不是二义文法决不是LR文法文法 3）SLR分析法包含的现实信息是体现在利用了分析法包含的现实信息是体现在利用了Follow(A)信息，可以解决信息，可以解决“归约归约归约归约”冲突。冲突。 4）SLR分析法没有包含足够的展望信息，不能完分析法没有包含足够的展望信息，不能完全解决全解决“移进移进归约归约”冲突，需要改进。冲突，需要改进。第61页/共113页第六十二页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6363）解解: :按照求按照求LR(0)项目集规范族的算法项目集规范族的算法, ,求得求得G(

34、E)文法的项目集族如下图文法的项目集族如下图: :第62页/共113页第六十三页，共113页。I5:F iI0:S E E E+T E T T T*F T F F (E) F iI2:E T T T*FI1:S E E E+TI4:F (E) E E+T E T T T*F T F F (E) F iI3:T FI6:E E+T T T*F T F F (E) F i I10:T T* *FI7:T T*F F (E) F iI9:E E+T F T*FI8:F (E) E E+TI11:F (E)ii(FTI2(I4TTE)EF*Fi(I5I3I5i+(第六章第六章 LR LR分析法及分析程

35、序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6464）F*+第63页/共113页第六十四页，共113页。6.3 SLR分析表的构造分析表的构造(guzo)二、构造二、构造(guzo)SLR分析分析表的算法表的算法构造构造SLRSLR分析表时要注意项目集族中分析表时要注意项目集族中I1,I2,I9I1,I2,I9三个项目集三个项目集, ,含有冲突含有冲突: :I1:S E I2:E I1:S E I2:E T I9:E E+T T I9:E E+T E E+T T T E E+T T T* *F F T TT T* *F F 根据原来的文法分别求根据原来的文法分别求S, ES,

36、 E的的FollowFollow集集, ,按按SLRSLR方法进行方法进行(jnxng)(jnxng)分析分析, ,得到得到SLRSLR分析表：分析表：第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6565）0.S E1.E E+T2.E T3.T T*F4.T F5.F (E)6.F iFOLLOW(S)=#FOLLOW(E)=FOLLOW(S)+ ) =#,+,)FOLLOW(T)=FOLLOW(E)*=#,+,),*FOLLOW(F)=FOLLOW(T)=#,+,),*第64页/共113页第六十五页，共113页。I5:F iI0:S

37、E E E+T E T T T*F T F F (E) F iI2:E T T T*FI1:S E E E+TI4:F (E) E E+T E T T T*F T F F (E) F iI3:T FI6:E E+T T T*F T F F (E) F i I10:T T* *FI7:T T*F F (E) F iI9:E E+T F T*FI8:F (E) E E+TI11:F (E)ii(FTI2(I4TTE)EF*Fi(I5I3I5i+(第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6464）F*+0.S E1.E E+T2.E T3.

38、T T*F4.T F5.F (E)6.F i第65页/共113页第六十六页，共113页。状态状态ACTIONGOTOi+*( )#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r4 4S5S48235r6r6 r6r6 6S5 S4 937S5 S4 108S6 S11 9 r1 S7r1r110 r3r3 r3r3第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6666）第66页/共113页第六十七页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6767

39、）返回第67页/共113页第六十八页，共113页。5:L i0:S S S L=R S R L * *R L I R L3:S R 4: L * * R R L L i L i6:S L=R R L L *R L i8:R L7:L * *R2:S L=R R L1:S S9:S L=R=iS*iRi*LLRR第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6868）L第68页/共113页第六十九页，共113页。状态状态ACTIONGOTO=i*#SLR0S5S41231acc2S6/ r6r6 3 r34S5S4875r5r56S5S489

40、7r4 r48r6 r69 r2第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（6969）第69页/共113页第七十页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7070）第70页/共113页第七十一页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7171）第71页/共113页第七十二页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7272

41、）第72页/共113页第七十三页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7373）第73页/共113页第七十四页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7474）第74页/共113页第七十五页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7575）第75页/共113页第七十六页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造

42、（构造（7676）第76页/共113页第七十七页，共113页。n注：在执行转换函数注：在执行转换函数GOGO时，搜时，搜索符并不改变。索符并不改变。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7777）第77页/共113页第七十八页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7878）第78页/共113页第七十九页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（7979）第79页/共113页第八十页，共1

43、13页。I0I0初态初态 S S S,#S,# S S L=R,#L=R,#S S R,#R,#L L * *R,=R,=L L i,=i,=R R L,#L,#L L * *R,#R,#L L i,# i,# I0I0初态初态 S S S,#S,# S S L=R,#L=R,#S S R,#R,# L L * *R,=|#R,=|# L L i,=|#i,=|#R R L,#L,#缩写缩写(suxi)为为2、接着利用、接着利用GO函数，对该项目函数，对该项目(xingm)集内得各项目集内得各项目(xingm)求后继项目求后继项目(xingm)集，然后再对新求的项目集，然后再对新求的项目(xi

44、ngm)集重复上面的过程，直到项目集重复上面的过程，直到项目(xingm)集不再增加为集不再增加为止。止。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8080）第80页/共113页第八十一页，共113页。S S,#S L= R,#S R,#R L,#L *R,=L i,=L *R,#L i,#S S,#sS L = R,#R L,#S R,#LRL *R,=L *R,#R L,=R L,#L *R,=L i,=L *R,#L i,#*L i,=L i,#ii*S L= R,#R L,#L *R,#L i,#=S L= R,#RL i,#i

45、L *R,=L *R,#R L,=R L,#RLR L,#L *R,#R L,#L *R,#L i,#L*L*L *R,#RI0I1I2I3I4I5I6I7I8I9I11I12I10I13i第81页/共113页第八十二页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8181）第82页/共113页第八十三页，共113页。构造的规范构造的规范LR(1)LR(1)分析分析(fnx)(fnx)表如下：表如下：第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8282）第83页/共113

46、页第八十四页，共113页。状态状态ACTIONGOTO=i*#SLR0S5S41231acc2S6r6 3 r34S5S4875r5r56S10S121197r4 r48r6 r69r210r511r612 S10 S121113第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8383）第84页/共113页第八十五页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8484）第85页/共113页第八十六页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自

47、动(zdng)(zdng)构造（构造（8585）第86页/共113页第八十七页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8686）第87页/共113页第八十八页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8787）第88页/共113页第八十九页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（8888）第89页/共113页第九十页，共113页。第六章第六章 LR LR分析法及分析程序自动分析

48、法及分析程序自动(zdng)(zdng)构造（构造（8989）第90页/共113页第九十一页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（9090）第91页/共113页第九十二页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（9191）第92页/共113页第九十三页，共113页。第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（9292）第93页/共113页第九十四页，共113页。第六章第六章 LR LR分析法及

49、分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（9393）第94页/共113页第九十五页，共113页。状态状态ACTIONGOTO=i*#SLR0S5S41231acc2S6r6 3 r34S5S4875r5r56S10S121197r4 r48r6 r69r210r511r612 S10 S121113LR(1)LR(1)分析分析(fnx)(fnx)表表第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（9494）第95页/共113页第九十六页，共113页。状态状态ACTIONGOTO=i*#SLR0S5S41231acc2

50、S6r6 3 r34S5S4875r5 r56S5S4897r4 r48r6 r69r2新构造新构造(guzo)(guzo)的的LALRLALR分析表分析表第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（9595）第96页/共113页第九十七页，共113页。步骤步骤状态栈状态栈符号栈符号栈输入串输入串0 00 0# #i=i=* *i=#i=#1 10 0，5 5#i#i= =* *i=#i=#2 20 0，2 2#L#L= =* *i=#i=#3 30 0，2 2，6 6#L=#L=* *i=#i=#4 40 0，2 2，6 6，1212#

51、L=#L=* *i=#i=#5 50 0，2 2，6 6，1212，1010#L=#L=* *i i=#=#报错报错第六章第六章 LR LR分析法及分析程序自动分析法及分析程序自动(zdng)(zdng)构造（构造（9696）第97页/共113页第九十八页，共113页。步骤步骤状态栈状态栈符号栈符号栈输入串输入串0 00 0# #i=i=* *i=#i=#1 10 0，5 5#i#i= =* *i=#i=#2 20 0，2 2#L#L= =* *i=#i=#3 30 0，2 2，6 6#L=#L=* *i=#i=#4 40 0，2 2，6 6，4 4#L=#L=* *i=#i=#5 50 0，2 2，6 6，4 4，5 5#L=#L=* *i i=#=#6 60,2,6,4,80,2,6,4,8#L=#L=* *L L=#=#7 70,2,6,4,70,2,6,4,7#L=#L=* *R R=#=#8 80,2,6,80,2,6,8#L=L#L=L=#=#9 90,2,6,90,