《LR(0)项目集族和LR(0)分析表的构造课件.ppt》由会员分享，可在线阅读，更多相关《LR(0)项目集族和LR(0)分析表的构造课件.ppt（42页珍藏版）》请在三一办公上搜索。
1、第五章 语法分析,5.1 自下而上分析基本问题5.2 算符优先分析 5.3 LR分析5.4 YACC,5.3 LR分析,5.3.1 LR分析器5.3.2 LR(0)项目集族LR(0)分析表的构造5.3.3 SLR分析表的构造5.3.4 规范LR分析表的构造5.3.5 LALR分析表的构造5.3.6 二义文法的应用,5.3.2 LR(0)项目集族LR(0)分析表的构造,一、前缀、活前缀 p104二、构造识别文法所有活前缀的DFA p104三、LR(0)项目集规范族的构造 p106四、有效项目 p108五、LR(0)分析表的构造 p109,一、前缀、活前缀,前缀:符号串的头 活前缀:规范句型的一个
2、前缀,这种前缀不包含句柄之后的任何符号.*可归前缀:包含句柄的活前缀.,规范推导序列,S=aAcBe=aAcde=aAbcde=abbcde,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe,活前缀,可归前缀ab,aAb,aAcd,aAcBe,补充例:找出句型#abbcde#的所有活前缀,G:SaAcBe1 Ab2 AAb3 Bd4,当栈顶出现可归前缀即可归约,栈里的文法符号与剩余符号串一起构成了规范句型栈里的文法符号构成活前缀,S=aAcBe=aAcde=aAbcde=abbcde,规范推导序列,#abbcde#的规范归约过程,识别句型#abbc
3、de#所有活前缀的DFA,确定化,最小化,G:SaAcBe1Ab2AAb3Bd4,利用DFA进行移近-归约分析(见黑板),G:SaAcBe1Ab2AAb3Bd4,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,acc,S,S,S,S,S,S,GOTO,ACTION,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,1,1,1,1,1,1,LR分析表,DFA的矩阵表示,一个LR分析器实质上是一个DFA,小结,识别文法所有活前缀的DFA,LR分析表,LR分析,二、构造识别文法所有活前缀的DFA,1.LR(0)项目2.构造识别文法
4、所有活前缀的DFA3.LR(0)项目的分类,求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串,1.LR(0)项目,在文法G中每个产生式的右部适当位置添加一个圆点构成项目.对空产生式A,仅有项目A,例:产生式 A XYZ 对应的项目有 AXYZ AXYZAXYZ AXYZ,一个产生式可对应的项目个数是它的右部符号长度加1每个项目的含义与圆点的位置有关,补充例,对应的项目:(1)SaAd(2)S aAd(3)S aAd(4)S aAd(5)Abc(6)A bc(7)A bc,借助项目构造识别文法活前缀的DFA,G:S aAd Abc,2.构造识别文法所有活前缀的DFA,1).文法的每个项目
5、都为NFA的一个状态 2).确定状态之间的转换关系 3).确定化最小化,例5.8 p105,G:SE EaA|bB AcA|d BcB|d,更正,1SE 2SE 11.EbB3EaA 12.EbB4EaA 13.EbB5EaA 14.BcB6AcA15.BcB7AcA 16.BcB8AcA 17.Bd9Ad 18.Bd 10.Ad,文法的项目:,1).文法的每个项目都为NFA的一个状态,2).确定状态之间的转换关系,Xi,XX1X2Xi-1XiXn,XX1X2XiXi+1Xn,XA,A,状态i,状态j,出自同一产生式,项目1为初态,P106 NFA,1SE2SE 3EaA4EaA 5EaA 6
6、AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd,每个状态都为活前缀识别态句柄识别态(可归前缀识别态):圆点在最后的项目,句子识别态,p106,识别一个文法活前缀的DFA,3).确定化 最小化,每个状态是一个项目集,称作LR(0)项目集整个状态集称为LR(0)项目集规范族,3.LR(0)项目的分类,移进项目:Aa分析时把a移进符号栈 待约项目:AB用产生式A的右部归约时,首先要将B的产生式右部归约为B,对A的右部才能继续进行分析 归约项目:A 表明一个产生式的右部已分析完，句柄已形成可以归约 接受项目
7、:SS 表明已分析成功,三、LR(0)项目集规范族的构造,构造识别文法活前缀DFA的三种方法*求出活前缀的正规表达式，然后由此正规表达式构造NFA,再确定化为DFA。求出文法的所有项目，按一定规则构造识别活前缀的NFA,再确定化为DFA。通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。,1.拓广文法2.项目集I的闭包函数 CLOSURE(I)3.状态转换函数 GO(I,X)4.构造文法的LR(0)项目集规范族,21,可编辑,1.拓广文法,原文法G的开始符号为S,在G中加SS 后得新的文法G，则称G为原文法G的拓广文法。使文法的开
8、始符号不出现在任何产生式右部，当栈顶出现S,则分析完成。注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。,2.项目集I的闭包函数 CLOSURE(I),a)I 的项目均在 CLOSURE(I)中。b)若AB属于CLOSURE(I),则每一形如 B的项目也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大。,NFA:状态集合I的-闭包-closure(I),AB,B,补充例,I SE CLOSURE(I)=SE,EaA,EbB,1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB
9、14.BcB15.BcB16.BcB 17.Bd 18.Bd,1,3,11,3.状态转换函数 GO(I,X),GO(I,X)=CLOSURE(J),X(VNVT),J=AX|AXI,X,AX,AX,若状态I识别活前缀,则状态J识别活前缀X,状态I,状态J,NFA:状态集合I的a弧转换,补充例,I SE,EaA,EbB GO(I,a)=CLOSURE(EaA)=EaA,AcA,Ad,1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd,1,3,11,4,6,9,4
10、.构造文法的LR(0)项目集规范族 C=I0,I1,In,核:圆点不在产生式右部最左边的项目称为核 a)置项目SS为初态集的核，然后对核求闭包，CLOSURE(SS）得到初态的项目集。b)对初态集或其它所构造的项目集应用转换函数GO(I，X)=CLOSURE(J)求出新状态J的项目集。c)重复b)直到不出现新的项目为止。,算法,Procedure itemsets(G)Begin C:=CLOSURE(SS)Repeat for C中的每一个I 和每一个X do if GO(I,X)非空且不属于C then 把GO(I,X)放入C中 until C不再增大end,p107,初态的项目集,应用状
11、态转换函数得到新的项目集,G:SE EaA|bB AcA|d BcB|d,I0:SE E aA E bB,I8:BcB B cB B d,I3:EbB B cB B d,I2:EaA A cA A d,I1:S E,I5:AcA A cA A d,I10:Ac A,I6:A d,I4:EaA,I7:EbB,I9:B d,I11:BcB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,识别文法所有活前缀的DFALR(0)项目集规范族 I0,I1,I11,四、有效项目*,如果存在规范推导 则项目A12 对活前缀 1 是有效的。如果2，应该移进如果2=，应该用产生式A1归约,G:SEEa
12、A|bBAcA|dBcB|d,项目集I5对活前缀bc有效,考虑如下规范推导(1)S E bB bcB(2)S E bB bcB bccB(3)S E bB bcB bcd,图5.7 p106,识别文法活前缀的DFA,从初态出发,经读出活前缀后,而到达的项目集称为活前缀的有效项目集,LR分析理论的一条基本定理 p108,在任何时候，分析栈中的活前缀X1X2.Xm的有效项目集正是栈顶状态Sm所代表的那个集合。,同一个项目可能对好几个活前缀都有效,G:SEEaA|bBAcA|dBcB|d,同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几
13、个输入符号,或许能够获得解决。,移进-归约冲突 一个项目集中移进和归约项目同时存在：AaB归约-归约冲突一个项目集中归约和归约项目同时存在:AB,五、LR(0)分析表的构造,LR(0)文法,假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况既含移进项目又含归约项目或者含有多个归约项目则称G是一个LR(0)文法。LR(0)文法规范族的每个项目集不包含任何冲突项目(移进-归约冲突、归约-归约冲突)。,LR(0)分析表的构造,假设已构造出LR(0)项目集规范族为:C=I0,I1,In 令包含SS 项目的集合Ik的下标k为分析器的初始状态。,a)若项目Aa属于Ik,且 G
14、O(Ik,a)=Ij 则置 ACTIONk,a 为Sjb)若项目A 属于Ik，则对任何终结符a 和#置ACTIONk,a 和ACTIONk,#为“rj”,j为在文法G中某产生式 A的序号。c)若项目 SS 属于Ik,则置ACTIONk,#为“acc”/接受d)若GO(Ik,A)Ij，则置GOTOk,A 为je)凡不能用上述方法填入的元素,均填上“报错标志”/“空白”,I0:SE E aA E bB,I8:BcB B cB B d,I3:EbB B cB B d,I2:EaA A cA A d,I1:S E,I5:AcA A cA A d,I10:Ac A,I6:A d,I4:EaA,I7:EbB,I9:B d,I11:BcB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,(0)SE(1)EaA(2)EbB(3)AcA(4)Ad(5)BcB(6)Bd,构造LR(0)分析表过程见黑板,根据这种方法构造的LR(0)分析表不含多重定义时，称这样的分析表为LR(0)分析表能用LR(0)分析表的分析器称为LR(0)分析器,42,可编辑,
