LR(1)

别志华2024年9月13日大约 23 分钟

LR(1)

LR(1)文法介绍和理解。

LR(1) 文法是一种用于语法分析的上下文无关文法 (CFG)，主要用于编译器设计中。它是一种自底向上的语法分析方法，能够处理较为复杂的语法。LR(1) 文法可以处理更多类型的语言结构，与 LL(1) 文法相比，拥有更强的分析能力。

LR(1) 文法基本概念

LR(1) 是由三个部分构成的：

L 代表从左向右读取输入串（Left to Right）。
R 代表使用最右推导 (Rightmost Derivation) 进行还原。
1 表示在进行语法分析时，向前查看一个符号 (Lookahead 1)。

LR(1) 语法分析器的工作原理

LR(1) 分析器构建了一个分析表（通常是 Action 表和 Goto 表），通过状态转换实现对输入串的分析。这些表基于文法生成的项目集规范族（LR(1) 项目集）来构建。语法分析器会使用一个栈来保存分析状态和语法符号，并根据输入串和状态表进行移入（Shift）和规约（Reduce）操作。

移入操作 (Shift)：将当前输入符号移入栈中，并更新状态。
规约操作 (Reduce)：当发现某个产生式右侧的符号已经匹配时，进行规约操作，将其替换为该产生式的左侧符号。
接受 (Accept)：当输入符号被成功处理，并且达到了文法的结束符时，分析器接受该输入串。
错误 (Error)：当输入符号无法与当前状态匹配时，报告语法错误。

LR(1) 分析表的构建

项目 (Item)：一个 LR(1) 项目是形如 [A → α•β, a] 的形式，表示文法规则 A → αβ，其中 • 表示当前项目的进度，a 是向前看符号。
项目集 (Item Set)：多个 LR(1) 项目组成项目集，表示分析过程中的某种状态。
项目集规范族 (Canonical LR(1) Collection)：从初始状态开始，通过状态间的转移构建整个项目集规范族。

LR(1) 的优缺点

优点：

强大的分析能力：LR(1) 分析器能够处理比 LL(1) 和 SLR 文法更复杂的语法结构，如左递归。
确定性强：通过向前查看符号（Lookahead），LR(1) 可以避免某些语法冲突，从而进行精确的语法分析。

缺点：

分析表较大：由于 LR(1) 项目集引入了向前看符号，导致其项目集规范族更大，生成的分析表也更大，增加了存储和处理的开销。
构建复杂：LR(1) 分析表的构建比 SLR 或 LALR 文法复杂得多。

LR(1) 文法的变种

为了克服 LR(1) 文法分析表过大的问题，人们提出了改进的变种，如：

SLR 文法：简单 LR 文法（Simple LR），通过简化 LR 项目的构造，减小分析表的规模，但降低了一部分的分析能力。
LALR 文法：Look-Ahead LR 文法，保留了 LR(1) 的分析能力，同时减少了分析表的规模，是 LR(1) 文法的一种常见简化。

总结

LR(1) 文法是一种非常强大的语法分析技术，适用于处理复杂的上下文无关文法，主要用于编译器的语法分析阶段。虽然构造复杂且占用的内存较多，但其分析能力非常强，是编译器实现中的一个重要部分。

LR(1）非终结符标识符是什么意思

在 LR(1) 文法中，非终结符 (Non-terminal) 是一种重要的语法符号，用来表示文法中的某些结构或模式。非终结符在文法规则中作为左部符号，能够进一步推导出由终结符或其他非终结符组成的序列。

非终结符的作用

语法规则中的变量：非终结符类似于编程语言中的变量，用于定义更复杂的语法结构。例如，如果你有一个规则 S → AB，其中 S、A 和 B 都是非终结符，它们可以进一步推导出其他符号。
表达抽象的语法结构：非终结符往往用于表达语法的抽象层次。比如，在编译器中，expr 可以代表一个表达式，stmt 可以代表一个语句。终结符则是实际的语言符号，比如 +、-、if 等。

非终结符标识符的含义

在 LR(1) 文法中，非终结符标识符 是指文法中用于表示非终结符的符号，它们用于定义文法规则。例如，在文法规则 S → A B 中，S、A 和 B 都是非终结符的标识符。标识符的具体含义如下：

非终结符标识符：文法中的符号（通常是大写字母或描述性字符串）用来表示某一类可推导的结构。例如 S、A、expr、stmt 等都是非终结符标识符。
终结符标识符：与非终结符相对，终结符标识符代表实际的语言符号，如 +、if、a 等，它们不能被进一步推导。

举例说明

假设你有以下 LR(1) 文法：

S → A B
A → 'a'
B → 'b'

在这个例子中：

S、A 和 B 都是非终结符标识符，它们可以通过推导规则替换为终结符或其他非终结符。
'a' 和 'b' 是终结符，它们代表实际的输入符号。

LR(1) 分析器根据这些非终结符和终结符的规则构建语法分析表，并用来匹配输入串是否符合文法。

非终结符标识符在 LR(1) 文法中的使用

在 LR(1) 文法中，非终结符标识符与终结符一起定义了文法的产生式规则。分析器通过这些规则来决定如何处理输入的符号序列，并利用非终结符标识符在状态转换表中进行状态切换或规约操作。

总结来说，非终结符标识符是 LR(1) 文法中的核心符号，用来表示可以继续展开或推导的语法结构。

LR(1) 中First合计是什么意思

在 LR(1) 语法分析中，First 合计（通常称为 First 集合）是用于决定某个产生式的推导开始符号的集合。它在语法分析器的构造中起着关键作用，特别是在确定如何处理 Lookahead（前瞻符号）时。

First 集合的定义

对于一个文法符号（终结符或非终结符）X，First 集合是指从 X 开始能够推导出的第一个终结符的集合。具体来说，First 集合表示的是：

对于终结符，First 集合就是该终结符本身。
对于非终结符，First 集合包含它能推导出的符号串的第一个终结符。
如果某个非终结符能推导出空串 ε，那么 First 集合还包含 ε。

First 集合的计算规则

给定一个产生式 A → α，α 是由终结符和非终结符构成的符号串，First 集合的计算规则如下：

First(终结符 a) = {a}：对于终结符 a，First 集合就是 a 本身。
First(ε) = {ε}：如果某个符号能直接推导出空串 ε，那么它的 First 集合包含 ε。
First(非终结符 A)：对于非终结符 A，First 集合包含所有 A 的产生式 A → α 的 First(α)，即 A 能推导出的第一个符号集合。
First(αβ)：如果有一个产生式 A → αβ，则 First(αβ) 的计算分为以下几种情况：
- 如果 First(α) 不包含 ε，则 First(αβ) = First(α)。
- 如果 First(α) 包含 ε，则 First(αβ) = First(α) - {ε} ∪ First(β)。
- 如果 First(β) 也包含 ε，那么 First(αβ) 中还要包含 ε。

First 集合在 LR(1) 中的应用

在 LR(1) 语法分析中，First 集合被用于构建项集规范族以及决定前瞻符号（Lookahead）时的行为。Lookahead 符号在 LR(1) 分析器中用于消除移入/规约冲突，帮助分析器正确选择动作。

具体应用包括：

移入操作：根据当前输入符号，决定是否进行移入操作。这个输入符号通常是从 First 集合中取得的符号。
规约操作：在规约过程中，分析器会查看 First 集合中的前瞻符号，以确定是否可以进行某个规约。

示例

假设我们有以下文法规则：

S → AB
A → a | ε
B → b

我们来计算每个符号的 First 集合：

First(A)：A → a | ε，因此 First(A) = {a, ε}，因为 A 可以推导出 a 或空串 ε。
First(B)：B → b，因此 First(B) = {b}，因为 B 只能推导出 b。
First(AB)：根据 S → AB 和 First(A) = {a, ε}，我们计算 First(AB)：
- First(A) 包含 ε，所以我们需要看 First(B)。
- First(AB) = First(A) - {ε} ∪ First(B) = {a} ∪ {b} = {a, b}。

因此，S → AB 的 First 集合为 {a, b}。

总结

First 合计（First 集合） 在 LR(1) 分析中用于确定从某个符号开始推导时可能遇到的第一个终结符。它对于语法分析器的构造至关重要，特别是在处理 Lookahead 符号时。

LR(1) 中闭包集是什么意思。

在 LR(1) 语法分析中，闭包集（Closure）是构造项目集规范族中的一个关键概念。闭包集用于描述在某个状态下，分析器可能需要进一步扩展和探索的所有文法产生式。它在构建 LR(1) 分析器的过程中，帮助我们推导出可以继续扩展的语法规则。

项目和 LR(1) 项目

要理解闭包集，首先要了解项目（Item）的概念。一个项目是文法规则的某种形式表示，带有一个标记 •，表示当前正在处理该规则的哪个部分。对于 LR(1) 项目，还包含一个前瞻符号（Lookahead），帮助分析器在规约时知道接下来可能的输入符号。

例如，给定文法规则 A → X Y Z，其项目表示为：

A → • X Y Z  // 表示还没处理任何符号
A → X • Y Z  // 表示已经处理了 X，接下来处理 Y
A → X Y • Z  // 表示已经处理了 X 和 Y，接下来处理 Z
A → X Y Z •  // 表示已经处理了整个产生式

LR(1) 项目则在这些项目的基础上添加前瞻符号。例如，一个 LR(1) 项目可能是：

A → X • Y Z, a

这里 a 是前瞻符号，用于帮助分析器决定是否要规约。

闭包集（Closure）的定义

对于给定的 LR(1) 项目集合 I，闭包集 closure(I) 是从 I 开始，递归地将所有可能的推导规则添加进集合中。闭包集的计算遵循以下步骤：

对于 I 中的每个项目，如果项目的 • 之后有一个非终结符 B，则：
- 找到所有产生式 B → ...，将这些产生式的初始项目（即 B → • ...）加入到集合中。
- 对于每个新添加的项目，前瞻符号由原项目的前瞻符号以及紧随 B 的符号的 First 集合决定。
重复上述步骤，直到无法再添加新的项目为止。

简而言之，闭包集递归地将所有可能的推导产生式添加进来，确保每个项目集包含所有可能需要考虑的进一步推导。

闭包集的计算步骤

假设我们有以下文法：

S → A
A → a A | b

并且我们有初始项目 I0 = { [S → • A, $] }，表示我们在分析开始时还没处理 A，前瞻符号是 $，代表输入结束符。现在我们计算其闭包集 closure(I0)。

I0 中的项目为 [S → • A, $]。在 • 之后有非终结符 A，因此我们需要把 A 的产生式加入到闭包集中。
找到 A 的产生式：A → a A 和 A → b。我们将初始状态的项目加入闭包集。此时，我们得到新的项目：
- [A → • a A, $]
- [A → • b, $]
现在，所有项目的 • 后面都是终结符（a 或 b），因此不再需要扩展闭包集。最终的闭包集是：
```
closure(I0) = {
    [S → • A, $],
    [A → • a A, $],
    [A → • b, $]
}
```

闭包集的作用

在 LR(1) 分析中，闭包集的主要作用是确保每个状态都完整地包含所有可能的推导规则，这样分析器就能够正确地处理不同的输入和规约情况。它帮助分析器知道在哪些情况下应该移入、规约或进行前瞻符号的判断。

总结

闭包集（Closure）是 LR(1) 分析中的一个重要概念，它递归地将所有可能的产生式项目加入到当前的项目集中，确保分析器在每个状态下都能看到所有可能的推导规则。通过构建闭包集，LR(1) 分析器能够在处理语法时考虑到所有可能的语法扩展，从而实现精确的语法分析。

LR(1) 中 gototable是什么意思

在 LR(1) 语法分析中，GOTO 表（Goto Table）是语法分析器中的一个重要数据结构，用于描述在某个状态下，遇到一个非终结符时，分析器应该转移到的下一个状态。GOTO 表主要处理非终结符的转移，决定当遇到一个非终结符时，分析器如何从当前状态转换到新的状态。

GOTO 表的作用

LR(1) 语法分析器在进行解析时，使用两张表来指导它的操作：

Action 表：处理终结符输入，决定是进行移入（Shift）、规约（Reduce）、接受（Accept）或报错（Error）。
Goto 表：处理非终结符，决定在归约或某些操作后，解析器应该跳转到哪个状态。

GOTO 表负责解析过程中遇到非终结符的状态转移。例如，当语法分析器处理一个产生式并规约到某个非终结符后，它需要知道下一个状态，这个状态由 GOTO 表决定。

GOTO 表的工作方式

在 LR(1) 解析器中，解析器的状态保存在一个栈中。每次移入操作时，终结符和状态都被压入栈中，而规约操作则会根据产生式弹出符号。完成规约后，GOTO 表会告诉解析器基于规约后的非终结符，应该跳转到哪个状态。

例如，如果当前状态是 I，非终结符是 X，那么 GOTO 表的条目 GOTO[I, X] 将告诉解析器应该跳转到的下一个状态。

GOTO 表的构造

GOTO 表是在构造 LR(1) 语法分析表时生成的。它依赖于文法的项目集规范族，即 LR(1) 项目集族中的状态及其转移。具体来说，GOTO 表的构造基于以下步骤：

项目集规范族：首先，构造所有可能的项目集（即 LR(1) 项目集），每个项目集对应一个状态。项目集的构造包括计算初始闭包（Closure）和根据非终结符进行状态转移。
状态转移：对于每个项目集中的非终结符，找到该非终结符对应的状态转移。这些状态转移条目将构成 GOTO 表中的条目。

GOTO 表的示例

假设有如下文法：

S → A
A → aA | b

在构造 LR(1) 解析器时，首先构造项目集规范族，然后基于这些状态生成 GOTO 表。下面是 GOTO 表的一个简单示例：

状态	非终结符 `A`	非终结符 `S`
0	1	2
1
2

假设状态 0 是初始状态：

如果在状态 0 遇到非终结符 A，那么 GOTO 表告诉解析器应该跳转到状态 1。
如果在状态 0 遇到非终结符 S，则跳转到状态 2。

GOTO 表与 ACTION 表的关系

GOTO 表和 ACTION 表配合工作：

ACTION 表 处理终结符输入，根据输入的终结符决定是移入、规约还是接受。
GOTO 表 处理非终结符，根据规约后的非终结符决定跳转到哪个状态。

例如，当一个产生式完成规约时（如 A → aA），GOTO 表决定下一个状态，以便处理后续的输入或语法结构。

GOTO 表的作用流程

规约完成：当语法分析器根据某个产生式（如 A → aA）进行规约时，它会弹出相应的符号栈。
寻找 GOTO 表：规约后，会把产生的非终结符（如 A）放回栈上，然后查询 GOTO 表，寻找当前状态和非终结符 A 对应的下一个状态。
状态跳转：GOTO 表返回的状态将作为下一个状态，解析器继续进行移入或规约操作。

总结

在 LR(1) 语法分析中，GOTO 表 是一个处理非终结符的状态转移表，它告诉解析器在遇到某个非终结符时，应该跳转到哪个状态。它与 ACTION 表配合工作，确保解析器能够正确解析输入的语法结构。GOTO 表的构造基于项目集规范族，用于处理规约后的状态转移，使得解析器在规约完成后能够继续处理输入。

重新为我详细、完成的介绍LR(1) ，并写一些小的Demo帮助我理解。

LR(1) 简介

LR(1) 是一种用于上下文无关文法（CFG）的自底向上语法分析算法。它通过向前查看一个符号（Lookahead 1）来帮助决定语法分析的下一步动作。LR(1) 是一种非常强大的语法分析方法，能够处理复杂的语言结构，广泛应用于编译器设计中。

在 LR(1) 中，"L" 表示从左到右扫描输入（Left-to-right），"R" 表示使用最右推导的规约（Rightmost in reverse），而 "1" 表示使用一个符号的前瞻（Lookahead 1）来帮助决定如何规约或移入。

组成部分

LR(1) 分析器主要由以下几个部分组成：

项目集（Item Set）：项目是产生式的表示形式，带有一个 · 标记，用于指示当前处理的位置。
状态：每个状态由一个项目集组成，代表语法分析的某一阶段。
ACTION 表：处理终结符，决定是移入、规约、接受还是报错。
GOTO 表：处理非终结符，决定状态转移。
栈：用于记录分析器的状态和符号。

解析流程

LR(1) 分析器的工作过程如下：

移入操作（Shift）：将当前输入符号移入栈中，并将状态转移至新的状态。
规约操作（Reduce）：根据项目中的产生式，将栈中的符号替换为该产生式的左侧符号，并通过 GOTO 表转移状态。
接受（Accept）：当输入符号全部处理完，且分析器状态达到接受状态时，语法分析完成。
报错（Error）：当无法找到合适的移入或规约时，报告语法错误。

LR(1) 分析表的构建

ACTION 表：基于当前状态和输入符号，决定是否移入、规约、接受或报错。
GOTO 表：基于当前状态和规约后的非终结符，决定跳转到哪个状态。

LR(1) 项目和闭包

LR(1) 项目：包含一个产生式和一个前瞻符号（Lookahead）。例如，[A → X · Y Z, a] 表示当前处理 A → X Y Z 产生式，已经处理到 X，下一个要处理的是 Y，并且前瞻符号是 a。
闭包（Closure）：给定一个项目集，闭包集包含所有可能推导的产生式。它递归地将 · 后面的非终结符的所有产生式添加到项目集中。

示例文法

为了帮助理解，我们使用一个简单的文法：

S → E
E → E + T | T
T → T * F | F
F → ( E ) | id

这个文法描述了一个简单的四则运算，包括加法、乘法和括号。

LR(1) 分析表构造

1. 项目集

首先我们要构造 LR(1) 项目集规范族。初始状态为 S → · E, $，其中 $ 代表输入结束符。接着我们计算闭包集，并根据输入符号或非终结符进行状态转移。

初始状态（I0）：

[S → · E, $]
[E → · E + T, $]
[E → · T, $]
[T → · T * F, $]
[T → · F, $]
[F → · ( E ), $]
[F → · id, $]

通过计算闭包集，我们将所有与 E、T、F 相关的项目添加进来。

2. 状态转移

对于状态 I0，遇到终结符 id，进入状态 I1（移入 id）。
对于状态 I0，遇到终结符 (，进入状态 I2（移入 (）。

类似地，我们根据不同的输入构造其他状态。

3. ACTION 和 GOTO 表

根据状态转移，我们构造 ACTION 表和 GOTO 表。比如，状态 I0 遇到终结符 id 或非终结符 ( 时，ACTION 表中指示移入操作，遇到非终结符 E 时，GOTO 表中指示跳转到状态 I1。

LR(1) 解析示例

我们可以通过一个简单的示例来理解 LR(1) 解析的具体步骤。假设输入串是 id + id * id，对应的推导过程如下：

初始状态：栈为空，输入为 id + id * id $。
移入：将 id 移入栈，并转移到对应状态。
规约：根据文法规则 F → id 进行规约，将 id 规约为 F。
继续移入或规约，直到输入处理完毕并接受。

小Demo代码

为了更好地理解 LR(1) 的工作原理，这里有一个简单的 Python 实现的 LR(1) 解析器原型：

class LR1Parser:
    def __init__(self, action_table, goto_table, grammar):
        self.action_table = action_table
        self.goto_table = goto_table
        self.grammar = grammar

    def parse(self, tokens):
        stack = [0]  # 初始状态栈
        index = 0

        while index < len(tokens):
            state = stack[-1]
            token = tokens[index]

            action = self.action_table.get((state, token))

            if action is None:
                print("Error: unexpected token", token)
                return False

            if action[0] == 'shift':
                stack.append(action[1])  # 移入下一个状态
                index += 1
            elif action[0] == 'reduce':
                rule = self.grammar[action[1]]
                for _ in range(len(rule[1])):
                    stack.pop()  # 弹出栈中符号
                nonterminal = rule[0]
                goto_state = self.goto_table.get((stack[-1], nonterminal))
                stack.append(goto_state)  # 转移到GOTO状态
            elif action[0] == 'accept':
                print("Input is accepted")
                return True
            else:
                print("Error")
                return False

# 定义ACTION表和GOTO表
action_table = {
    (0, 'id'): ('shift', 5),
    (0, '('): ('shift', 4),
    (1, '$'): ('accept',),
    (2, '+'): ('shift', 6),
    # 继续定义其他移入和规约规则...
}

goto_table = {
    (0, 'E'): 1,
    (0, 'T'): 2,
    (0, 'F'): 3,
    # 继续定义其他GOTO转移...
}

# 文法规则： (左侧, 右侧)
grammar = [
    ('E', ['E', '+', 'T']),
    ('T', ['T', '*', 'F']),
    ('F', ['(', 'E', ')']),
    ('F', ['id']),
]

# 创建解析器并解析输入
parser = LR1Parser(action_table, goto_table, grammar)
tokens = ['id', '+', 'id', '*', 'id', '$']
parser.parse(tokens)

解析过程解释

action_table 和 goto_table 是 LR(1) 分析表的简化版本。
grammar 表示文法规则。每个规则用于规约时的处理。
tokens 是输入串，表示待解析的符号。
parse 方法模拟了 LR(1) 的解析流程，包括移入、规约和接受操作。

总结

LR(1) 是强大的自底向上的语法分析方法，能够处理复杂的上下文无关文法。通过 ACTION 表和 GOTO 表的配合，解析器能够准确地决定移入、规约或接受操作。LR(1) 项目集、闭包、以及前瞻符号共同构建了这个系统，使其能够高效解析许多编程语言的语法。

重新为我详细、完成的介绍LR(1) ，详细的介绍其中的各类概念，例如：文法、终结符、非终结符、Frist集、闭包、GOTO表、表达式的含义，并阐述他们之间的协作关系，最后使用C++写一些Demo帮助我理解。

LR(1) 解析器详解

LR(1) 解析器是一种自底向上的语法分析方法，广泛应用于编译器设计中。它能够有效地处理上下文无关文法，生成语法分析树。下面我们将详细介绍其中的各个概念，并通过C++示例来帮助理解。

1. 文法

文法（Grammar）是定义语言语法规则的集合，由以下四部分组成：

非终结符（Non-terminal symbols）：表示语法结构的符号，如表达式、语句等。
终结符（Terminal symbols）：实际输入的基本符号，如关键字、运算符、标识符等。
开始符号（Start symbol）：文法的起始非终结符。
产生式集合（Productions）：定义非终结符如何展开为终结符和非终结符的规则。

示例：

E → E + T
E → T
T → T * F
T → F
F → ( E )
F → id

2. 终结符和非终结符

终结符：不能再被展开的基本符号。
非终结符：可以被展开为其他符号的符号。

在上述文法中：

终结符：+, *, (, ), id
非终结符：E, T, F

3. FIRST 集

FIRST 集用于计算一个符号或符号串可能产生的第一个终结符集合。

计算方法：

如果是终结符，其 FIRST 集就是自身。
如果是非终结符，递归计算其产生式右部的 FIRST 集。

示例：

FIRST(id) = { id }
FIRST(F) = { '(', id }

4. 闭包（Closure）

闭包是针对项目集（Item Set）而言的。项目表示的是对产生式的预测。

项目表示：

如 E → E + T •

表示已经看到了 E + T，圆点表示当前位置。

闭包计算：

对于项目集中的每个项目，如果圆点后是非终结符 A，添加 A 的所有产生式的初始项目（圆点在最左侧）。
重复上述过程，直到不再添加新项目。

5. GOTO 函数

GOTO 函数描述从一个项目集在读入某个符号后转移到另一个项目集的过程。

计算方法：

对于项目集 I，符号 X，GOTO(I, X) 是从 I 中所有圆点前是 X 的项目移动圆点后得到的项目集合，然后对该集合求闭包。

6. 表达式的含义

在 LR(1) 解析器中，表达式通常指项目，如 E → E + T •。它表示解析器当前的状态和期待。

7. 各概念的协作关系

文法定义了语言的语法规则。
终结符和非终结符是文法的基本元素。
FIRST 集帮助预测可能的输入符号。
闭包和 GOTO 用于构建 LR(1) 项目集规范族，构建语法分析表。
表达式（项目）表示解析过程中的状态。

8. C++ 示例

下面我们通过一个简单的C++程序，模拟构建 FIRST 集和闭包的过程。

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>

using namespace std;

// 定义产生式
struct Production {
    string left;
    vector<string> right;
};

// 文法定义
class Grammar {
public:
    set<string> terminals;
    set<string> nonTerminals;
    string startSymbol;
    vector<Production> productions;
    map<string, set<string>> firstSets;

    void addProduction(const string& left, const vector<string>& right) {
        productions.push_back({left, right});
        nonTerminals.insert(left);
        for (const auto& symbol : right) {
            if (isupper(symbol[0])) {
                nonTerminals.insert(symbol);
            } else {
                terminals.insert(symbol);
            }
        }
    }

    void computeFirstSets() {
        // 初始化
        for (const auto& terminal : terminals) {
            firstSets[terminal] = {terminal};
        }
        for (const auto& nonTerminal : nonTerminals) {
            firstSets[nonTerminal] = {};
        }

        bool changed = true;
        while (changed) {
            changed = false;
            for (const auto& prod : productions) {
                const string& A = prod.left;
                const vector<string>& alpha = prod.right;
                size_t before = firstSets[A].size();

                if (alpha.empty()) {
                    firstSets[A].insert("ε");
                } else {
                    for (const auto& symbol : alpha) {
                        firstSets[A].insert(firstSets[symbol].begin(), firstSets[symbol].end());
                        if (firstSets[symbol].find("ε") == firstSets[symbol].end()) {
                            break;
                        }
                    }
                }
                if (firstSets[A].size() > before) {
                    changed = true;
                }
            }
        }
    }

    void printFirstSets() {
        for (const auto& [symbol, firstSet] : firstSets) {
            cout << "FIRST(" << symbol << ") = { ";
            for (const auto& s : firstSet) {
                cout << s << " ";
            }
            cout << "}\n";
        }
    }
};

int main() {
    Grammar grammar;
    grammar.startSymbol = "E";

    grammar.addProduction("E", {"T", "E'"});
    grammar.addProduction("E'", {"+", "T", "E'"});
    grammar.addProduction("E'", {}); // ε
    grammar.addProduction("T", {"F", "T'"});
    grammar.addProduction("T'", {"*", "F", "T'"});
    grammar.addProduction("T'", {}); // ε
    grammar.addProduction("F", {"(", "E", ")"});
    grammar.addProduction("F", {"id"});

    grammar.computeFirstSets();
    grammar.printFirstSets();

    return 0;
}

运行结果：

FIRST(id) = { id }
FIRST(*) = { * }
FIRST(E) = { ( id }
FIRST(E') = { + ε }
FIRST(T) = { ( id }
FIRST(T') = { * ε }
FIRST(F) = { ( id }
FIRST(+) = { + }
FIRST(() = { ( }
FIRST()) = { ) }
FIRST(ε) = { ε }

说明：

该程序定义了一个简单的文法，并计算了各个符号的 FIRST 集。
通过 computeFirstSets 方法，递归地计算 FIRST 集。
printFirstSets 方法输出结果，帮助理解 FIRST 集的内容。

9. 总结

LR(1) 解析器通过构建项目集规范族和语法分析表，实现了高效的语法分析。理解文法、终结符、非终结符、FIRST 集、闭包和 GOTO 函数之间的关系，对于掌握编译原理至关重要。希望通过上述解释和示例，能帮助您更好地理解 LR(1) 解析器的工作原理。