《5.3.2-lr(0)项目集族和lr(0)分析表的构造》由会员分享，可在线阅读，更多相关《5.3.2-lr(0)项目集族和lr(0)分析表的构造（40页珍藏版）》请在金锄头文库上搜索。
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:SaAcBe 1 Ab 2 AAb 3 Bd 4,当栈顶出现可归前缀即可归约,栈里的文法符号与剩余符号串一起构成了规范句型 栈里的文法符号构成活前缀,S =aAcBe =aAcde =aA
3、bcde =abbcde,规范 推导 序列,#abbcde#的规范归约过程,识别句型#abbcde#所有活前缀的DFA,确定化,最小化,G:SaAcBe 1 Ab 2 AAb 3 Bd 4,利用DFA进行 移近-归约分析 (见黑板),G:SaAcBe 1 Ab 2 AAb 3 Bd 4,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,
4、小结,识别文法所有活前缀的DFA,LR分析表,LR分析,二、构造识别文法所有活前缀的DFA,1. LR(0)项目 2. 构造识别文法所有活前缀的DFA 3. LR(0)项目的分类,求出文法所有的活前缀 根据产生式得出可能出现在栈中的符号串,1. LR(0)项目,在文法G中每个产生式的右部适当位置添加一个圆点构成项目. 对空产生式A , 仅有项目A,例: 产生式 A XYZ 对应的项目有 AXYZ AXYZ AXYZ AXYZ,一个产生式可对应的项目个数是它的右部符号长度加1 每个项目的含义与圆点的位置有关,补充例,对应的项目: (1)SaAd (2)S aAd (3)S aAd (4)S aA
5、d (5)Abc (6)A bc (7)A bc,借助项目构造识别文法活前缀的DFA,G: S aAd Abc,2. 构造识别文法所有活前缀的DFA,1). 文法的每个项目都为NFA的一个状态 2). 确定状态之间的转换关系 3). 确定化最小化,例5.8 p105,G: SE EaA|bB AcA|d BcB|d,更正,1SE 2SE 11. EbB 3EaA 12. EbB 4EaA 13. EbB 5EaA 14. BcB 6AcA 15. BcB 7AcA 16. BcB 8AcA 17. Bd 9Ad 18. Bd 10. Ad,文法的项目:,1). 文法的每个项目都为NFA的一个状
6、态,2). 确定状态之间的转换关系,Xi,XX1X2Xi-1XiXn,XX1X2XiXi+1Xn,XA,A,状态i,状态j,出自同一产生式,项目1 为初态,P106 NFA,1SE 2SE 3EaA 4EaA 5EaA 6AcA 7AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,每个状态都为活前缀识别态 句柄识别态(可归前缀识别态): 圆点在最后的项目,句子识别态,p106,识别一个文法活前缀的DFA,3).确定化 最小化,每个状态是一个项目集, 称作LR(0)项目集 整个状态集
7、称为LR(0)项目集规范族,3. LR(0)项目的分类,移进项目: Aa 分析时把a移进符号栈 待约项目: AB 用产生式A的右部归约时,首先要将B的产生式右部归约为B, 对A的右部才能继续进行分析 归约项目: A 表明一个产生式的右部已分析完，句柄已形成可以归约 接受项目: SS 表明已分析成功,三、LR(0)项目集规范族的构造,构造识别文法活前缀DFA的三种方法 * 求出活前缀的正规表达式，然后由此正规表达式构造NFA, 再确定化为DFA。 求出文法的所有项目，按一定规则构造识别活前缀的NFA, 再确定化为DFA。 通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状
8、态之间的连接关系得到识别活前缀的DFA。,1.拓广文法 2.项目集I的闭包函数 CLOSURE(I) 3.状态转换函数 GO(I, X) 4.构造文法的LR(0)项目集规范族,1.拓广文法,原文法G的开始符号为S, 在G中加SS 后得新的文法G， 则称 G为原文法G的拓广文法。 使文法的开始符号不出现在任何产生式右部，当栈顶出现S,则分析完成 。 注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。,2.项目集I的闭包函数 CLOSURE(I),a) I 的项目均在 CLOSURE(I) 中。 b) 若AB属于CLOSURE(I), 则每一形如 B的项目也属于CLOSUR
9、E(I) c) 重复b)直到CLOSURE(I)不再扩大。,NFA : 状态集合I的-闭包 -closure(I),AB,B,补充例,I SE CLOSURE(I) = SE, EaA, EbB ,1SE 2SE 3EaA 4EaA 5EaA 6AcA 7AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. 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识别活前缀,
10、则状态J识别活前缀X,状态I,状态J,NFA : 状态集合I的a弧转换,补充例,I SE , EaA , EbB GO(I, a) = CLOSURE( EaA ) = EaA , AcA, Ad ,1SE 2SE 3EaA 4EaA 5EaA 6AcA 7AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,1,3,11,4,6,9,4.构造文法的LR(0)项目集规范族 C=I0,I1,In,核: 圆点不在产生式右部最左边的项目称为核 a) 置项目SS为初态集的核，然后对核求闭包，C
11、LOSURE(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,初态的项目集,应用状态转换函数得到新的项目集,G: SE EaA|bB AcA|d BcB|d,I0: SE E aA E bB,I8: BcB
12、 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,识别文法所有活前缀的DFA LR(0)项目集规范族 I0,I1, I11,四、有效项目 *,如果存在规范推导 则项目A12 对活前缀 1 是有效的。 如果2 ，应该移进 如果2 = ，应该用产生式A1归约,G: SE EaA|bB AcA|d BcB|d,项目集I5对活前缀bc有效,考虑如下规范推导 (1) S E
13、 bB bcB (2) S E bB bcB bccB (3) S E bB bcB bcd,图5.7 p106,识别文法 活前缀的DFA,从初态出发,经读出活前缀后,而到达的项目集称为活前缀的有效项目集,LR分析理论的一条基本定理 p108,在任何时候，分析栈中的活前缀X1X2.Xm的有效项目集正是栈顶状态Sm所代表的那个集合。,同一个项目可能对好几个活前缀都有效,G: SE EaA|bB AcA|d BcB|d,同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。 这种冲突通过向前多看几个输入符号, 或许能够获得解决。,移进-归约冲突 一个项目集中移进和归约项目同时存在： Aa B 归约-归约冲突 一个项目集中归约和归约项目同时存在: A B,五、LR(0)分析表的构造,LR(0)文法,假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况 既含移进项目又含归约项目 或者含有多个归约项目 则称G是一个LR(0)文法。 LR(0)文法规范族的每个项目集不包含任何冲突项目(移进-归约冲突、归约-归约冲突) 。,LR(0)分析表的构造,假设已构造出LR(0)项目集规范族为: C=I0,I1, , In 令包含SS 项目的集合Ik的下标k为分析器的初始状态。,a) 若项目Aa属于I
