第7章LR法(lly)3讲述资料.ppt

文法G‘：(0) S’ ? S(1) B ? aB (2) S ? BB(3) B ? b I0: S’ ? ? S, # S ? ? BB, # B ? ? aB, a/b B ? ? b, a/b I1: S’ ? S ?, # I2: S ? B ? B, # B ? ? a B, # B ? ? b, # I5: S ? B B ?, # I6: B ? a ? B, # B ? ? aB, # B ? ? b, # I9: B ? a B ?, # I4: B ? b ?, a/b I3: B ? a ? B, a/b B ? ? aB, a/b B ? ? b, a/b I8: B ? a B ?, a/b I7: B ? b ?, # S B b b B b b a a a a B B LR(1)项目集和转换函数 分析可发现I3和I6 ， I4和I7 ， I8和I9分别为同心集 I3: B ? a ? B, a/b B ? ? aB, a/b B ? ? b, a/b I6: B ? a ? B, # B ? ? aB, # B ? ? b, # I4: B ? b ?, a/b I7: B ? b ?, # I8: B ? a B ?, a/b I9: B ? a B ?, # I3,6: B ? a ? B, a/b/# B ? ? aB, a/b/# B ? ? b, a/b/# I4,7: B ? b ?, a/b/# I8,9: B ? a B ?, a/b/# 合并为 合并为 合并为 LALR(1)分析 对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。 合并同心集的几点说明 同心集合并后心仍相同，只是超前有哪些信誉好的足球投注网站符集合为各同心集超前有哪些信誉好的足球投注网站符的和集 合并同心集后转换函数自动合并 LR(1)文法合并同心集后也只可能出现归约-归约冲突，而没有移进-归约冲突 合并同心集后可能会推迟发现错误的时间，但错误 出现的位置仍是准确的 合并同心集后 二义性文法在LR分析中的应用 对于某些二义文法，可以人为地给出优先性和结合性的规定，从而可以构造出比相应非二义性文法更优越的LR分析器 P149-151 LR(0),SLR(1),LR(1),LR(k),LALR(1) LR(0) SLR(1): 生成的LR(0)项目集如有冲突，则根据非终结符的FOLLOW集决定 LR(1)、LR(k): 项目由 心与向前有哪些信誉好的足球投注网站符组成，有哪些信誉好的足球投注网站符长度为1或k LALR(1): 对LR(1)项目集规范族合并同心集 结论 一个文法是LR(0)文法，一定也是SLR(1)文法，也是LR(1)文法。反之不一定成立。 任何一个二义性文法都不是LR类文法，也不是一个算符优先文法或LL(k)文法。 LALR(1)文法一定是LR(1)文法，反之不一定成立。 LR(1)分析法强于LALR(1)分析法，而LALR(1)分 析法强于SLR(1)分析法。 知识体系 考查重点： LR(0)、SLR(1)、LR(1)，LALR(1)项目集规范族的构造，识别活前缀的DFA的构造，分析表的构造，及输入串的分析。 LR(0)、SLR(1)、LR(1)、LALR(1)文法及其关系和区别 作业：P152 2 153 9 补充作业 1、设文法G[S]：(1) S → aAcBe(2) A → b(3) A → Ab(4) B → d (1)构造它的LR(1)分析表 (2) 输入串abbcde#的分析过程 2、设文法G[S]: S→BB B→aB|b 构造此文法的LR（0）项目集族，并写出识别活前缀的DFA； 构造LR（0）分析表，写出输入串aabab的分析过程。 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * NFA for Viable Prefixes in Detail (7) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T e e e e E e e e e e e T E ? T.+E T T ? (E.) E T ? (E). ) NFA for Viable Prefixes in Detail (8) T ? . (E) T ? (.E) ( S’ ? E. E