编译原理复习——语法分析(自底向上)3

LR(1)分析

在SLR(1)分析中我们虽然解决了部分问题可以将移进—规约或者规约—规约冲突解决。但是我们有时候会发现这个冲突有很多时候是无法解决的，利用SLR(1)方法是不可以解决这个问题的。

尽管 FOLLOW(A) 中包含了所有含 A 的句型中 A 后的 可能终结符，但 并不是每个 含有 A 的句型 中， A 的后 面都可以出现 Follow(A) 中的每一个符号 ，所以 SLR(1) 未能从根本上消除所有无效归约。

这时候我们需要引入的是一个更加强大的分析方法:LR(1)方法。

LR(1) 分析法的基本思想 在分析过程中，当试图用规则 A→α 归约栈顶的符号串α时，不仅应该查看栈中符号串δα，还应向 前扫描一个输入符号 a，只有当δAa 的确构成 文法 某一句型 的前缀时，才能用此规则进行归约。 LR(1) 方法按 每个具体的句型 设置展望信息。 如果存在如下的一些句型 …αAa… ， …βAb… ， …γAc… ，则 FOLLOW(A)={a,b,c} 处理到句型 …αA ，只当输入符号为 a 时归约 处理到句型 …βA ，只当输入符号为 b 时归约 处理到句型 …γA ，只当输入符号为 c 时归约 注意 LR （ 1 ）的基本思想是 对 非终结符的每个不同出现 求其后继符号 ，而不是给每个非终结符求其统一的 后继符号集 相关定义： LR(1) 项目 形如（ A→ α•β,a ）的二元式称为 LR(1) 项目 。其中， A→ αβ 是文法的一个产生式， a 是终结符，称为 向前 搜索符 LR(1) 项目 = LR(0) 项目 + 向前搜索符 注意 (A→ α•β,a) 的含义：预期当栈顶句柄 αβ 形成后，待 输入的符号为 a 。此时， α 在栈内， β 还未入栈，即 它展望了句柄后的一个符号 S’→ . S, # 的含义：若将 γ(S→ γ) 规约为 S ，必须面临输 入符号为 # 才可以 对于多数程序设计语言，向前展望一个符号就足以 决定归约与否，所以只研究 LR(1) LR(1) 项目集族的构造 1 拓展文法 , 同 LR(0)
2 将 S’→. S, # 作为 LR(1) 初始项目集的核
3 项目 I 的闭包 closure(I)
(1) I 的任何项目都属于 closure(I) ；
(2) 若 [A→ α. Bβ,a]∈ closure(I)， B→ γ 为一产生式，则对 ∀ b∈ FIRST( βa ) ， 如果 [ B→. γ,b ]∈ closure(I) 原来不在 CLOSURE(I) 中，则把它加进去
重复 (2) ，直到 CLOSURE(I)不 再扩大为止 例子：求出下列文法的Closure(I)
(0) S’→ S
(1) S→BB
(2) B→aB
(3) B→b
I={S’→ . S , # }
Closure(I)={ S’→ . S , #  S → . BB , #  B → . aB , a/b  B → . b , a/b } (3)  转换函数的构造 GO （ I ， X ） = CLOSURE （ J ） 其中： I 为 LR(1) 的项目集， X 为一文法符号 J={任 何形如 [A→α X •β , a ] 的项目 | [A→α • X β,a ] 属于 I} 在执行转换函数 GO 时，搜索符并不改变 LR(1) 分析表的构造 设 LR(1) 项目集族 C={I 0 ,I 1 ,…I n } (1) 若项目 [A→ α. aβ,b] 属于 I k 且 Go[ I k ,a]= I j ， a 为终结符，则置 Action[k,a]= S j ； (2) 若项目 [A→ α. ,a] 属于 I k ，置 Action[k, a]= r j， j 为产生式 A→ α 在文法中的编号； (3) 若项目 [S’→ S. ,#] 属于 I k ，则置 Action[k, # ]= acc ； (4) 若 Go[I k ,A]=I j ，则置 Goto[k, A ]= j ； (5)不 能用 (1) － (4) 条填入信息的空白格均填“出错标志” 这里给出一个例子： (0) S’→ S (1) S→ BB (2) B→ aB (3) B→ b

 在这里我们可以看到4状态和7状态  8状态和9状态他们只有向前搜索符是不一样的其他都是一样的，那么我们是不是可以把他们转换成一个状态然后把向前搜索符进行合并。

LALR(1) 分析法 LR(1) 分析法虽然可以解决一些 SLR(1) 方法无法解 决的冲突，但是对同一个文法而言，当向前看搜索 符不同时， LR(1) 方法使同一个项目集分裂为多个 项目集，从而 导致状态数目增加 ， 所需存储空间急 剧增加 为了克服 LR(1) 的这种缺点，考虑一种折中的方法 ―― LALR(1) 方法 对于同一个文法， LR(1) 分析表和 LR(0) 以及 SLR 分析表永远具有相同数目的状态 LALR 方法本质上是一种折中方法， LALR 分析表 比 LR(1) 分析表要小得多 ，能力也差一点，但它却 能对付一些 SLR(1) 所不能对付的情况 但是LR(1)文法合并同心集后也可能会出现新的冲突但是只 可能出现归约-归约冲突，而 没有移进-归约冲突 若构造的 LALR 分析表不存在冲突 ，则该文法称为 LALR(1) 文法。 最后总结部分详见： 自底向上分析部分总结_用编程写诗的博客-CSDN博客

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！