编译原理5.3.2-LR项目集族和LR分析表的构造.pptVIP

第五章 语法分析 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 一、前缀、活前缀 前缀 : 符号串的头 活前缀 : 规范句型的一个前缀, 这种前缀不包含句柄之后的任何符号. *可归前缀: 包含句柄的活前缀. 规范推导序列 S =aAcBe =aAcde =aAbcde =abbcde 二、构造识别文法所有活前缀的DFA 1. LR(0)项目 2. 构造识别文法所有活前缀的DFA 3. LR(0)项目的分类 1. LR(0)项目 在文法G中每个产生式的右部适当位置添加一个圆点构成项目. 对空产生式A→ε , 仅有项目A→·　 补充例: 若有产生式 S? aAd , A?bc 对应的项目: (1)S?·aAd (2)S? a·Ad (3)S? aA·d (4)S?aAd· (5)A?·bc (6)A?b·c (7)A?bc· 2. 构造识别文法所有活前缀的DFA 例5.8 p105 G: S→E　　 E→aA|bB　　 A→cA|d　　 B→cB|d 2). 确定状态之间的转换关系 3. LR(0)项目的分类 移进项目: A→α·aβ 分析时把a移进符号栈 待约项目: A→α·Bβ 用产生式A的右部归约时,首先要将B的产生式右部归约为B, 对A的右部才能继续进行分析 归约项目: A→α· 表明一个产生式的右部已分析完，句柄已形成可以归约 接受项目: S→S· 表明已分析成功 三、LR(0)项目集规范族的构造 构造识别文法活前缀DFA的三种方法 * 求出活前缀的正规表达式，然后由此正规表达式构造NFA, 再确定化为DFA。 求出文法的所有项目，按一定规则构造识别活前缀的NFA, 再确定化为DFA。 通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。 1.拓广文法 2.项目集I的闭包函数 CLOSURE(I) 3.状态转换函数 GO(I, X) 4.构造文法的LR(0)项目集规范族 1.拓广文法 原文法G的开始符号为S, 在G中加S→S 后得新的文法G， 则称 G‘为原文法G的拓广文法。 使文法的开始符号不出现在任何产生式右部，当栈顶出现S′,则分析完成 。 注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。 2.项目集I的闭包函数 CLOSURE(I) a) I 的项目均在 CLOSURE(I) 中。 b) 若A→α·Bβ属于CLOSURE(I), 则每一形如 B→·γ的项目也属于CLOSURE(I) c) 重复b)直到CLOSURE(I)不再扩大。 补充例 I＝{ S→·E } CLOSURE(I) = { S→·E, E→·aA, E→·bB } 3.状态转换函数 GO(I, X) GO(I, X) = CLOSURE(J)　, X∈(VN∪VT) , J = {A→αX·β| A→α·Xβ∈I } 补充例 I＝{ S→·E , E→·aA , E→·bB } GO(I, a) = CLOSURE( { E→a·A } ) = { E→a·A , A→·cA, A→·d } 4.构造文法的LR(0)项目集规范族 C={I0,I1,……,In} 核: 圆点不在产生式右部最左边的项目称为核 a) 置项目S′→