《编译原理5.3.2-lr(0)项目集族和lr(0)分析表的构造》由会员分享，可在线阅读，更多相关《编译原理5.3.2-lr(0)项目集族和lr(0)分析表的构造（32页珍藏版）》请在金锄头文库上搜索。
1、第五章 语法分析 5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析 5.4 YACC5.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 Bd4abb c d eAABS当栈顶出现可归前缀即可归约步 骤符号栈剩余 输入串动作1#abbcde# 移进 2#abbcde# 移进 3#abbcde# 归约
3、 Ab 4#aAbcde# 移进 5#aAbcde# 归约 AAb 6#aAcde# 移进 7#aAcde# 移进 8#aAcde# 归约 Bd 9#aAcBe# 移进 10 #aAcBe# 归约 SaAcBe 11 #S# 接受abb c d eAABS栈里的文法符号与 剩余符号串一起构 成了规范句型 栈里的文法符号构 成活前缀S =aAcBe=aAcde=aAbcde =abbcde 规 范 推 导 序 列#abbcde#的规范归约过程二、构造识别文法所有活前缀的DFA 1. LR(0)项目 2. 构造识别文法所有活前缀的DFA 3. LR(0)项目的分类1. LR(0)项目在文法G中每个
4、产生式的右部适当位置添加一 个圆点构成项目. 对空产生式A , 仅有项目A 例: 产生式 A XYZ 对应的项目有 AXYZ AXYZAXYZ AXYZ一个产生式可对应的项目个数是它的右部符号长度加1 每个项目的含义与圆点的位置有关 补充例: 若有产生式 S aAd , Abc 对应的项目: (1)SaAd (2)S aAd (3)S aAd (4)SaAd (5)Abc (6)Abc (7)Abc2. 构造识别文法所有活前缀的DFA1). 文法的每个项目都为NFA的一个状态 2). 确定状态之间的转换关系 3). 确定化最小化例 5.8 p105 G: SE EaA|bBAcA|d BcB|
5、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的一个状态2). 确定状态之间的转换关系XiXX1X2Xi-1XiXnXX1X2XiXi+1XnXAA状态i状态j出自同一产生式项目1 为初态 P106 NFA1 SE 2 SE 3EaA 4EaA 5EaA 6AcA 7 AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB
6、 15. BcB 16. BcB 17. Bd 18. Bd 每个状态都为活前缀识别态 句柄识别态(可归前缀识别 态): 圆点在最后的项目句子识别态 p106识别一个文 法活前缀的 DFA3). 确 定 化 最 小 化每个状态是一 个项目集, 称作 LR(0)项目集 整个状态集称 为LR(0)项目集 规范族3. LR(0)项目的分类 移进项目: Aa分析时把a移进符号栈 待约项目: AB用产生式A的右部归约时,首先要将B的产生 式右部归约为B, 对A的右部才能继续进行分析 归约项目: A 表明一个产生式的右部已分析完，句柄已形 成可以归约 接受项目: SS 表明已分析成功 三、LR(0)项目集
7、规范族的构造构造识别文法活前缀DFA的三种方法 * 求出活前缀的正规表达式，然后由此正规表 达式构造NFA, 再确定化为DFA。 求出文法的所有项目，按一定规则构造识别 活前缀的NFA, 再确定化为DFA。 通过闭包函数和转换函数，直接求出LR(0) 项目集规范族，再由转换函数建立状态之间的 连接关系得到识别活前缀的DFA。1.拓广文法 2.项目集I的闭包函数 CLOSURE(I) 3.状态转换函数 GO(I, X) 4.构造文法的LR(0)项目集规范族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)ABB补 充 例I SE CLOSURE(I) = SE, EaA, EbB 1SE 2SE 3EaA 4EaA 5EaA 6AcA 7AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 1
9、3. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd 13113.状态转换函数 GO(I, X)GO(I, X) = CLOSURE(J) , X(VNVT) , J = AX| AXI XAXAX若状态I识别活前缀,则状态J识别活前缀X 状态I状态JNFA : 状态集合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
10、. BcB 15. BcB 16. BcB 17. Bd 18. Bd 13114694.构造文法的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)
11、非空且不属于C then 把GO(I, X)放入C中 until C不再增大 end p107初态的项目集 应用状态转换 函数得到新的 项目集 G: SE EaA|bB AcA|dBcB|d I0: SE E aA E bBI8: BcB B cB B dI3: EbB B cB B dI2:EaA A cA A dI1: S EI5:AcA A cA A dI10:Ac AI6:A dI4:EaAI7:EbBI9:B dI11:BcBbEaccccddddAABB识别文法所有活前 缀的DFA LR(0)项目集规范族 I0,I1, I11四、有效项目 *移进-归约冲突 一个项目集中移进和归约项
12、目同时 存在： 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属于Ik ,且 GO(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 为“j“e) 凡不能用上述方法填入的元素,均填上“报错标志” / “ 空白”I0: SE E aA E bBI
