本文档由notebookLM独家指导，尝试新时代速通路线。

词法分析

核心概念

词法单元 (Token)：由一个词法单元名和一个可选的属性值组成，通常用 <token name, token value> 的形式表示。它是词法分析器输出给语法分析器的逻辑符号。

模式 (Pattern)：描述了源语言中特定记号的构成规则。在编译器设计中，模式通常使用正则表达式来刻画，例如变量名的命名规则就是一个模式。(事实上翻译成模板你就理解是什么意思了，就是一堆东西应该长成什么样子)

词素 (Lexeme)：是源程序中的一个具体的字符序列。它与某个词法单元的模式相匹配，并被词法分析器识别为该词法单元的一个实例。

词法分析器根据模式（规则），在源代码中识别出词素（字符序列），并将其转化为词法单元（逻辑单元）传递给后续阶段

DFA：确定有穷自动机 NFA：不确定有穷自动机 二者区别在于NFA允许有多个出边，DFA所有状态、所有字符都必须有唯一转移，并不至少单纯的唯一输入唯一转移就可以，如果一个节点接受一个输入但是即不能终结也没有去处，那就还是NFA，满足不了DFA，

正则表达式

ϵ：匹配空串

字符 a：匹配字母表中的单个符号 a

选择 (r|s)：匹配 r 或 s 定义的语言。例如 a|b 匹配集合 {a,b}。

连接 (rs)：匹配 r 后面紧跟 s 的字符串。例如 ab 匹配 {ab}。

Kleene 闭包 ($r^*$)：匹配 r 出现 0 次或多次的情况。例如 a* 匹配 {ϵ,a,aa,…}。

优先级：闭包（*）优先级最高，其次是连接，最后是选择（|）。所有算符均为左结合

还有一些扩展语法我们通常在题目中不用，如正闭包 (r+)这种，因为做题不方便。不方便写状态机。但是是可以等价转换的。

  • $r^+$ 还原为 $rr^*$
  • $r?$ 还原为 $r | \epsilon$

RE转NFA

正则表达式 Regular Expression

非确定性有穷自动机 Non-Deterministic Finite Automata

选择 ($s|t$)：创建一个新起点和新终点。从起点画两条 $\epsilon$ 弧分别指向 $s$ 和 $t$ 的开始，再从 $s$ 和 $t$ 的结束各画一条 $\epsilon$ 弧指向新终点, 。

连接 ($st$)：将 $s$ 的接受状态与 $t$ 的开始状态合并（或者用一条 $\epsilon$ 弧连接） 。

闭包 ($s^*$)：增加新起点和新终点。新起点可直接跳到新终点（匹配空串），也可进入 $s$；$s$ 的终点画 $\epsilon$ 弧回跳到其起点（实现循环），同时也指向新终点。

唯一性：整个 NFA 只能有一个开始状态（用 start 箭头标出）和一个接受状态（用双圈表示）。

出口限制：接受状态不能有向外的转换弧。

弧的限制：每个状态要么发出一条字母表符号弧，要么最多发出两条 $\epsilon$ 弧。

推荐步骤：

  1. 先画出单个字母（如 $a, b$）的基础 NFA。
  2. 按照括号 > 闭包 > 连接 > 选择的优先级顺序逐步合并。
  3. 最后检查是否只有一个双圈状态，且该状态没有发出的弧。

NFA转DFA

子集构造法 (Subset Construction)，其核心思想是让 DFA 的每一个状态对应 NFA 的一个状态集合。

我们通过一个为Dtran的表格来实现，假设我们的语言只有ab两个字母。

NFA 状态 DFA状态 a b
{0,1,2,3,4,…..} A B C
{1,2,6,8,10,…} E B D

以上数据均为瞎编构造，仅用于说明NFA状态填入集合，DFA状态填入一个字母表示这个集合，当不存在新的集合出现时，证明已经转换完毕。

在填充表格之前，必须定义两个操作：

  1. $\epsilon\text{-closure}(S)$：从状态集 $S$ 中的每个状态开始，只通过 $\epsilon$ 边（空移动）能够到达的所有状态的集合。
  2. $move(S, c)$：从状态集 $S$ 中的每个状态开始，通过消耗一个输入字符 $c$ 能够直接到达的状态集合。

初始的时候第一个NFA状态是start通过不限量个ε可达的节点。然后这个集合通过一个a/b进行状态转移，能到达什么地方，再计算这个几个通过不限量个ε可达的节点，也就是求$\epsilon_{closure}({T}) $（T为集合）。

DFA最小化

DFA 最小化（通常采用 Hopcroft 算法）的核心是通过划分等价状态组，将行为完全一致的状态合并，从而得到状态数最少的等价 DFA。

核心步骤：

  1. 初始划分：将 DFA 的所有状态分为两个初始组：接受状态组（终态）和非接受状态组。检查可区分性：对于同一组内的状态，检查它们在输入相同符号 a 后，是否跳转到了不同的组。如果跳转目标不在同一个组，说明这些状态是“可区分”的，必须将它们拆分。
  2. 迭代与合并：重复上述拆分过程，直到所有组都不能再划分为止。最后，将每个组内的状态合并为一个代表状态。
  3. 区分标准：如果从状态 s 出发经路径 w 到达接受状态，而从 t 出发经相同路径 w 到达非接受状态，则 s 和 t 是不可合并的。

终态也叫接受状态就是完事了，非终态通常指自动机中的初始状态或中间状态。等价类就是对于任意输入他们跳转到同一个等价类并且它们两个本身必须同为“终态”或同为“非终态”。

语法分析

核心概念

语法分析的基础是上下文无关文法 (CFG)，它的任务是根据词法分析提供的记号（Token）流，构造出具有层次结构的语法分析树。

上下文无关文法（CFG）是用于描述程序设计语言语法的核心工具，它比正则表达式更强大，能够表达递归和嵌套结构（如配对的括号 (( ))）,。

它由一个四元组定义：

  1. 非终结符 ($V_N$)：表示语法范畴的逻辑符号，如“语句”或“表达式”。
  2. 终结符 ($V_T$)：语言的基本单元，即词法分析传来的记号（如 id, +, if）。
  3. 开始符号 ($S$)：文法中指定的唯一起始非终结符。
  4. 产生式 ($P$)：重写规则，形式为 $A \rightarrow \alpha$，表示左边的符号可以被右边的序列替换。

推导 (Derivation)：这是分析的核心过程。通过不断地用产生式的右部替换左部的非终结符，最终生成只包含终结符的字符串。

文法设计

  • 线性文法 (正则文法)：用于描述简单的重复或顺序结构。其产生式形式受限：
    • 右线性：$A \rightarrow aB$ 或 $A \rightarrow a$（非终结符只能在最右边）。
    • 左线性：$A \rightarrow Ba$ 或 $A \rightarrow a$。
    • 考试技巧：设计生成“被 3 除余 1 的二进制串”这类题目时，通常使用右线性文法，通过状态转换的思想来写。
  • 上下文无关文法 (CFG)：比线性文法更强大，左部只有一个非终结符，右部可以是任意符号串。
    • 应用：处理配对（如 $a^n b^n$）或嵌套结构（如括号匹配）时必须使用 CFG。

二义性与语法树

  • 定义：如果一个文法能为同一个句子构造出两棵不同的语法分析树（或两个不同的最左推导），它就是二义性的。
  • 证明方法：找一个简单的输入串（如真题中的 a+a+a 或 id*id+id），尝试画出两棵结构不同的树：一棵左结合，一棵右结合。
  • 消除方法：通过改写产生式来引入优先级和结合性。例如，先处理乘法再处理加法，从而强制生成的树只有一种形态。

构造等价无二义文法的核心在于引入运算符的优先级和结合性，通过将产生式分层来强制唯一的推导路径。

以真题文法 $S \rightarrow a \mid S+S \mid SS \mid S^* \mid (S)$ 为例，构造步骤如下：

  1. 确定优先级：通常顺序为括号 $(S)$ 和原子 $a$ > 闭包 $S^*$ > 连接 $SS$ > 选择 /运算符$S+S$。
  2. 处理结合性：
    • 左结合（如 $+$ 和连接）：采用左递归形式（$A \rightarrow A\alpha \mid \beta$）。
    • 右结合：采用右递归形式。
  3. 分层改写：
    • $S \rightarrow S + A \mid A$ （处理优先级最低的 $+$，左结合）
    • $A \rightarrow AB \mid B$ （处理连接，左结合）
    • $B \rightarrow B^ \mid C$* （处理闭包）
    • $C \rightarrow (S) \mid a$ （处理最高优先级的括号和原子）

补充：引入的东西在于不同层级的非终结符只能推导出一种优先级的运算，每一级非终结符，只能包含它自己这一级以及比它优先级更高的运算，严格排斥更低优先级的运算。

引入的非终结符 代表含义 负责的运算符 关键特征
F (Factor) 原子/因子 ( ) , id 不可分割的最小单元，不包含任何二元运算符
T (Term) 项 * 只能生成连乘的结构，不允许在此层直接生成 +
E (Expr) 表达式 + 最外层，只能生成连加的结构，加法的右侧必须是 T

左递归消除

  • 为什么要消除：自顶向下的 LL(1) 分析器不能处理左递归（如 $A \rightarrow A\alpha$），否则会陷入死循环。

  • 固定公式 (直接左递归)：

  • 若有 $A \rightarrow A\alpha \mid \beta$，改写为：

  1. $A \rightarrow \beta A'$
  2. $A’ \rightarrow \alpha A’ \mid \epsilon$

进一步还有隐式左递归消除

隐式左递归（间接左递归）是指文法产生式中没有直接的 $A \rightarrow A\alpha$，但经过两步或多步推导后，会出现以自身开头的符号串（例如 $S \Rightarrow Aa \Rightarrow Sda$）。

消除步骤（算法 4.1）：

  1. 非终结符排序：将文法中的所有非终结符按一定顺序排列，如 $A_1, A_2, \dots, A_n$。
  2. 代入转化：按照排序依次检查每一个 $A_i$。如果 $A_i$ 的产生式右部以排在它前面的非终结符 $A_j$ ($j < i$) 开头，则将 $A_j$ 的所有定义代入到 $A_i$ 的产生式中。
  3. 消除直接左递归：完成代入后，若 $A_i$ 出现了直接左递归，则应用标准公式：$A \rightarrow \beta A’, A’ \rightarrow \alpha A’ \mid \epsilon$ 进行消除。 实例演示

已知文法：$B \rightarrow Sa \mid a$，$A \rightarrow Bb \mid b$，$S \rightarrow Ac \mid c$。

  • 代入：将 $B$ 的定义代入 $A$，得到 $A \rightarrow Sab \mid ab \mid b$。
  • 再代入：将 $A$ 的新定义代入 $S$，得到 $S \rightarrow Sabc \mid abc \mid bc \mid c$。
  • 消除：此时 $S$ 变为了直接左递归，应用公式改写为 $S \rightarrow (abc \mid bc \mid c) S’$ 和 $S’ \rightarrow abc S’ \mid \epsilon$ 即可。

LL（1）分析

LL(1) 分析是考试中分值最高的大题（约 20-30 分），它代表：L（从左向右扫描）、L（产生最左推导）、1（每步只向前看一个输入符号）。

掌握这个专题需要按以下三个核心步骤走：

第一步：计算 First 集和 Follow 集

这是构造分析表的依据。

  • First(X)：从 $X$ 推导出的字符串中第一个终结符的集合。

  • Follow(A)：可能紧跟在非终结符 $A$ 后面的终结符集合。

  • 必考点：开始符号 $S$ 的 Follow 集初始必包含 $。

这三条规则的核心逻辑是：找出在所有可能的推导序列中，哪些终结符可能紧跟在非终结符 $B$ 的右边。

1. 开始符号规则：若 $A$ 是开始符号，则 $$ \in FOLLOW(A)$

  • 总结：文法的起始目标是匹配整个输入串，而输入串的逻辑终点由 $$$ 标记。
  • 证明：根据句法分析的设计，完整的推导序列表现为 $S$ \Rightarrow w$$，因此 $$$ 必然存在于起始符号的后继集合中。

2. 右邻居规则：若 $A \rightarrow \alpha B \beta$，则 $FIRST(\beta) - {\epsilon} \subseteq FOLLOW(B)$

  • 总结：$B$ 的“右手边邻居”能推导出的所有开头字符，都是 $B$ 的追随者。
  • 证明：在推导序列 $A \Rightarrow \alpha B \beta$ 中，如果 $\beta$ 推导出的字符串以终结符 $a$ 开头（即 $a \in FIRST(\beta)$），则序列变为 $\dots \alpha B a \dots$，证明 $a$ 可以紧跟在 $B$ 之后。

3. 左部继承规则：若 $A \rightarrow \alpha B$ 或 $A \rightarrow \alpha B \beta$（且 $\beta \Rightarrow \epsilon$），则 $FOLLOW(A) \subseteq FOLLOW(B)$

  • 总结：如果 $B$ 位于产生式末尾，或者它后面的所有符号都能消失（推导出空串），那么凡是能跟在左部符号 $A$ 后面的，也一定能跟在 $B$ 后面。
  • 证明：
    • 针对 $A \rightarrow \alpha B$：假设 $a$ 跟在 $A$ 后面，推导为 $Aa \Rightarrow \alpha Ba$，此时 $a$ 显然也跟在 $B$ 后。
    • 针对 $\beta \Rightarrow \epsilon$：若 $Aa \Rightarrow \alpha B \beta a$，由于 $\beta$ 可以变为空，推导最终变为 $\alpha B a$，证明 $a$ 也是 $B$ 的追随者。

第二步：构造预测分析表 $M$

根据产生式 $A \rightarrow \alpha$ 填表：

  1. 对 $First(\alpha)$ 中的每个终结符 $a$，把 $A \rightarrow \alpha$ 放入 $M[A, a]$。
  2. 若 $\epsilon \in First(\alpha)$，则对 $Follow(A)$ 中的每个终结符 $b$，把 $A \rightarrow \alpha$ 放入 $M[A, b]$。
  3. 判定：如果表中任何单元格都没有重定义（即一个格子里只有一条产生式），该文法就是 LL(1) 文法。

第三步：显式栈模拟句法分析

在考试中，通常要求你演示对输入串（如 babbb 或 adccd）的分析过程：

  • 初始化：栈底为 $，栈顶为开始符号 $S$；输入串末尾加 $。

  • 操作：

    • 若栈顶是终结符且与输入匹配，则弹出并前进。
    • 若栈顶是非终结符，查表 $M$，将栈顶替换为对应产生式的右部逆序入栈。
    • 若栈顶与输入都是 $，则分析成功。