NOTE
这笔记我自己看就好了，不适合考试复习

一、词法分析#

编译原理中，词法分析器是第一个把字符流变成有意义单元的组件。它的理论基础是正则语言与有限自动机。词法分析是编译原理中最优雅的部分之一是，它把一个看似工程化的任务，变成了正则表达式、NFA、DFA 三者之间的等价变换。

1. 词法单元、词素与模式#

词法分析器的输入是源程序的字符流，输出是 token 流。
前置概念：

词法单元 / token：一个 token 类，例如 ID、NUM、IF。
词素 / lexeme：源程序中实际出现的字符串，例如 foo、42。
模式 / pattern：描述一个 token 类所有合法词素的规则，通常用正则表达式表示。

一个 token 可以看作二元组：

\langle \text{token class}, \text{attribute value} \rangle

例如输入 foo 可能被识别为：

\langle ID, \text{symbol table ptr to "foo"} \rangle

也就是说，Token 通常可以带一个 attribute（属性），告诉后面阶段这个 Token 对应的具体信息。

2. 正则表达式与正则定义#

正则表达式是描述词法模式的标准工具。
设 $\Sigma$ 是有限字母表。正则表达式最基本只有三种运算：

r | s：二选一
rs：先匹配 r, 再匹配 s
r*：r 重复 0 次或多次

NOTE
这里先提一下 $\epsilon$ ， $\epsilon$ 表示空串，里面什么字符都没有（长度为0），但是是一个合法字符串，这里和空集 ∅ 是两回事（一个字符串都没有）

优先级为：* > 连接 > |，括号可以改变优先级。常用扩展如 +、?、字符类 [a-z] 都可以归约到上述基本运算。

3. 有限自动机#

3.1 NFA 与 DFA#

NFA 的非确定并非随机。其实它只是说，同一输入可能有多条路径，只要存在一条接受路径即可。NFA 是非确定的选择，不是概率。

3.2 正则表达式 → NFA：Thompson 构造#

Thompson 构造法用结构归纳把正则表达式转换为 NFA。

基本构造：

$\varepsilon$ ：一个开始状态，一个接受状态，一条 $\varepsilon$ 边。
$a$ ：一个开始状态，一个接受状态，一条 $a$ 边。

复合构造：

并 $r|s$ ：新建开始状态，用 $\varepsilon$ 边连到两个子 NFA 的开始；两个子 NFA 的接受状态各用 $\varepsilon$ 边连到新建接受状态。
连接 $rs$ ： $r$ 的接受状态用 $\varepsilon$ 边连到 $s$ 的开始。
闭包 $r^*$ ：新建开始状态和接受状态；新开始状态用 $\varepsilon$ 边连到 $r$ 的开始和新接受状态； $r$ 的接受状态用 $\varepsilon$ 边连到 $r$ 的开始和新接受状态。

画画 a(b|c)* 的 NFA 结构练习一下

3.3 NFA → DFA：子集构造#

NFA 便于构造，但模拟效率低；DFA 判定每个字符只需一次状态转移。因此需要把 NFA 转换为 DFA。
核心思想：DFA 的一个状态对应 NFA 的一个状态集合。

[!question] 为什么 DFA 可以把 NFA 的整个状态集合当成一个状态？
比如当前读入 a，NFA 的状态可能从 q1, q2, q3 变到 q2, q4，我们并不需要知道 NFA 到底在哪个状态，因为 NFA 本来就不要求我们做出唯一选择，我们只需要记住读到这里时，所有可能到达的状态有哪些。所以 DFA 把 {q1, q2 ,q3} 当做一个状态，然后 {q1, q2 ,q3} —a—> {q2, q4}，即 DFA 把 NFA 的多条可能路径压缩成了一个确定的集合状态，这便是子集构造

定义两个操作：

$\varepsilon\text{-closure}(s)$ ：从状态 $s$ 只经过 $\varepsilon$ 边可达的所有状态集合，包括 $s$ 自身（因为他们不消耗输入字符）
$\text{move}(T, a)$ ：从集合 $T$ 中任意状态经过输入 $a$ 可达的状态集合。

子集构造算法：

1
Dstates = { ε-closure(s0) }
2
while 存在未标记状态 T in Dstates
3
{
4
    mark T
5
    for (a : Σ)
6
    {
7
        U = ε-closure(move(T, a))
8
        if U not in Dstates
9
            add U unmarked
10
        Dtran[T, a] = U
11
    }
12
}

最坏情况下，DFA 状态数可能是 NFA 状态数的指数级（ $2^n）$ 。但真实编程语言的词法模式通常不会触发最坏情况，本质就是子集构造只会生成实际从初始状态出发、沿着输入字符能够到达的那些状态集合

3.4 DFA 最小化#

子集构造得到的 DFA 可能包含冗余状态。最小化可以让自动机更紧凑，也能暴露不同正则表达式之间的本质等价性。
DFA 最小化最核心的思想：
如果两个状态对所有可能的后续输入产生完全相同的接受结果，那么它们就是等价状态，可以合并。
最小化算法的基本步骤：

移除不可达状态。
初始划分 $\Pi = \{F, S \setminus F\}$ 。
反复分裂：若同一组中的状态在某个输入符号上转移到不同组，则按转移目标组分裂该组。
直到没有组可以分裂。

最终每个划分组成为最小 DFA 的一个状态。理论上，最小 DFA 在同构意义下是唯一的。这也是正则语言理论的一个漂亮结论。

4. 多规则与最长匹配#

真实词法分析器需要同时识别多种 token，例如 if、id、num、<= 等。
合并方法：

为每个 token 类构造 NFA。
新建一个总开始状态，用 $\varepsilon$ 边连到所有规则 NFA 的开始状态。
对合并后的 NFA 做子集构造，得到 DFA。
每个 DFA 接受状态关联一个或多个规则及其优先级。

此时出现两个问题：

不同规则可能有公共前缀，例如 if 与 identifier。
一个字符串可能有多个可接受前缀，例如 >= 可以被识别为 > 后接 =。

实际词法分析器采用两个原则：

最长匹配：在输入上模拟 DFA，直到无法继续；然后回溯到最近经过的接受状态。
优先级：如果最近接受状态对应多个规则，选择优先级最高的规则。

最长匹配保证了 >= 不会被切分为 > 和 =；优先级保证了关键字不会被识别为标识符。

二、语法分析#

语法分析器接收词法分析器输出的 token 流，验证它是否符合语言的语法规则，并构建出语法树。词法分析把字符流变成 token 流，语法分析则把这个线性的 token 流重新变回树状结构。
这一阶段的理论基础是上下文无关文法（CFG）和下推自动机。但实际编译器使用的不是完整的 CFG，而是它的两个确定性子类：LL 和 LR。

1. 上下文无关文法#

一个上下文无关文法 $G$ 是一个四元组：

(V, \Sigma, R, S)

$V$ ：非终结符集合
$\Sigma$ ：终结符集合（与 $V$ 不相交）
$R$ ：产生式集合，形如 $A \to \alpha$ ，其中 $A \in V$ ， $\alpha \in (V \cup \Sigma)^*$
$S \in V$ ：开始符号

从产生式可以定义推导关系 $\Rightarrow$ 。如果存在产生式 $A \to \gamma$ ，那么 $\alpha A \beta \Rightarrow \alpha \gamma \beta$ 。推导的自反传递闭包记为 $\Rightarrow^*$ 。

文法 $G$ 定义的语言是所有能从 $S$ 推导出的终结符串的集合：

L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}

推导过程中，如果每一步都替换最左边的非终结符，称为最左推导；替换最右边的称为最右推导。最右推导又称规范推导，其逆过程是自底向上分析的基础。

2. 语法树与二义性#

语法树是推导的图形表示：根是开始符号，内部节点是非终结符，叶子是终结符。一个推导对应一棵语法树，但不同的推导顺序可能对应同一棵树。例如，最左推导和最右推导通常对应同一棵语法树。

如果一个文法存在某个句子对应两棵或更多不同的语法树，则称该文法是二义文法。经典的例子是悬空 else 问题：

1
stmt -> if expr then stmt
2
      | if expr then stmt else stmt
3
      | other

对于句子 if E1 then if E2 then S1 else S2，else 可以与内层 if 或外层 if 匹配，产生两棵语法树。

消除二义性的方法：

引入优先级和结合性规则，如规定 else 与最近的未匹配 then 匹配。
改写文法，引入新的非终结符来强制分层，例如区分 matched_stmt 和 unmatched_stmt。

二义性本身不是错误，很多文法天然二义，但可以通过附加规则消解。然而，对于 LL 和 LR 分析，二义文法通常无法直接使用，需要消除或借助规则。

3. 自顶向下分析#

自顶向下分析从开始符号出发，尝试构造一个最左推导，使得叶子序列与输入 token 流匹配。最直观的实现是递归下降，但回溯代价高。预测分析通过提前查看输入符号来消除回溯，典型代表是 LL(1) 文法。

3.1 FIRST 和 FOLLOW 集合#

预测分析需要两个集合：

$\text{FIRST}(\alpha)$ ：可以从 $\alpha$ 推导出的所有串的首终结符集合。如果 $\alpha \Rightarrow^* \varepsilon$ ，则 $\varepsilon \in \text{FIRST}(\alpha)$ 。
$\text{FOLLOW}(A)$ ：可能在某些句型中紧跟在非终结符 $A$ 之后的终结符集合。

计算 FIRST 的规则：

若 $X$ 是终结符，则 $\text{FIRST}(X) = \{X\}$ 。
若 $X \to \varepsilon$ 是产生式，则 $\varepsilon \in \text{FIRST}(X)$ 。
若 $X \to Y_1 Y_2 \cdots Y_k$ ，则将 $\text{FIRST}(Y_1)$ 中除 $\varepsilon$ 外的元素加入 $\text{FIRST}(X)$ ；若 $Y_1$ 能推出 $\varepsilon$ ，则继续加入 $\text{FIRST}(Y_2)$ ，依此类推；若所有 $Y_i$ 都能推出 $\varepsilon$ ，则 $\varepsilon \in \text{FIRST}(X)$ 。

计算 FOLLOW 的规则：

将 $\$$（输入结束标记）放入$ \text{FOLLOW}(S)$。
若存在产生式 $A \to \alpha B \beta$ ，则 $\text{FIRST}(\beta)$ 中除 $\varepsilon$ 外的元素加入 $\text{FOLLOW}(B)$ 。
若存在产生式 $A \to \alpha B$ ，或 $A \to \alpha B \beta$ 且 $\beta \Rightarrow^* \varepsilon$ ，则 $\text{FOLLOW}(A)$ 加入 $\text{FOLLOW}(B)$ 。

3.2 预测分析表与 LL(1) 文法#

预测分析表 $M$ 是一个二维表，行是非终结符，列是终结符（含 $\$$）。对于每个产生式$ A \to \alpha$：

对 $\text{FIRST}(\alpha)$ 中的每个终结符 $a$ ，将 $A \to \alpha$ 填入 $M[A, a]$ 。
若 $\varepsilon \in \text{FIRST}(\alpha)$ ，则对 $\text{FOLLOW}(A)$ 中的每个终结符 $b$ ，将 $A \to \alpha$ 填入 $M[A, b]$ 。

如果表中每个格子至多一个产生式，则该文法是 LL(1) 文法。LL(1) 的含义是：从左到右扫描输入，使用最左推导，只需向前看一个符号。

LL(1) 文法是无二义的，且没有左递归和公共前缀。消除左递归和提取左因子是将文法改造成 LL(1) 的常用技术。

4. 自底向上分析#

自底向上分析从输入串出发，反向进行最右推导，即不断将产生式右部归约为左部，直到归约为开始符号。这个归约序列正好是最右推导的逆序。

自底向上分析器的核心是移进-归约模型：

维护一个栈，初始为空。
输入缓冲区存放剩余的 token 流。
每一步可以选择：
- 移进：将下一个输入符号压入栈。
- 归约：栈顶的某段符号串匹配某个产生式的右部，将其替换为该产生式的左部。
- 接受：栈中只剩开始符号，且输入耗尽。
- 报错：无法继续。

归约时栈顶需要匹配的符号串称为句柄。在规范归约中，句柄总是出现在栈顶。

5. LR 分析#

LR(k) 分析是一类自底向上分析方法，能处理大多数实际程序设计语言的文法。L 表示从左到右扫描，R 表示最右推导的逆过程，k 表示向前看符号数。实践中 k=0 或 1。

5.1 LR(0) 项目与项目集规范族#

LR 分析器的核心是构造一个 DFA，其状态是“项目集”。一个项目是在产生式右部某处加一个点的产生式，例如 $A \to \alpha \cdot \beta$ ，点表示已经看到了多少。

项目集通过闭包和转移函数构造：

闭包：若项目 $A \to \alpha \cdot B \beta$ 在集合中，则对所有 $B \to \gamma$ ，将 $B \to \cdot \gamma$ 加入集合。
转移：对项目集 $I$ 和符号 $X$ ， $I$ 的 $X$ 转移是闭包 $\{ A \to \alpha X \cdot \beta \mid A \to \alpha \cdot X \beta \in I \}$ 。

从初始项目集出发，反复求转移，得到所有项目集的规范族。这个规范族构成 LR(0) 自动机的状态集合。

5.2 SLR、LR(1) 与 LALR#

LR(0) 自动机构造简单，但可能产生移进-归约冲突或归约-归约冲突。SLR 通过引入 FOLLOW 集合来减少冲突：仅当输入符号属于产生式左部的 FOLLOW 集合时才进行归约。SLR 构造简单，但能力有限。

LR(1) 项目在 LR(0) 项目基础上增加一个向前看符号，形如 $[A \to \alpha \cdot \beta, a]$ ，表示只有在下一个输入符号是 $a$ 时才归约。LR(1) 能力最强，但状态数可能非常多。

LALR(1) 是 LR(1) 的实用折中：将 LR(1) 项目集中“同心”的状态（忽略向前看符号后相同的状态）合并，从而大幅减少状态数，同时保留大部分 LR(1) 的能力。Yacc/Bison 等工具默认使用 LALR(1)。

5.3 LR 分析表#

LR 分析器由两个表驱动：ACTION 和 GOTO。

ACTION 表：给定状态和输入符号，决定移进、归约、接受或报错。
GOTO 表：给定状态和非终结符，决定转移到哪个状态。

分析过程反复查表，直到接受或报错。LR 分析器的构造算法虽然复杂，但可以完全自动化，这正是工具生成器的价值所在。

6. 复习要点#

语法分析的理论基础是上下文无关文法，但实际编译器只使用确定性的子类：LL 和 LR。
推导与语法树：最左推导对应自顶向下，最右推导的逆过程对应自底向上。
二义性是文法的属性，需要消除或通过规则消解。
自顶向下分析需要 FIRST/FOLLOW 集合和预测分析表；LL(1) 文法是无二义、无左递归、无公共前缀的。
自底向上分析基于移进-归约，LR 分析器通过项目集构造 DFA，SLR/LR(1)/LALR 是不同强度的变体。
LL 与 LR 的关键区别：LL 在推导时决定使用哪个产生式；LR 在归约时决定使用哪个产生式。LR 能处理更多文法，但状态构造更复杂。
实际工具：ANTLR 使用 LL(*)，Yacc/Bison 使用 LALR(1)。

如果只让我记住一句话：语法分析就是把线性的 token 流重新组装成树，LL 从根往下长，LR 从叶往上拼。前者靠预测，后者靠归约。

萘Naie_Char

一、词法分析#

1. 词法单元、词素与模式#

2. 正则表达式与正则定义#

3. 有限自动机#

3.1 NFA 与 DFA#

3.2 正则表达式 → NFA：Thompson 构造#

3.3 NFA → DFA：子集构造#

3.4 DFA 最小化#

4. 多规则与最长匹配#

二、语法分析#

1. 上下文无关文法#

2. 语法树与二义性#

3. 自顶向下分析#

3.1 FIRST 和 FOLLOW 集合#

3.2 预测分析表与 LL(1) 文法#

4. 自底向上分析#

5. LR 分析#

5.1 LR(0) 项目与项目集规范族#

5.2 SLR、LR(1) 与 LALR#

5.3 LR 分析表#

6. 复习要点#

目录