资源描述：
《语法分析自底向上的分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、语法分析——自底向上的分析重点与难点重点：自底向上分析的基本思想，算符优先分析法的基本思想，简单算符优先分析法。LR分析器的基本构造思想，LR分析算法，规范句型活前缀及其识别器一一DFA,LR(O)分析表的构造，SLR(1)分析表的构造。难点：求FIRSTOP和LASTOP,算符优先关系的确定，算符优先分析表的构造，素短语与最左素短语的概念。规范句型活前缀，LR(0)项目集闭包与项目集规范族，它们与句柄识别的关系，活前缀与句柄的关系。基本要求掌握自底向上分析的基本思想、移进规约、分析器的基本结构，分析器的四种
2、动作，移进归约冲突，归约归约冲突。掌握算符优先分析方法；熟练掌握LR分析器、SLR(l)分析。了解LR⑴分析、LALR(l)分析。例题解析例1S-*aS
3、bS
4、a(1)构造该文法的LR(O)项目集规范族(2)构造识别该文法所产生的活前缀的DFAo(3)构造其SLR分析表，并判断该文法是否是SLR(l)文法。【解】解题思路构造LR(0)项目集规范族，有两种方法：一种是利用有限白动机來构造，另一种是利用函数CLOSURE和GO來构造。木题采取笫2种方法，通过计算函数CLOSURE和GO得到文法的LR(O)项H集规
5、范族，而GO函数则把LR(O)项H集规范族连成一个识别该文法所产生的活前缀的DFAo解答(1)将文法G(S)拓广为G(S,)：(O)S'->s(l)S-aS⑵S->bS(3)S-*a构造该文法的LR(0)项目集规范族：I。二CLOSURE({S->・S})二{S'-・S,S->・aS,S-・bS,S-*・a}Ii=G0(Io,a)二CLOSURE({S—a・S,S—a•})={S-*a・S,S-*a•,S—•aS,S—・bS,S-*・a}I2二GOdo,b)二CLOSURE({S-b・S})={S-b・S,S
6、-・aS,S->・bS,S-・a}I3二GO(Io,S)二CLOSURE({S'-S・})二{S'-S・}GO仃】，a)=CLOSURE({S->a・S,S-*a・})二hG0(I2,b)二CLOSURE({S-b•S})=I2I.i=GO(Ii,S)二CLOSURE({S-aS・})={S—aS・}GO仃2,a)二CLOSURE({S->a・S,S->a・})二1】G0(I2,b)=CLOSURE({S->b•S})=I2I5=G0(I2,S)二CLOSURE({S-bS•})={S-bS•}所以，项目集I
7、。，II,12,I3,Il和Is构成了该文法的LR(O)项目集规范族。(1)我们用GO函数把LR(O)项
8、=
9、集规范族连成一个识别该文法所产生的活前缀的DFA如图1所示。L图1识别活前缀的DFA(3)构造其SLR分析表。表1SLR分析表ACTIONGOTO状态ab#S0SIS231SIS2r342SIS253acc4rl5r2注意到状态L存在“移进-归纳”冲突，计算S的FOLLOW集合:FOLLOW(S)={#}可以采用SLR冲突消解法，得到表5.1所列的SLR分析表。从分析表可以看出，表中没有冲突项，所以该
10、文法是SLR(l)文法。例2构造识别下列文法的所有活前缀的DFAS-A
11、BA-*aAcA-*aBbBdB-b【解】(1)构造推广文法0)S'->s1)S-*A2)S-*B3)A-*aAc4)A->a5)B-bBd6)B-*b(2)识别该拓广文法的所有规范句型活前缀的DM项目集规范族0{10,11,12,13,14,15,16,17,18,19}10={S'->.S,S->.A,S->.B,A->.aAc,A->.a,B->.bBd,B->.b}Il二{S'-*S.}12=(S->A.)13二(S-B.)T4=
12、(A-*a.Ac,A-*a.,A~*.aAcA-*.a)15=(BfBd,B—b・,BfbBd,Bfb)16=(A-*aA.c)17=(B—bB.d)18=(A-^aAc.)19=(B-^bBd.)(1)识别该拓广文法的所有规范句型活前缀的DFA例3给定文法G:S-(L
13、aL-S,L
14、)(1)构造拓广文法及拓广文法的LR(0)项目集规范族(状态集合)o(2)构造这个文法的SLR(1)分析表，【解】(1)构造拓广文法S'-SS-(L2)S-*a3)L-S,L4)L)拓广文法的LR(0)项H集规范族(状态集介)0
15、)S，fs011)S一(L0,2,7232)S-*a0,2,763)LS,L2,74784)L-)2,75(2)求各非终结符的FISRT集和FOLLOW集:FIRST(S)={(,a)FIRST(L)={a}uFIRST(S)={(,),a}FOLLOW(S)={，,，,#}FOLLOW(L)=FOLLOW(S)={',',#}G的SLR(l)分析表:(a)#SL0s2s611acc2S2s6s54
