LALR (1) 分析

什么是 LALR 分析器？

LALR 指的是向前看 LR。 为了构造 LALR (1) 分析表，我们使用 LR (1) 项的规范集合。

在 LALR (1) 分析中，具有相同产生式但不同向前看的 LR (1) 项被组合以形成单个项集

LALR (1) 分析与 CLR (1) 分析相同，只是分析表不同。

创建 LALR 分析表的步骤

以下是创建 LALR 分析表的步骤列表。

• 在设计分析表的第一个步骤中，编写增广文法。
• 在收集 LR(1) 项之后查找项。
• 在设计分析表的最后一步中，定义 2 个函数
  • goto(): 它包含终端的集合。
  • action(): 它包含非终端的集合。

示例

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

I0 状态

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

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•, $

如果我们分析，则 I3 和 I6 的 LR (0) 项相同，但它们的向前看不同。

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

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

显然，I3 和 I6 在它们的 LR (0) 项中相同，但在向前看方面不同，因此我们可以将它们组合并称为 I36。

I36 = { A → a•A, a/b/$
       A → •aA, a/b/$
       A → •b, a/b/$
        }

I4 和 I7 相同，但它们的向前看不同，因此我们可以将它们组合并称为 I47。

I47 = {A → b•, a/b/$}

I8 和 I9 相同，但它们的向前看不同，因此我们可以将它们组合并称为 I89。

I89 = {A → aA•, a/b/$}

绘制 DFA

LALR (1) 分析表

LALR 分析表的优点

以下是分析表的优点列表。

• 处理大型文法：与任何其他分析器相比，LALR 分析器可以处理更大的文法类。
• 高效：它在时间和空间复杂度方面更有效。
• 构建抽象语法树：它用于构建输入源代码的抽象语法树。

LALR 分析表的局限性

以下是分析表的局限性列表。

• 复杂：构建 LALR 分析器需要大量的精力和技巧，因为它可能很大且复杂。
• 开销：分析过程可能会给编译器带来开销，这也会影响性能。
• 受限的向前看：在 LALR 分析器中，使用有限数量的向前看可能导致某些情况下的分析错误。

LALR 分析器的应用

LALR 分析器在编译器设计中有很多应用。

• 分析编程语言：它通常用于分析源代码。 它可以高效地在更短的时间内处理各种文法。
• 产生错误消息：LALR 分析器用于生成错误消息。 它检查位置和输入符号，如果源代码中存在语法错误。
• 灵活性：它很灵活，可以处理特定的文法规则。 它适用于各种编译器设计。

有关 LALR 分析表常见问题解答

1. LALR 在分析过程中处理的主要目标是什么？

答案：LALR 处理用于将输入符号序列减少到输出左侧的非终结符。 它可以减小堆栈的大小并简化分析过程。

2. 列出 LALR 分析器的类型？

答案：以下是 LALR 分析器的类型

• 简单分析器：它使用简单的分析表来构建算法。 它只能处理有限的文法类，因此功能较弱。
• 规范分析器：它使用复杂的分析表构造算法来更有效地处理更大的文法类。