第四章_语法分析(4)

《第四章_语法分析(4)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析(4)4.7LR(1)、LALR14.6.4构造SLR分析表算法4.32构造SLR分析表输入：一个拓广文法G输出：G的SLR分析表的函数action和goto方法：1.构造G的LR(0)项目集规范族C={I0,I2,…,In}。2.对于状态Ii的分析动作如下：(a)若A.aBIi且goto(Ii,a)=Ijaction[i,a]=“shiftj”(b)若A.Ii,对于所有aFOLLOW(A)action[i,a]=“reduceA”,AS(c)若SS.Ii,action[i,

2、$]=“accept”3.若goto(Ii,A)=Ij,AVN,则goto[i,A]=j4.分析表其余位置为error2编译原理例4.34每个SLR(1)文法都不是二义的，但是，有许多非二义的文法不是SLR(1)。例如，下面的产生式文法SL=RSRL*RLidRL3编译原理拓广文法G的LR(0)项目集规范族为：I0:S'·SS·L=RS·RL·*RL·idR·LI3:SR·I4:L*·RR·LL·*RL·idI5:Lid·I6:SL=·RR·LL·*RL·idI7:L*R·I

3、8:RL·I9:SL=R·I1:S'S·I2:SL·=RRL·4编译原理idS'SSL=RSRL*RLidRLLidSL=RRLS'SI0I1I2I3SRI4L*RRLLidL*RI5SL*idRSL=RRLL*RLidI6=RSL=RRLLLI7idI3**L*RRI8I95编译原理第一个项目使得action[2,=]为shift第二个项目使得action[2,=]为reduce，因为=Follow(R)。SL=R*R

4、=R但是，不存在以R=…开始的右句型，只有*R=…开始的右句型。SLR(1)文法的描述能力有限S'SSL=RSRL*RLidRLSL=RRLI0I2L6编译原理4.6.5可行前缀（viableprefix）对于一个文法G，构造一个LR（0）自动机，它能识别所有可能出现在分析栈中的文法符号串，栈中的文法符号串一定是某个右句型的前缀。不是右句型的所有前缀都会出现在栈中。7编译原理可以出现在移进归约分析器栈中的右句型的前缀称为可行前缀。定义：一个可行前缀是一个右句型的前缀，并且不含右句柄之后的任何

5、符号。可行前缀后加上终结符可以得到右句型。只有输入串中已分析过的那部分能归约成可行前缀，就没有语法错误。事实上，LR（0）自动机是一个识别可行前缀的DFA。8编译原理识别G的所有可行前缀的NFANFA的状态是一个LR(0)项目。从每个形如B·X的状态出发画一条标记为X的弧到状态BX·，从每个形如B·A的状态出发画一条标记为的弧到所有形如A·的状态。这个NFA通过子集构造法得到的DFA和前面构造的LR(0)自动机是相同的。9编译原理例：p153描述文法的可行前缀SSSSS+

6、SS*

7、a文法的项目

8、有：1.S·S2.SS·3.S·SS+4.SS·S+5.SSS·+6.SSS+·7.S·SS*8.SS·S*9.SSS·*10.SSS*·11S·a12.Sa·10编译原理startS1237S4S511S8S12识别可行前缀的NFA+69*10a11编译原理S.SS.SS+S.SS*S.aI0startSa识别可行前缀的DFASS.SS.S+SS.S*S.SS+S.SS*S.aI1Sa.I2SSS.+SSS.*SS.S+SS.S*S.SS+S

9、.SS*S.aI3SaSSS+.I4SaSSS*.I5+*12编译原理有效项目如果存在一个规范推导S*Aw12w，则项A1·2对可行前缀1是有效的。若项目A1·B2对可行前缀1是有效的，且B是产生式，则项目B·对可行前缀1也是有效的。据假设，存在一个规范推导S*Aw1B2w设2w*xw，则对任何B有规范推导S*Aw1B2w1Bxw1xw所以B.对可行前缀1也是有效的。13编译原理一个项目可能对好几个可行前缀都是有效的。

10、E·E+T对和(这两个可行前缀都有效EEE+T(，1都为空)EE(E)(E+T)(=“(”，1为空)DFA读入和(后到达不同的状态，那么项目E·E+T就出现在不同的项目集中14编译原理一个可行前缀可能有多个有效项目。可能存在动作冲突一个可行前缀的有效项目集就是从这个DFA