LR项目集族和LR分析表的构造ppt课件.ppt

第五章语法分析 5 1自下而上分析基本问题5 2算符优先分析5 3LR分析5 4YACC 5 3LR分析 5 3 1LR分析器5 3 2LR 0 项目集族 LR 0 分析表的构造5 3 3SLR分析表的构造5 3 4规范LR分析表的构造5 3 5LALR分析表的构造5 3 6二义文法的应用 5 3 2LR 0 项目集族 LR 0 分析表的构造 一 前缀 活前缀p104二 构造识别文法所有活前缀的DFAp104三 LR 0 项目集规范族的构造p106四 有效项目p108五 LR 0 分析表的构造p109 一 前缀 活前缀 前缀 符号串的头活前缀 规范句型的一个前缀 这种前缀不包含句柄之后的任何符号 可归前缀 包含句柄的活前缀 规范推导序列 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 S aAcBe 1 A b 2 A Ab 3 B d 4 当栈顶出现可归前缀即可归约 栈里的文法符号与剩余符号串一起构成了规范句型栈里的文法符号构成活前缀 S aAcBe aAcde aAbcde abbcde 规范推导序列 abbcde 的规范归约过程 识别句型 abbcde 所有活前缀的DFA 确定化 最小化 G S aAcBe 1 A b 2 A Ab 3 B d 4 利用DFA进行移近 归约分析 见黑板 G S aAcBe 1 A b 2 A Ab 3 B d 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 小结 识别文法所有活前缀的DFA LR分析表 LR分析 二 构造识别文法所有活前缀的DFA 1 LR 0 项目2 构造识别文法所有活前缀的DFA3 LR 0 项目的分类 求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串 1 LR 0 项目 在文法G中每个产生式的右部适当位置添加一个圆点构成项目 对空产生式A 仅有项目A 例 产生式A XYZ对应的项目有A XYZA X YZA XY ZA XYZ 一个产生式可对应的项目个数是它的右部符号长度加1每个项目的含义与圆点的位置有关 补充例 对应的项目 1 S aAd 2 S a Ad 3 S aA d 4 S aAd 5 A bc 6 A b c 7 A bc 借助项目构造识别文法活前缀的DFA G S aAdA bc 2 构造识别文法所有活前缀的DFA 1 文法的每个项目都为NFA的一个状态2 确定状态之间的转换关系3 确定化最小化 例5 8p105 G S EE aA bBA cA dB cB d 更正 1 S E2 S E 11 E bB3 E aA12 E b B4 E a A13 E bB 5 E aA 14 B cB6 A cA15 B c B7 A c A16 B cB 8 A cA 17 B d9 A d18 B d 10 A d 文法的项目 1 文法的每个项目都为NFA的一个状态 2 确定状态之间的转换关系 Xi X X1X2 Xi 1 Xi Xn X X1X2 Xi Xi 1 Xn X A A 状态i 状态j 出自同一产生式 项目1为初态 P106NFA 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 每个状态都为活前缀识别态 句柄识别态 可归前缀识别态 圆点在最后的项目 句子识别态 p106 识别一个文法活前缀的DFA 3 确定化最小化 每个状态是一个项目集 称作LR 0 项目集整个状态集称为LR 0 项目集规范族 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 不再扩大 NFA 状态集合I的 闭包 closure I A B B 补充例 I S E CLOSURE I S E E aA E bB 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 1 3 11 3 状态转换函数GO I X GO I X CLOSURE J X VN VT J A X A X I X A X A X 若状态I识别活前缀 则状态J识别活前缀 X 状态I 状态J NFA 状态集合I的a弧转换 补充例 I S E E aA E bB GO I a CLOSURE E a A E a A A cA A d 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 1 3 11 4 6 9 4 构造文法的LR 0 项目集规范族C I0 I1 In 核 圆点不在产生式右部最左边的项目称为核a 置项目S S为初态集的核 然后对核求闭包 CLOSURE S S 得到初态的项目集 b 对初态集或其它所构造的项目集应用转换函数GO I X CLOSURE J 求出新状态J的项目集 c 重复b 直到不出现新的项目为止 算法 Procedureitemsets G BeginC CLOSURE S S RepeatforC中的每一个I和每一个XdoifGO I X 非空且不属于Cthen把GO I X 放入C中untilC不再增大end p107 初态的项目集 应用状态转换函数得到新的项目集 G S EE aA bBA cA dB cB d I0 S EE aAE bB I8 B c BB cBB d I3 E b BB cBB d I2 E a AA cAA d I1 S E I5 A c AA cAA d I10 A cA I6 A d I4 E aA I7 E bB I9 B d I11 B cB b E a c c c c d d d d A A B B 识别文法所有活前缀的DFALR 0 项目集规范族 I0 I1 I11 四 有效项目 如果存在规范推导则项目A 1 2对活前缀 1是有效的 如果 2 应该移进如果 2 应该用产生式A 1归约 G S EE aA bBA cA dB cB d 项目集I5对活前缀bc有效 考虑如下规范推导 1 S E bB bcB 2 S E bB bcB bccB 3 S E bB bcB bcd 图5 7p106 识别文法活前缀的DFA 从初态出发 经读出活前缀 后 而到达的项目集称为活前缀 的有效项目集 LR分析理论的一条基本定理p108 在任何时候 分析栈中的活前缀X1X2 Xm的有效项目集正是栈顶状态Sm所代表的那个集合 同一个项目可能对好几个活前缀都有效 G S EE aA bBA cA dB cB d 同一个活前缀 可能存在若干个项目对它都是有效的 而且告诉我们应做的事情各不相同 相互冲突 这种冲突通过向前多看几个输入符号 或许能够获得解决 移进 归约冲突一个项目集中移进和归约项目同时存在 A a B 归约 归约冲突一个项目集中归约和归约项目同时存在 A B 五 LR 0 分析表的构造 LR 0 文法 假若一个文法G的拓广文法G 的活前缀识别自动机中的每个状态 项目集 不存在下述情况 既含移进项目又含归约项目 或者含有多个归约项目则称G是一个LR 0 文法 LR 0 文法规范族的每个项目集不包含任何冲突项目 移进 归约冲突 归约 归约冲突 LR 0 分析表的构造 假设已构造出LR 0 项目集规范族为 C I0 I1 In 令包含S S项目的集合Ik的下标k为分析器的初始状态 a 若项目A a 属于Ik 且GO Ik a Ij则置ACTION k a 为Sjb 若项目A 属于Ik 则对任何终结符a和 置ACTION k a 和ACTION k 为 rj j为在文法G 中某产生式A 的序号 c 若项目S S 属于Ik 则置ACTION k 为 acc 接受d 若GO Ik A Ij 则置GOTO k A 为 j e 凡不能用上述方法填入的元素 均填上 报错标志 空白 I0 S EE aAE bB I8 B c BB cBB d I3 E b BB cBB d I2 E a AA cAA d I1 S