1 Lexical Analysis¶

词法分析是编译器的第一个阶段，负责将源代码字符流转换为Token 流（词法记号流），供语法分析器消费。本质上是为每种 Token 类型定义正则表达式，然后用自动机识别。

核心流程：正则定义 → RE → NFA → DFA → 最小化 DFA → 表驱动实现。

1.1 Specification¶

输入：源代码字符流。输出：Token 流。

关键概念：Lexeme（词素）是源代码中匹配到的具体字符串，Token（记号）是词素的类型分类（如 ID、NUMBER、IF）。每个 Token 通常还携带属性值（如标识符的名字、数字的值）。

输入:  "x = 42 + y"
输出:  <ID, "x">  <ASSIGN>  <NUMBER, 42>  <PLUS>  <ID, "y">

正则定义 (Regular Definitions)：为复杂模式命名，自底向上构造：

digit  → 0 | 1 | 2 | ... | 9
letter → A | B | ... | Z | a | b | ... | z
id     → letter (letter | digit)*
number → digit+ (. digit+)? (E (+|-)? digit+)?

Token 的属性值

像 ID 的 lexeme 各不相同（x, y, foo），需要保留具体的字符串值；关键字如 if 则只需要 Token 类型就够了。因此 Token 通常是一个 (type, value) 对。

1.2 Formalization (RE & Disambiguation)¶

将自然语言规则转化为正则表达式。三种基本运算：

选择 (Union)：A | B — 匹配 A 或 B
连接 (Concatenation)：AB — A 后紧跟 B
闭包 (Kleene Star)：A* — 零个或多个 A

优先级：* > 连接 > |。如 a | bc* = a | (b(c*))。

正则表达式满足代数定律（用于等价变换和化简）：

定律	公式
选择交换律	\(r \mid s = s \mid r\)
选择结合律	\((r \mid s) \mid t = r \mid (s \mid t)\)
连接结合律	\((rs)t = r(st)\)
分配律	\(r(s \mid t) = rs \mid rt\)
幂等律	\(r^{*} = r^\)

二义性处理 (Disambiguation)：当多个规则匹配同一段输入时：

Longest Match：尽可能多地读入字符（如 >= 不会在读完 > 后就停下）。
Rule Priority：若多个规则匹配同一最长前缀，取定义中排在前面的规则（如关键字 if 虽然也符合 id 的模式，但关键字规则排在前面，优先匹配）。

1.3 Transformation (RE → NFA → DFA)¶

将正则表达式转化为确定性有限自动机，这是词法分析的理论核心。

1.3.1 Thompson Construction (RE → NFA)¶

Thompson 构造法基于 RE 的结构进行递归构造。每个 NFA 片段有一个起始状态和一个接受状态，通过 \(\varepsilon\) 转移连接。

基本单元：

空串 \(\varepsilon\)：start →(ε)→ accept
单字符 a：start →(a)→ accept

复合构造（设 \(N(s)\) 和 \(N(t)\) 分别为 \(s\) 和 \(t\) 的 NFA）：

选择 \(s \mid t\)：新建开始/接受状态，各引一条 \(\varepsilon\) 边分别进入 \(N(s)\) 和 \(N(t)\)，两个旧接受状态各引 \(\varepsilon\) 边到新接受状态。
连接 \(st\)：\(N(s)\) 的接受状态与 \(N(t)\) 的开始状态合并。
闭包 \(s^*\)：新建开始/接受状态；新开始 \(\varepsilon\)→ \(N(s)\) 的开始 + \(\varepsilon\)→ 新接受（处理零次）；\(N(s)\) 的接受 \(\varepsilon\)→ \(N(s)\) 的开始（处理多次）+ \(\varepsilon\)→ 新接受。

这个在计算理论中有详细说明

1.3.2 Subset Construction (NFA → DFA)¶

NFA 的缺点：一个输入可能对应多个后继状态，需要回溯或并行模拟。子集构造法将 NFA 的状态集合作为 DFA 的单个状态，消除非确定性。

两个核心操作：

\(\varepsilon\)-closure(\(S\))：从状态集 \(S\) 出发，只经过 \(\varepsilon\) 转移能到达的所有状态的集合（包括 \(S\) 自身）。
move(\(S\), \(c\))：从状态集 \(S\) 出发，经过字符 \(c\) 的转移能到达的状态集合（不含 \(\varepsilon\) 转移）。

算法：

Dstates = { ε-closure({nfa_start}) }   // DFA 状态集合
while there is an unmarked state T in Dstates:
    mark T
    for each input character c:
        U = ε-closure(move(T, c))
        if U not in Dstates: add U to Dstates
        Dtran[T, c] = U                 // 添加 DFA 转移

DFA 的每个状态是 NFA 状态的子集，包含 NFA 接受状态的即为 DFA 接受状态。

这个也在计算理论中有详细的说明

1.3.3 DFA Minimization¶

目的：合并等价状态，减少状态数量。核心思想是划分等价类——如果两个状态在任意输入下都转移到"同类"状态，则它们等价。

算法（Hopcroft）：

初始划分 Π = { 接受状态集合, 非接受状态集合 }
while Π 发生变化:
    for each 组 G in Π:
        for each 输入字符 c:
            若 G 中状态在 c 上的转移目标属于 Π 中不同组:
                按转移目标所属组，将 G 分裂

1.4 Implementation¶

DFA 的代码实现主要有两种方式。

Table-Driven：将 DFA 转移表存储为二维数组 next[state][char]，循环查表驱动：

state = START;
while (char = nextChar()) {
    state = table[state][char];
    if (state == ERROR) break;
}
if (isAccepting(state)) return tokenFor(state);

表可能很大（状态数 × 字符集大小），实际中常用压缩技术（如行压缩、稀疏矩阵）。

Lex/Flex：词法分析器生成工具。.l 文件结构：

%{
/* 声明部分：C 代码、全局变量 */
int count = 0;
%}

/* 正则宏定义 */
digit   [0-9]
letter  [a-zA-Z]
id      {letter}({letter}|{digit})*

%%
/* 规则部分：模式 { 动作 } */
{id}        { printf("ID: %s\n", yytext); }
{digit}+    { printf("NUM: %s\n", yytext); }
[ \t\n]     { /* skip whitespace */ }
.           { printf("Error: %s\n", yytext); }
%%

/* 辅助函数 */
int yywrap() { return 1; }

编译流程：.l → lex → lex.yy.c → cc → a.out。

评论区

对你有帮助的话请给我个赞和 star =>

欢迎跟我探讨！！！