本文档由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$ （处理最高优先级的括号和原子）

左递归消除

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

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

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

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