C 语言 LL(1) 解析器程序

在本文中，我们将讨论 C 语言中的 **LL(1) 解析器** 程序。但在讨论 LL(1) 解析器的实现之前，我们需要了解 LL(1) 解析器及其规则。

什么是 LL(1) 解析器？

LL(1) 是一种 **自顶向下解析器**。它处理 LL(1) 类文法。第一个 **"L"** 表示输入是从 **左** 到 **右** 扫描的，第二个 **"L"** 表示输入是 **从左** 推导的，而 **"1"** 表示用于做出决定的前看符号的数量。

在创建 **LL(1)** 解析表之前，我们必须确定文法是否为 **LL(1)**。

构建 LL(1) 解析表的规则

我们可以使用以下规则来理解 C 语言中的 **LL(1) 解析**。

步骤 1：文法求值

• 首先，检查以 **BNF (巴克斯范式)** 编写的给定上下文无关文法。
• 确保文法是 **LL(1) 可解析** 且 **不是左递归** 的。可以使用适当的转换来消除 **左递归**。
• 将文法格式化为对分析有用的 **格式**，例如解析规则表或 **产生式规则** 的集合。

步骤 2：FIRST 集和 FOLLOW 集

• 对于文法中的每个 **非终结符**，确定其 **FIRST 集。非终结符 **A** 的 **FIRST 集** 包含所有可以派生自 **A** 的字符串的 **终结符**。
• 对于文法中的每个非终结符，确定其 **FOLLOW 集。非终结符 A 的 **FOLLOW 集** 包含所有可以紧跟派生自 **A** 的字符串的终结符。

步骤 3：如何构建解析表

• 在 **A** 是 **非终结符** 且 α 是由终结符和/或非终结符组成的字符串的每种情况下
• 对于 **FIRST(α)** 中的每个终结符 **t**，将 **A->α** 添加到表中的 **[A, t]** 条目。
• 如果 **ε (epsilon)** 在 **FIRST(α)** 中，则对于 **FOLLOW(A)** 中的每个终结符 **t**，将 **A -> α** 添加到表中的 **[A, t]** 条目。
• 如果 **FIRST()** 中包含 **ε** 且 **FOLLOW(A)** 中包含 **$ (输入结束符)**，则将 **A->** 添加到表项 **[A, $]**。
• 如果解析表中存在任何冲突（同一单元格中有多个条目），则该文法不是 **LL(1)** 的，不能使用 **LL(1) 解析**。

步骤 4：如何使用解析表

• 首先，从头开始创建一个 **解析栈**，并将文法的开始符号放入其中。
• **读取** 当前的输入标记。
• 使用当前 **输入标记** 作为 **列索引**，并使用栈顶作为行索引来查询 **解析表**。
• 如果表项为空或包含错误，则表示输入存在语法 **错误**。
• 如果表项包含产生式 **A -> α**，则将 **A** 从栈中 **弹出**，然后按相反顺序将其 **压入** 栈中。

C 语言 LL(1) 解析表示例程序

在此程序中，程序读取一个名为 **"text.txt"** 的文件来读取文法。Epsilon 由符号 **"^"** 表示。程序认为输入文法为 **LL(1)**。

text.txt

程序

输出

FIRST OF E: ( t
FIRST OF A: + ^
FIRST OF T: ( t
FIRST OF B: * ^
FIRST OF F: ( t

FOLLOW OF E: $ )
FOLLOW OF A: $ )
FOLLOW OF T: + $ )
FOLLOW OF B: + $ )
FOLLOW OF F: * + ) $ 

FIRST OF TA: ( t
FIRST OF +TA: + ^
FIRST OF FB: ( t
FIRST OF *FB: * ^
FIRST OF t: t
FIRST OF (E): (

(   )   *   +   t   $
E           TA              TA
A           ^   ^   ^   +TA   ^   
T           FB              FB
B           ^   ^   *FB   ^   ^   
F           (E)              t