CLR (1) 分析

引言

在本文中，我们将详细解释CLR(1)分析器的概念及其工作示例。

什么是CLR (1) 分析器？

CLR指的是规范前瞻。CLR分析使用LR(1)项的规范集合来构建CLR(1)分析表。与SLR(1)分析相比，CLR(1)分析表产生更多的状态。

在CLR(1)中，我们只将归约节点放置在超前符号中。

CLR (1) 分析中涉及的各种步骤

• 对于给定的输入字符串，编写一个上下文无关文法
• 检查文法的歧义性
• 在给定的文法中添加增广产生式
• 创建LR(0)项的规范集合
• 绘制数据流图 (DFA)
• 构造一个CLR (1) 分析表

LR (1) 项

LR(1)项是LR(0)项和超前符号的集合。

LR(1)项 = LR(0)项 + 超前

超前用于确定放置最终项的位置。

超前总是为参数产生式添加$符号。

示例

CLR ( 1 ) 文法

添加增广产生式，在G中每个产生式的第一个位置插入'•'符号，并添加超前。

I0 状态

将增广产生式添加到 I0 状态并计算闭包

I0 = Closure (S` → •S)

将所有以S开头的产生式添加到I0状态，因为"."后跟非终结符。所以，I0状态变为

I0 = S` → •S, $
        S → •AA, $

将所有以A开头的产生式添加到修改后的I0状态，因为"."后跟非终结符。所以，I0状态变为。

I0=  S` → •S, $
        S → •AA, $
        A → •aA, a/b
        A → •b, a/b

I1= Go to (I0, S) = closure (S` → S•, $) = S` → S•, $
I2= Go to (I0, A) = closure ( S → A•A, $ )

将所有以A开头的产生式添加到I2状态，因为"."后跟非终结符。所以，I2状态变为

I2= S → A•A, $
       A → •aA, $
       A → •b, $

I3= Go to (I0, a) = Closure ( A → a•A, a/b )

将所有以A开头的产生式添加到I3状态，因为"."后跟非终结符。所以，I3状态变为

I3= A → a•A, a/b
       A → •aA, a/b
       A → •b, a/b

Go to (I3, a) = Closure (A → a•A, a/b) = (与I3相同)
Go to (I3, b) = Closure (A → b•, a/b) = (与I4相同)

I4= Go to (I0, b) = closure ( A → b•, a/b) = A → b•, a/b
I5= Go to (I2, A) = Closure (S → AA•, $) =S → AA•, $
I6= Go to (I2, a) = Closure (A → a•A, $)

将所有以A开头的产生式添加到I6状态，因为"."后跟非终结符。所以，I6状态变为

I6 = A → a•A, $
       A → •aA, $
       A → •b, $

Go to (I6, a) = Closure (A → a•A, $) = (与I6相同)
Go to (I6, b) = Closure (A → b•, $) = (与I7相同)

I7= Go to (I2, b) = Closure (A → b•, $) = A → b•, $
I8= Go to (I3, A) = Closure (A → aA•, a/b) = A → aA•, a/b
I9= Go to (I6, A) = Closure (A → aA•, $) = A → aA•, $

绘制 DFA

CLR (1) 分析表

产生式编号如下

CLR(1)分析表中移进节点的放置与SLR(1)分析表相同。唯一的区别在于归约节点的放置。

I4包含驱动(A → b•, a/b)的最终项，因此action {I4, a} = R3，action {I4, b} = R3。
I5包含驱动(S → AA•, $)的最终项，因此action {I5, $} = R1。
I7包含驱动(A → b•,$)的最终项，因此action {I7, $} = R3。
I8包含驱动(A → aA•, a/b)的最终项，因此action {I8, a} = R2，action {I8, b} = R2。
I9包含驱动(A → aA•, $)的最终项，因此action {I9, $} = R2。

列出SLR(1)和CLR(1)分析器之间的一些区别

以下是SLR(1)和CLR(1)分析器之间的区别

关于CLR (1) 分析表的常见问题

1. 列出构造CLR (1) 分析表的步骤？

答案

• 在设计分析表的第一步中，定义一个增广文法。
• 在收集 LR(1) 项之后查找项。
• 在设计CLR分析表的这一步中，定义2个函数
• goto(): 它包含终端的集合。
• action(): 它包含非终端的集合。
• 在最后一步中，使用栈实现分析算法来管理状态和输入符号。

2. 增广文法是什么意思？

回答: 增广文法是一种新的文法G′，它包括一个新的产生式和新的起始标记，这有助于更有效地管理分析过程。

例如

S′ → S 以及给定文法G的所有其他产生式。

扩展文法的主要目的是引入唯一的起始位置并显式处理输入的结束标记。

3. CLR分析器是什么意思？

回答: CLR分析器使用LR(1)项，其中包括前瞻符号。与LR(0)和SLR分析器相比，它具有更多的冲突，这使其更加强大并能够处理更广泛的文法。