理：五 语法分析——自下而上分析(唐益明).ppt

SLR（1）的局限 Follow 集包含了在任何句型中跟在 R 后的符号但没有严格地指出在一个特定的推导里哪些符号跟在 R后。所以需要扩充状态以包含更多的信息：Follow 集的哪些部分 才是进到该状态最恰当的归约依据. 处在状态 2时，试图构建句子有两条路： 1.S ?L = R 或 2.S ? R ? L. 如下一符号是 =, 那就不能用第二个选择，必须用第一个,即移进. 只有下一个符号是#时才能归约. 尽管 = 属于 Follow(R) ，那是因为一个 R 可以出现在别的上下文中，在现在这个特定的情况，它不合适,因为在用S ? R ? L推导句子时, = 不能跟在R后。 非 LR(0),非SLR(1)举例 (0) S’→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e I5: S →ae.c I7: S →be.d A →e． A →e． S’==S==aAd==aed S’==S==bAc==bec S’==S==aec S’==S==bed ae是活前缀 be是活前缀 aAc不是规范句型 , bAd不是规范句型 不作无效归约 ？信息－ 在特定的规范推导中，哪些输入符号能跟在句柄之后？ LR(1)的项目集C和函数GO I0: S’??S, # S??BB, # B??aB, a/b B? ?b, a/b S I1: S’?S ?, # B I2: S?B ? B, # B??aB, # B? ?b, # a I3: B?a?B, a/b B??aB, a/b B? ?b, a/b b I4: B? b ?, a/b B I5: S?BB?, # a I6: B?a?B, # B??aB, # B? ?b, # b I7: B? b ?, # B I8: B? aB?, a/b a b a I9: B? aB?, # B b I0: S’??S, # S??BB, # B??aB, a B??aB, b B? ?b, a B? ?b, b LR(1)分析表为: 例: 按上表对aabab进行分析 步骤 状态 符号 输入串 0 0 # aabab# 1 03 #a abab# 2 033 #aa bab# 3 0334 #aab ab# 4 0338 #aaB ab# 5 038 #aB ab# 6 02 #B ab# 7 026 #Ba b# 8 0267 #Baa # 9 0269 #BaB # 10 025 #BB # 11 01 #S # acc 例: 按上表对abab进行分析 步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB # 8 025 #BB # 9 01 #S # acc 定义：如果采用同心项目集合并方法，进行合并后的文法G的LR(1)项目集规范族，没有LR(1)项目冲突，则称文法G为LALR(1)文法。 5.3.5 规范LALR(1)分析 LR(1)语法分析表的状态数量很大 SLR(1)语法分析表的分析能力较弱 LALR(1)是实践中常用的方法 状态数量和SLR(1)的状态数量相同 能够方便地处理大部分常见的程序设计语言的构造 定义：同心项目集：如果除去有哪些信誉好的足球投注网站符之后，这两个集合是相同的，则我们两个LR(1)项目集具有相同的心。 LR(1)语法分析表的合并 状态4和7仅仅向前有哪些信誉好的足球投注网站符不同。 当前状态为4时：如果后面是a或者b时，应该归约；后面是#时，应该报错。当前状态为7时，分析动作正好反过来。 如果我们将4和7中的项合并得47，那么在所有情况都归约。 新的语法分析过程会在原来报错时进行归约；但是最终总