Lesson 21: 词法分析器 CNB

练习任务

实现一个 DFA（确定有限自动机）驱动的词法分析器。逐字符读入 C 语言代码片段，通过查表 yy_nxt[当前状态][字符] 驱动状态转移，当状态变为负数时识别到 token 边界，用 yy_accept 查出 token 类型并打印。

输入示例 int x=42;，期望输出：

	Pattern  3 found: int
	Pattern 27 found: x
	Pattern 49 found: =
	Pattern 24 found: 42
	Pattern 60 found: ;

提示：本课的核心思想是「机制与策略分离」—— DFA 主循环是机制（逻辑不变），yy_nxt 转移表和 yy_accept 动作表是策略（由工具生成，换一张表就能识别不同的语言）。回顾 Lesson 13 中的 switch 驱动状态机和 Lesson 16 中的字符数组操作，本课将它们组合成了编译原理中最基础的一环——词法分析器（Lexer）。

核心知识点

DFA 确定有限自动机 — 状态 + 输入字符 → 新状态，无歧义的确定性转移
状态转移表 — yy_nxt[state][char] 二维数组，编译原理中 DFA 的标准表示
动作表 — yy_accept[state] 记录每个终止状态对应的 token 类型
负数标记 — state < 0 表示到达终止状态，取反恢复原始状态编号
字符回退 — ungetc(c, stdin) 将触发 token 边界的字符退回输入流
机制与策略分离 — DFA 引擎不变，换表即可识别不同语言
getchar/EOF — 逐字符读取与文件结束检测
debug 宏 — fprintf(stderr, ...) 变参宏的调试技巧
二维数组 — int yy_nxt[][128] 行优先存储与查表访问
编译原理入门 — 词法分析（Lexing）、token 化、flex/lex 工具
空格与换行过滤 — yy_accept 中 pattern 1（换行）和 pattern 21（空格）的跳过逻辑

代码框架

mylex.c

#include <stdio.h>
#include "yy_nxt.c"
#include "yy_accept.c"

#define debug(fmt, args...)	fprintf(stderr, fmt, ##args)

int main(void)
{
	int state = 1;       // 初始状态
	char buf[64];        // 当前 token 缓冲区
	int i = 0;           // buf 写入位置

	while (1)
	{
		char c;

		c = getchar();   // 逐字符读取
		if (c == EOF)    // 文件结束
			break;

		buf[i++] = c;    // 积累当前 token

		debug("\tstate = %d, ", state);

		// 在这里查表转移:
		// state = yy_nxt[state][c];

		debug("c = <%c>, new state = %d\n", c, state);

		// 在这里判断 state < 0:
		//   - state = -state; 恢复状态编号
		//   - act = yy_accept[state]; 查动作表
		//   - buf[i-1] = '\0'; 去掉触发退出的字符
		//   - 跳过空白 (act==21) 和换行 (act==1)
		//   - 否则 printf("Pattern %d found! <%s>\n", act, buf);
		//   - ungetc(c, stdin); 回退触发字符
		//   - i = 0; state = 1; 重置
	}

	return 0;
}

请根据注释中的算法提示，补全查表转移和 token 识别逻辑。yy_nxt.c 和 yy_accept.c 是预生成的转移表和动作表（由 flex 工具从正则规则自动生成），你不需要修改它们，只需在 main 中实现 DFA 主循环。

先不要往下翻看参考解答。试着理解「查表 → 状态转移 → 负数表示 token 边界」这个核心循环，然后自己动手实现。卡住时可以运行 `clings hint` 获取提示。

深度讲解

1. 什么是词法分析

编译器在拿到源代码之后，第一件事就是把字符流切成一个个有意义的「词」——这就是词法分析（Lexical Analysis）。比如对于 C 代码片段：

sample.c

int x = 42;

人类一眼就能看出这里有四个词：int（关键字）、x（标识符）、=（运算符）、42（整数字面量）、;（分隔符）。但编译器看到的是：

'i' 'n' 't' ' ' 'x' ' ' '=' ' ' '4' '2' ';'

词法分析器的任务就是把这串字符流翻译成 token 序列：

KEYWORD(int)  IDENTIFIER(x)  OPERATOR(=)  NUMBER(42)  SEMICOLON(;)

1.1 Token 是什么

Token 是词法分析器输出的最小单元。每个 token 包含两个信息：

类型（token type / pattern）：它是什么（关键字、标识符、数字、运算符...）
值（lexeme / value）：它对应的源代码文本（"int"、"x"、"42"...）

在 flex 生成的状态机中，yy_accept 数组返回的就是 token 类型编号（pattern number）。例如 int 的 pattern 是 3，; 的 pattern 是 60。

NOTE

词法分析器不关心语法是否正确。它只管「切词」，不管这些词能不能拼成合法的句子。int int = ; x 42 照样能切出 token，只不过后续的语法分析阶段会发现这是不合法的。这就是编译器的分层设计：每层只管自己的事。

1.2 编译器的前端流水线

词法分析是编译器的第一道工序。整个编译前端（front-end）的流水线如下：

源代码（字符流）
    │
    ▼
词法分析器 (Lexer / Scanner)      ← 本课
    │  输出: token 流
    ▼
语法分析器 (Parser)
    │  输出: 抽象语法树 (AST)
    ▼
语义分析器 (Semantic Analyzer)
    │  输出: 带类型标注的 AST
    ▼
中间代码生成 (IR Generator)
    │
    ▼
... 后端优化、代码生成 ...

每一层只处理上一层输出的数据结构，不关心上层如何产生这些数据。这种分层让编译器的每一层都可以独立开发、测试和替换。

词法分析器之所以值得单独实现，是因为它把「字符流 → token 流」这个看似简单的问题，用 DFA 的数学框架精确解决了。本课虽然只写了 30 行主循环代码，但这 30 行代码背后的 DFA 理论支撑了整个编译原理的基石。

1.3 本课的范围

本课的词法分析器覆盖了 C 语言的一个实用子集：关键字（int、return、if、while 等）、标识符、整数、浮点数、字符串字面量、运算符、分隔符、空白和注释。转移表 yy_nxt 由 flex 从正则规则自动生成，共约 139 个状态，足以处理实际教学代码的 token 化。

2. DFA：确定有限自动机

2.1 状态机回顾

回顾 Lesson 13（状态机编程），我们用 switch 语句实现了一个密码验证状态机：

fsm_switch.c

int state = 0;
while ((c = getchar()) != '\n') {
    switch (state) {
    case 0: if (c == '1') state = 1; else state = 0; break;
    case 1: if (c == '2') state = 2; else state = 0; break;
    case 2: if (c == '3') state = 3; else state = 0; break;
    case 3: printf("unlocked!\n"); state = 0; break;
    }
}

这种写法的问题是：状态转移逻辑硬编码在代码中。如果要识别另一组模式（比如改为密码 abc），必须修改所有 case 分支。有没有办法把状态转移和代码逻辑分离？

2.2 把状态机变成表格

考虑一个更通用的写法。状态机的核心是：

next_state = f(current_state, input_char)

如果我们把 f 写成一个表格——行是当前状态，列是输入字符，单元格是下一个状态：

          '0' '1' '2' '3' ... 'a' ... 'i' 'n' 't' ...
state 0:   0   1   0   0  ...  0  ...  0   0   0  ...
state 1:   0   0   2   0  ...  0  ...  2   0   0  ...
state 2:   0   0   0   3  ...  0  ...  0   0   0  ...
state 3:  -4  -4  -4  -4  ... -4  ... -4  -4  -4  ...

这就是 DFA 的状态转移表。对于密码 123：

状态 0 + '1' → 状态 1
状态 1 + '2' → 状态 2
状态 2 + '3' → 状态 3
状态 3 是负数 -4，表示识别到了 token！

负数是一个巧妙的编码：用符号区分「继续」（正数/0）和「终止」（负数）。取绝对值后，就是终止状态的编号，用于查 yy_accept 获取 token 类型。

用表格驱动后，主循环变得极其简洁：

dfa_table_driven.c

int state = 1;
while ((c = getchar()) != EOF) {
    state = yy_nxt[state][c];
    if (state < 0) {
        // token 识别完成
        int act = yy_accept[-state];
        printf("Pattern %d found\n", act);
        state = 1;  // 重置到初始状态
    }
}

现在如果要识别不同的语言，只需换一张表，主循环代码完全不变。这就是「机制与策略分离」。

2.3 手工追踪：DFA 如何识别 `int`

以输入 int （带尾部空格）为例，手工追踪 DFA 的每一步：

步骤 │ 当前状态 │ 读入字符 │ yy_nxt 查表         │ 新状态 │ 动作
─────┼─────────┼─────────┼────────────────────┼───────┼──────
  1  │    1    │   'i'   │ yy_nxt[1][105] →   │   46   │ 继续
  2  │   46    │   'n'   │ yy_nxt[46][110] →  │   62   │ 继续
  3  │   62    │   't'   │ yy_nxt[62][116] →  │   78   │ 继续
  4  │   78    │   ' '   │ yy_nxt[78][32] →   │   -3   │ 终止! token=3

注意第 4 步：在状态 78 读到空格，yy_nxt 返回 -3。负数表示「到达了终止状态 3」，而不是「转移到状态 -3」。此时：

取反：state = 3
查动作表：yy_accept[3] → 63（或其他 pattern 编号）
缓冲区 buf 中此时是 "int "（4 个字符），buf[3] = '\0' 截断为 "int"

这个追踪表展示了 DFA 工作的完整过程：状态逐步推进，直到遇到不属于当前 token 的字符时触发终止。

IMPORTANT

DFA 的「D」代表 Deterministic（确定的）：给定当前状态和输入字符，下一个状态是唯一确定的，没有任何歧义。这保证了词法分析器的行为可预测、可复现。

3. 转移表的结构：yy_nxt

3.1 二维数组作为转移表

yy_nxt 是一个二维 int 数组，声明为：

yy_nxt_decl.c

static int yy_nxt[][128] = { ... };

第一维：状态编号（从 0 开始，本课约 139 个状态）
第二维：输入字符（ASCII 码，0-127）

yy_nxt[state][c] 的含义是：「在状态 state 读到字符 c 后，转移到哪个状态」。

yy_nxt_access.c

state = yy_nxt[state][c];  // 二维数组查表，O(1) 时间

回顾 Lesson 14（迷宫搜索），我们学习了二维数组的行优先存储。这里 yy_nxt 的每一行有 128 个元素，yy_nxt[state] 就是指向第 state 行的指针（int (*)[128] 类型）。

3.2 转移表编码规则

yy_nxt 中的数值遵循以下编码约定：

数值	含义
`0`	未使用的状态行（状态 0 行全为 0）
`> 0`	正常转移，到达新状态编号
`< 0`	到达终止状态，负数绝对值 = 终止状态编号

例如，yy_nxt[2][105] = 46 表示在状态 2 读到字符 'i'（ASCII 105）转移到状态 46。yy_nxt[10][59] = -11 表示在状态 10 读到 ';' 时识别到了 token，终止状态编号是 11。

yy_nxt_example.c

// 在状态 1 读到 'i':
//   yy_nxt[1]['i'] = yy_nxt[1][105] → 正数，继续
// 在某个状态读到 ';':
//   yy_nxt[state][';'] → 负数，token 结束

3.3 状态的渐进含义

让我们追踪几个典型 token 的状态转移路径：

追踪 int：从状态 1 开始，依次读入 i → n → t，然后读到空格：

state 1 + 'i' (105) → state 46   // 可能是标识符或关键字开头
state 46 + 'n' (110) → state 62  // 进一步缩小范围
state 62 + 't' (116) → state 78  // 可能是 "int" 或标识符 "int..."
state 78 + ' ' (32)  → -3        // 空格触发终止！act=yy_accept[3]=63

yy_accept[3] = 63 可能对应 KEYWORD 类型。对比 yy_accept 的开头部分：

yy_accept_head.c

static int yy_accept[139] =
    {   0,
        0,    0,   63,   61,   21,    1,   38,   61,   59,   31,
       34,   61,   54,   55,   30,   28,   52,   29,   61,   24,
       24,   53,   60,   43,   49,   44,   58,   27,   37,   27,
       ...
    };

注意 yy_accept 的下标从 1 开始（flex 生成的约定）。yy_accept[3] = 63 就是 pattern 63——这正是 int 关键字对应的 token 类型。

理解转移表最好的方式是自己追踪

在 debug 宏的帮助下，运行程序输入 int x=42;，观察 stderr 输出的状态转移日志：

state = 1, c = <i>, new state = 46
state = 46, c = <n>, new state = 62
state = 62, c = <t>, new state = 78
state = 78, c = < >, new state = -3

每一条日志都对应一次查表。通过追踪，你可以直观理解 DFA 是如何一步步「缩小候选范围」的。

4. 动作表：yy_accept

4.1 终止状态到 token 类型

yy_accept 是一个一维数组，将终止状态编号映射到 token 类型（pattern number）：

yy_accept_decl.c

static int yy_accept[139] = { ... };

当 DFA 到达终止状态（yy_nxt 返回负数）时，我们用 -state 恢复状态编号，然后查 yy_accept：

yy_accept_lookup.c

state = -state;               // 恢复终止状态编号
int act = yy_accept[state];   // 查 token 类型

4.2 Pattern 编号的含义

不同的 pattern 编号对应不同的 token 类型。通过观察 yy_accept 数组和测试输入输出，我们可以推断出部分映射：

Pattern	Token 类型	示例
1	换行 `\n`	（跳过）
3	关键字 `int`	`int`
21	空白	、`\t`（跳过）
24	整数	`42`
27	标识符	`x`
49	运算符 `=`	`=`
60	分隔符 `;`	`;`

pattern 1 和 21 代表换行和空白，它们在词法分析中是「无意义 token」——需要被跳过而不输出。这就是代码中 if (!(act == 1 || act == 21)) 这一行的作用。

NOTE

为什么用 1 和 21 而不是 0 或 -1？这是 flex 工具的生成约定。flex 从用户定义的正则规则自动编号，空白和换行通常被分配较小的编号。换表时这些编号可能变化，但「跳过空白」的逻辑不变——这是「机制」的一部分。

5. 主循环详解

5.1 字符积累与缓冲区

buffer_accumulate.c

int state = 1;
char buf[64];
int i = 0;

while (1) {
    c = getchar();
    if (c == EOF) break;
    buf[i++] = c;      // 把读到的字符加入缓冲区
    state = yy_nxt[state][c];

    if (state < 0) {
        // token 结束
        buf[i-1] = '\0';  // 去掉触发退出的字符
        printf("Pattern %d found! <%s>\n", act, buf);
        i = 0;            // 重置缓冲区
        state = 1;        // 重置状态
    }
}

当读到 int （注意尾部空格）时：

i、n、t 被依次写入 buf[0]、buf[1]、buf[2]，状态持续正数
读到空格时，state 变为负数，触发 token 识别
此时 buf[0..2] 是 int，buf[3] 是空格——空格是触发 token 边界的字符，不属于这个 token
buf[i-1] = '\0' 即 buf[3] = '\0'，用空字符覆盖空格，使 buf 变成 C 字符串 "int"

这就是为什么需要用 i-1 去掉最后一个字符：触发终止状态的字符不属于当前 token。

5.2 字符回退：ungetc

ungetc(c, stdin) 将一个字符退回标准输入流。下一次调用 getchar() 时，会先读到被退回的字符。

ungetc_demo.c

int c1 = getchar();   // 读到 'a'
int c2 = getchar();   // 读到 'b'
ungetc(c2, stdin);    // 把 'b' 退回去
int c3 = getchar();   // 又读到 'b'
int c4 = getchar();   // 读到 'c'

在我们的词法分析器中，读到空格触发 int 的 token 边界后，空格本身可能属于下一个 token（或需要被跳过）。ungetc(c, stdin) 把这个字符退回，让下一轮循环重新处理它。

ungetc_in_lexer.c

if (state < 0) {
    state = -state;
    act = yy_accept[state];
    buf[i-1] = '\0';

    if (!(act == 1 || act == 21))
        printf("Pattern %d found! <%s>\n", act, buf);

    i = 0;
    state = 1;
    ungetc(c, stdin);  // 退回触发字符
}

5.3 空格和换行的过滤

空格（act == 21）和换行（act == 1）被识别为 token，但不需要输出。它们的作用仅仅是分隔其他 token。

skip_whitespace.c

if (!(act == 1 || act == 21))
    printf("Pattern %d found! <%s>\n", act, buf);

注意：虽然不输出，但代码仍然执行了 buf[i-1] = '\0'、i = 0、state = 1 和 ungetc。空格和换行仍然完成了 token 边界识别的作用，只是不打印。

缓冲区溢出

本课的 buf[64] 假设每个 token 不超过 63 个字符。对于 C 语言的常规 token（关键字、标识符、数字），这个大小绰绰有余。但如果输入包含超长字符串字面量（如 200 个字符的 "..."），buf 会溢出。在工业级 lexer 中，通常会动态分配缓冲区或用 realloc 扩容。回顾 Lesson 24 中 read_all 的动态扩容模式，同样的思路可以应用到 token 缓冲区。

6. debug 宏与调试技巧

6.1 变参宏

debug_macro.c

#define debug(fmt, args...)	fprintf(stderr, fmt, ##args)

这个宏做了几件事：

fmt, args... 是 GNU C 扩展的变参宏，允许接受可变数量的参数
##args 中的 ## 是 GNU 扩展——当 args 为空时，自动删除前面的逗号，避免语法错误
输出目标是 stderr 而不是 stdout，这样调试信息不会混入程序的正式输出

使用示例：

debug_usage.c

debug("state = %d\n", state);             // → fprintf(stderr, "state = %d\n", state)
debug("c = <%c>, new state = %d\n", c, state);

回顾 Lesson 18（snprintf 格式化），fprintf 和 printf 的区别在于第一个参数指定输出流。stderr 是无缓冲的，保证调试信息即使程序崩溃也能输出。

6.2 调试 vs 正式输出的分离

stderr_vs_stdout.c

debug("\tstate = %d, ", state);   // → stderr，调试信息
printf("Pattern %d found!\n", act); // → stdout，正式输出

练习系统的测试用例只检查 stdout，所以 stderr 上的调试输出不会干扰测试。但在实际运行时，你可以通过 shell 重定向分离两者：

bash

./mylex < input.c           # 混合输出
./mylex < input.c 2>/dev/null  # 只看正式输出，丢弃调试信息
./mylex < input.c 2>debug.log  # 调试信息写入文件

调试宏的开关

在发布版本中，可以定义一个开关来关闭所有调试输出：

#ifdef DEBUG
#define debug(fmt, args...) fprintf(stderr, fmt, ##args)
#else
#define debug(fmt, args...)  // 空宏，什么都不做
#endif

编译时加 -DDEBUG 开启，不加则关闭。这样调试代码不会进入最终二进制。

7. 机制与策略分离：DFA 的哲学

7.1 两层的分工

这是本课最重要的设计思想。我们把词法分析器分成两层：

层	是什么	变还是不变	对应代码
机制 (mechanism)	DFA 主循环：逐字符读入、查表转移、token 边界检测	不变	`while` 循环 + `state = yy_nxt[state][c]` + `state < 0` 判断
策略 (policy)	转移表 + 动作表：定义哪些字符序列构成 token	可变	`yy_nxt[][]` + `yy_accept[]`

mechanism_policy.c

// ========== 机制层（不变）==========
int state = 1;
while ((c = getchar()) != EOF) {
    buf[i++] = c;
    state = yy_nxt[state][c];    // ← 查表：机制调用策略
    if (state < 0) {
        act = yy_accept[-state]; // ← 查表：机制调用策略
        if (!(act == 1 || act == 21))
            printf("Pattern %d found! <%s>\n", act, buf);
        i = 0; state = 1;
        ungetc(c, stdin);
    }
}
// ========== 策略层（可替换）==========
// yy_nxt.c 和 yy_accept.c 的内容由 flex 从正则规则生成

7.2 换表实验

如果换一张识别 Python 词法的转移表，同样的 main 循环就能变成一个 Python 词法分析器。机制层的代码一行都不用改。

这就是软件工程中「分离变化与不变」的经典实践：

把不变的逻辑提炼为机制（框架）
把可变的配置抽取为策略（数据）
机制通过接口（这里就是二维数组查表）调用策略

IMPORTANT

这种思想不仅适用于编译原理。数据库的查询优化器（机制不变，统计信息可变）、图形渲染管线（管线不变，着色器可变）、Web 框架的路由匹配（匹配引擎不变，路由表可变）——都是同一模式的不同应用。

7.3 flex 如何生成转移表

yy_nxt.c 和 yy_accept.c 不是手写的，而是由 flex（Fast Lexical Analyzer Generator）从正则规则自动生成：

flex 输入 (.l 文件):
%%
"int"       { return KEYWORD; }
[a-z]+      { return IDENTIFIER; }
[0-9]+      { return NUMBER; }
...
%%

↓ flex 编译

输出: lex.yy.c (包含 yy_nxt[], yy_accept[], DFA 循环)

flex 的工作流程：

将每条正则规则转换为 NFA（非确定有限自动机）
用子集构造法将 NFA 转换为 DFA
用 Hopcroft 算法最小化 DFA
将最小化 DFA 输出为 yy_nxt 和 yy_accept 表格

对于本课，你不需要理解这些算法细节（那是编译原理课程的内容），但你需要理解 DFA 表格的使用方式——查表驱动状态转移。

7.4 DFA vs NFA：为什么需要确定化

正则表达式天然对应 NFA（非确定有限自动机）。考虑规则 [a-z]+ 和 "int"：

NFA 在读入 i 时，可能同时处于「标识符路径」和「int 关键字路径」两个状态
这种「同时处于多个状态」就是非确定性（Nondeterministic）

DFA 消除非确定性，保证每个（状态, 字符）对只有唯一的下一状态。这需要把 NFA 的状态集合映射为 DFA 的单个状态——子集构造法（subset construction）。

nfa_vs_dfa.c

// NFA（概念层面）：同时追踪多个状态
//   active_states = {S_id, S_int}
//   读到 'n' → 两个状态分别转移 → 新的 active_states

// DFA（实际实现）：只有一个当前状态
//   state = yy_nxt[state][c];  // 确定性的单步转移

从编程角度看，DFA 的优势在于：单线程、单变量、O(1) 每字符。你不需要维护状态集合，不需要回溯。这就是为什么所有实用的词法分析器都用 DFA 而不是 NFA——即使 DFA 的状态数可能是指数级增长的（实际中远小于理论最坏情况）。

7.5 二维数组 vs 一维索引

yy_nxt[state][c] 在 C 中的实际地址计算是：

地址 = yy_nxt + state * 128 * sizeof(int) + c * sizeof(int)

这里 128 是第二维的大小。回顾 Lesson 14（迷宫），我们学习过二维数组的行优先存储：同一行的元素在内存中连续排列，yy_nxt[0] 和 yy_nxt[1] 之间相隔 128 × 4 = 512 字节（假设 int 为 4 字节）。

row_major.c

// 遍历所有 128 个字符在状态 1 下的转移
for (int ch = 0; ch < 128; ch++) {
    if (yy_nxt[1][ch] != 0)
        printf("state 1 + '%c' → state %d\n", ch, yy_nxt[1][ch]);
}

由于行优先存储，这个循环的内存访问是顺序的，对 CPU 缓存非常友好。每次查表 yy_nxt[state][c] 本质上是两次数组索引：先找到第 state 行的起始地址，再在第 state 行内偏移 c 个元素。

7.6 内存中的状态机

把 yy_nxt 想象成一幅巨大的 ASCII 图，每一行代表一个状态，每一列代表一个 ASCII 字符。这个表格就是状态机的「完整定义」——它精确描述了在所有状态下面对所有输入时的行为。

         NUL SOH STX ... ' ' ... '0' '1' ... 'A' ... 'a' 'b' ... 'z' ... DEL
state 0:   0   0   0 ...   0 ...   0   0 ...   0 ...   0   0 ...   0 ...   0
state 1:   3   4   4 ...   5 ...   0   0 ...  28 ...  28  28 ...  28 ...   4
state 2:   3   4   4 ...   5 ...   0   0 ...  28 ...  28  28 ...  28 ...   4
state 3:  -3  -3  -3 ...  -3 ...  -3  -3 ...  -3 ...  -3  -3 ...  -3 ...  -3
...

观察这个表格，你会发现：

状态 0 是全 0 行——它是一个「吸收」状态，任何字符都不会改变它
状态 1 和状态 2 的很多列完全相同（因为它们在初始状态下行为相似）
状态 3、4、5、6... 都是全负数行——它们是终止状态，读入任何字符都会触发 token 边界

这些模式就是表格压缩算法利用的规律。

参考解答

参考解答：完整的 main 函数

mylex_solution.c

#include <stdio.h>
#include "yy_nxt.c"
#include "yy_accept.c"

#define debug(fmt, args...)	fprintf(stderr, fmt, ##args)

int main(void)
{
	int state = 1;
	char buf[64];
	int i = 0;

	while (1)
	{
		char c;

		c = getchar();
		if (c == EOF)
			break;

		buf[i++] = c;

		debug("\tstate = %d, ", state);

		state = yy_nxt[state][c];

		debug("c = <%c>, new state = %d\n", c, state);

		if (state < 0)
		{
			int act = 0;

			state = -state;
			act = yy_accept[state];
			buf[i-1] = '\0';

			// 1: \n   21: space
			if (!(act == 1 || act == 21))
				printf("Pattern %d found! <%s>\n", act, buf);
			i = 0;

			state = 1;
			ungetc(c, stdin);
		}
	}

	return 0;
}

解析：整个 DFA 主循环只有 30 行代码。核心流程：getchar 读字符 → 积累到 buf → 查 yy_nxt 转移 → 如果 state < 0 则查 yy_accept 输出 token → 回退字符 → 重置。注意 buf[i-1] = '\0' 的时机：必须在查 yy_accept 之后、输出之前执行，因为触发终止状态的字符已经被写入 buf，需要用 \0 覆盖它。

转移表片段解读

让我们解读 yy_nxt 中状态 1 的第一行（初始状态）：

yy_nxt_state1.c

// yy_nxt[1] — 初始状态的转移表
{
    3,    4,    4,    4,    4,    4,    4,    4,    4,    5,  // 0-9
    6,    4,    4,    4,    4,    4,    4,    4,    4,    4,  // 10-19
    ...
    // ASCII 32 (空格): yy_nxt[1][32] = 5 → 转移到状态 5 (处理空白)
    // ASCII 10 (\n):   yy_nxt[1][10] = 6 → 转移到状态 6 (处理换行)
    // ASCII 'a'-'z':  yy_nxt[1][97..122] → 转移到标识符/关键字处理状态
    // ASCII '0'-'9':  yy_nxt[1][48..57]  → 转移到数字处理状态
    ...
}

从初始状态开始，不同的字符会把状态机导向不同的处理路径：

字母 → 标识符/关键字路径
数字 → 数值字面量路径
引号 → 字符串字面量路径
运算符 → 运算符路径
空白 → 空白路径

这就是 DFA 的「分流」机制——通过初始状态的一次查表，将输入分流到对应的处理子流程。

课堂讨论

讨论题

如果去掉 ungetc(c, stdin)，程序的行为会有什么变化？以输入 int x=42; 为例，逐步推演会输出什么。
buf[i-1] = '\0' 能否移到 act = yy_accept[state] 之前执行？为什么？
debug 宏为什么要输出到 stderr 而不是 stdout？如果在正式代码中保留 debug 输出会有什么问题？
如果换一张识别 JSON 词法的转移表，main 循环需要修改哪些部分？
二维数组 yy_nxt[state][c] 中，c 是 char 类型（-128~127），但数组的第二维声明为 128。如果输入的字符是扩展 ASCII（128-255），会发生什么？
本课的 yy_nxt 约 139 个状态 × 128 个字符 ≈ 17000 多个条目，但大多数是重复的。思考一下：如何压缩这张表以减少内存占用？（提示：思考状态 3、4、5、6 之间的关系）

讨论答案

Q1: 去掉 ungetc 的影响

以输入 int x=42; 为例推演。当 DFA 读到空格时：

状态转移: state 78 + ' ' → state -3 (终止)
act = yy_accept[3] = 63 (int 关键字)
buf = "int " → buf[i-1]='\0' → buf = "int"

如果有 ungetc：空格被退回，下一轮 getchar() 重新读到空格。空格触发 pattern 21（空白），被跳过。然后继续读 x。

如果没有 ungetc：空格已经被消费，不会被重新读到。下一轮 getchar() 读到 x，开始积累 "x"。看起来似乎也正确？

但实际上 int 之后的空格可能不止一个。如果输入是 int x=42;（两个空格）：

有 ungetc：第一个空格被退回 → 下一轮读到空格 → 识别 pattern 21（跳过）→ 再读下一个空格 → 再跳过 → 然后读 x
没有 ungetc：第一个空格被消费 → 下一轮读到第二个空格 → 识别 pattern 21（跳过）→ 然后读 x

在这个特定输入下，行为恰好也正确——因为空格被正确处理了。但考虑另一种情况：

输入 intx=42;（int 和 x 之间没有空格）：

int 在读到 x 时触发终止（yy_nxt[78]['x'] 可能为负数）
有 ungetc：x 被退回，下一轮重新读到 x，正确识别为标识符
没有 ungetc：x 丢失！下一轮读到 =，输出变成 Pattern xx found: int 然后 Pattern yy found: =42;

所以 ungetc 是必需的——它确保触发 token 边界的字符不会丢失，会在下一轮被正确处理。

Q2: buf[i-1]='\0' 能否提前

不能。act = yy_accept[state] 查的是 state（终止状态编号），与 buf 的内容无关。所以从功能上看，buf[i-1] = '\0' 放在 act = yy_accept[state] 之前或之后都不会影响 act 的值。

但从代码可读性角度看，放在 act 之后更清晰：

// 推荐顺序：先查动作，再截断字符串，再输出
state = -state;
act = yy_accept[state];  // 1. 查出 token 类型
buf[i-1] = '\0';         // 2. 截断触发字符
printf("...", act, buf); // 3. 输出

这个顺序体现了「先获取元数据，再准备数据，最后输出」的逻辑流程。如果提前执行 buf[i-1] = '\0'，代码意图不如这个顺序直观。

Q3: debug 输出到 stderr 的原因

stderr 和 stdout 是两个独立的输出流。关键区别：

特性	stdout	stderr
缓冲	行缓冲（连终端）或全缓冲（连管道）	无缓冲
重定向	`>` 和 `	` 重定向 stdout
用途	程序正式输出	错误和诊断信息

如果 debug 输出到 stdout：

bash

./mylex < input.c | grep "Pattern"   # grep 会看到 debug 输出，干扰匹配
./mylex < input.c > output.txt       # debug 信息混入正式输出

输出到 stderr 则互不干扰：

bash

./mylex < input.c > output.txt 2>debug.log
# output.txt: 只有 Pattern xx found: ...
# debug.log: 只有 state = 1, c = <i>, new state = 46 ...

练习系统也依赖这种分离：测试用例只检查 stdout，stderr 上的 debug 输出不影响判题。

Q4: 换 JSON 词法表后的修改

main 循环不需要修改任何一行代码。这就是「机制与策略分离」的威力。

只需要替换 yy_nxt.c 和 yy_accept.c 文件（由 flex 从 JSON 词法规则生成），main 循环完全不变：

// 同样的主循环，不同的转移表
state = yy_nxt[state][c];  // 现在走 JSON 词法的状态转移
if (state < 0) {
    act = yy_accept[-state]; // 现在查 JSON token 类型
    // ...
}

当然，如果 JSON token 的 pattern 编号分配不同（比如空格变成了 pattern 5 而不是 21），你需要更新 if (!(act == 1 || act == 21)) 中的过滤条件。但这是配置的调整，不是机制的修改。

更好的做法是把「需要跳过的 pattern 列表」也放到策略层：

// 策略层
static int skip_patterns[] = {1, 21, -1};  // -1 表示列表结束

// 机制层
int should_skip = 0;
for (int j = 0; skip_patterns[j] != -1; j++) {
    if (act == skip_patterns[j]) { should_skip = 1; break; }
}
if (!should_skip) printf(...);

这样连过滤条件也变成策略了，换语言时只需修改 skip_patterns 数组。

Q5: char 类型与数组下标

C 标准中，char 可以是 signed 或 unsigned，这由编译器决定。在 x86/x86_64 上，char 通常是 signed，范围是 -128 到 127。

yy_nxt 的第二维声明为 [128]，有效下标是 0 到 127。如果输入字符的 ASCII 码在 0-127 范围内（标准 ASCII），使用 yy_nxt[state][c] 是安全的。

但如果遇到扩展 ASCII（128-255），char c 如果是 signed，这个值会是负数（-128 到 -1），导致数组越界访问！

安全的做法：

safe_char_index.c

unsigned char c;  // 声明为 unsigned，保证 0-255
// 或者
state = yy_nxt[state][(unsigned char)c];  // 使用时强制转换

对于本课的 C 语言词法分析器，源代码只包含 ASCII 可打印字符（加上换行和制表符），全部在 0-127 范围内，所以 char c 是安全的。但如果你要处理 UTF-8 编码的中文注释，就需要考虑这个问题。

Q6: 压缩转移表

观察 yy_nxt 可以发现，许多状态行几乎完全相同。例如：

状态 3:  全 -3（任何字符都到终止状态 3）
状态 4:  全 -4（任何字符都到终止状态 4）
状态 5:  全 -5
...

这些「全终止」状态完全没必要存储完整行。一种经典的压缩方法是base/default/check/next 四数组法：

base[state]:   基地址
default[state]: 回退状态（如果当前状态没有对应转移）
check[index]:  验证该转移属于哪个状态
next[index]:   转移目标

查询过程：

compressed_dfa.c

int next_state(int state, int c) {
    int idx = base[state] + c;
    if (check[idx] == state)
        return next[idx];     // 命中
    else if (default[state] != 0)
        return next_state(default[state], c);  // 回退到默认状态
    else
        return 0;             // 未定义转移
}

这种方法可以将 139 × 128 ≈ 17000 个条目压缩到几千个。flex 生成的代码实际上就使用了类似的压缩技术（yy_ec、yy_meta、yy_base、yy_def、yy_nxt、yy_chk 等数组协同工作）。本课为了教学清晰性，使用了未压缩的二维数组。

Q7: 为什么状态从 1 开始而不是 0

观察 yy_nxt 的第 0 行——全部是 0。状态 0 是一个特殊的「吸收状态」：一旦进入状态 0，无论读入什么字符都留在状态 0，永远不会到达终止状态。

// yy_nxt[0] — 全 0 行
{
    0, 0, 0, ..., 0   // 128 个 0
}

为什么需要这个状态？在 flex 生成的 DFA 中，状态 0 表示「错误恢复」——当词法分析器遇到无法匹配任何规则的字符序列时，它会进入状态 0，然后尝试跳过问题字符并重新开始。这是一种「容错」机制。

但在我们简化的实现中，初始状态设为 1 而不是 0：

状态 1 是真正的初始状态，对应「还没开始读任何有意义的字符」
状态 0 永远不会被主动进入，它只是一个安全兜底

如果初始状态设成 0，第一次查表 yy_nxt[0][c] 总是返回 0，永远无法开始识别 token。这就是为什么 int state = 1 而不是 int state = 0。

课后练习

练习 1：追踪状态转移

修改程序，在每个 token 输出之后，额外打印该 token 经过的状态转移路径。例如对于 int：

Pattern 3 found: <int>
  Path: 1 -> 46 -> 62 -> 78

提示：维护一个 int path[64] 数组，每次查表前记录当前状态，token 识别后打印。

知识点提示：状态转移路径可以直观展示 DFA 的工作过程。你需要一个 path 数组和一个 path_len 变量，在 state = yy_nxt[state][c] 之前记录当前状态。

参考解答

trace_path.c

#include <stdio.h>
#include "yy_nxt.c"
#include "yy_accept.c"

#define debug(fmt, args...)	fprintf(stderr, fmt, ##args)

int main(void)
{
	int state = 1;
	char buf[64];
	int i = 0;
	int path[64];       // 状态转移路径
	int path_len = 0;

	while (1)
	{
		char c;

		c = getchar();
		if (c == EOF)
			break;

		buf[i++] = c;

		path[path_len++] = state;  // 记录转移前的状态

		debug("\tstate = %d, ", state);
		state = yy_nxt[state][c];
		debug("c = <%c>, new state = %d\n", c, state);

		if (state < 0)
		{
			int act = 0;

			state = -state;
			act = yy_accept[state];
			buf[i-1] = '\0';

			if (!(act == 1 || act == 21)) {
				printf("Pattern %2d found: <%s>\n", act, buf);
				// 打印状态转移路径
				printf("  Path: %d", path[0]);
				for (int j = 1; j < path_len; j++)
					printf(" -> %d", path[j]);
				printf("\n");
			}

			i = 0;
			path_len = 0;
			state = 1;
			ungetc(c, stdin);
		}
	}

	return 0;
}

解析：path[path_len++] = state 在每次查表前记录当前状态。当 token 识别完成时，path 数组中存储了从初始状态到终止状态之间的所有中间状态。注意 path 数组需要在每次 token 输出后重置 path_len = 0。

练习 2：统计 token 分布

扩展程序，统计输入中每种 token 类型的出现次数。程序结束时输出一个统计表，按出现次数降序排列。输出格式：

Token Statistics:
  Pattern 27 (IDENTIFIER): 5
  Pattern 24 (NUMBER): 3
  Pattern 49 (OPERATOR): 2
  ...

提示：用两个数组 patterns[] 和 counts[] 记录每种 pattern 的出现次数。

知识点提示：你需要一个「查找-累加」模式——遍历已有的 pattern 列表，找到匹配的累加计数，找不到则添加新 pattern。这和 Lesson 24 课后练习 4 中的域名统计是同一模式。排序可以使用简单的冒泡排序或选择排序（回顾 Lesson 05）。

参考解答

token_stats.c

#include <stdio.h>
#include "yy_nxt.c"
#include "yy_accept.c"

int main(void)
{
	int state = 1;
	char buf[64];
	int i = 0;

	// 统计数据结构
	int patterns[100];   // 记录出现的 pattern 编号
	int counts[100];     // 对应的出现次数
	int pcount = 0;      // 不同 pattern 的数量

	while (1)
	{
		char c;
		c = getchar();
		if (c == EOF) break;

		buf[i++] = c;
		state = yy_nxt[state][c];

		if (state < 0)
		{
			int act = 0;
			state = -state;
			act = yy_accept[state];
			buf[i-1] = '\0';

			if (!(act == 1 || act == 21)) {
				printf("Pattern %2d found: <%s>\n", act, buf);

				// 查找-累加模式
				int found = 0;
				for (int j = 0; j < pcount; j++) {
					if (patterns[j] == act) {
						counts[j]++;
						found = 1;
						break;
					}
				}
				if (!found) {
					patterns[pcount] = act;
					counts[pcount] = 1;
					pcount++;
				}
			}

			i = 0;
			state = 1;
			ungetc(c, stdin);
		}
	}

	// 冒泡排序（按计数降序）
	for (int j = 0; j < pcount - 1; j++) {
		for (int k = j + 1; k < pcount; k++) {
			if (counts[j] < counts[k]) {
				int tmp;
				tmp = counts[j]; counts[j] = counts[k]; counts[k] = tmp;
				tmp = patterns[j]; patterns[j] = patterns[k]; patterns[k] = tmp;
			}
		}
	}

	// 输出统计
	printf("\nToken Statistics:\n");
	for (int j = 0; j < pcount; j++)
		printf("  Pattern %2d: %d\n", patterns[j], counts[j]);

	return 0;
}

解析：核心是「查找-累加」模式。patterns 和 counts 是平行数组——patterns[j] 和 counts[j] 是一对。排序时使用冒泡排序同时交换两个数组中的元素，保持配对关系。

练习 3：手动构造小型转移表

构造一个 DFA 转移表，识别三种 token：整数 [0-9]+、标识符 [a-z]+、分号 ;。只需要手动写一个小型的 yy_nxt 和 yy_accept，然后用本课的 main 循环驱动它。

状态设计提示：

状态 1（初始）：[0-9] → 状态 2，[a-z] → 状态 3，; → 终止，空格 → 状态 1（自环），其他 → 终止（非法）
状态 2（整数内）：[0-9] → 状态 2，其他 → 终止
状态 3（标识符内）：[a-z0-9] → 状态 3，其他 → 终止

知识点提示：转移表只对 c 在 ASCII 0-127 范围内有意义。状态 0 是全 0 行（占位）。终止状态用负数表示。yy_accept 的下标从 1 开始（flex 约定），你需要确保 pattern 编号与你的 skip 逻辑一致。

参考解答

mini_lexer.c

#include <stdio.h>

// 手动构造的小型 DFA 转移表
// 状态 0: 占位（未使用）
// 状态 1: 初始状态
// 状态 2: 整数内部
// 状态 3: 标识符内部
// 负数: 终止状态
static int yy_nxt[4][128] = {
    /* state 0 — 占位 */
    {0},
    /* state 1 — 初始状态 */
    [1] = {
        ['0']=2, ['1']=2, ['2']=2, ['3']=2, ['4']=2,
        ['5']=2, ['6']=2, ['7']=2, ['8']=2, ['9']=2,
        ['a']=3, ['b']=3, ['c']=3, ['d']=3, ['e']=3,
        ['f']=3, ['g']=3, ['h']=3, ['i']=3, ['j']=3,
        ['k']=3, ['l']=3, ['m']=3, ['n']=3, ['o']=3,
        ['p']=3, ['q']=3, ['r']=3, ['s']=3, ['t']=3,
        ['u']=3, ['v']=3, ['w']=3, ['x']=3, ['y']=3,
        ['z']=3,
        [';'] = -1,   // 分号: 终止状态 1
        [' '] = 1,    // 空格: 自环（留在初始状态）
        ['\t']= 1,
        ['\n']= 1,
    },
    /* state 2 — 整数内部 */
    [2] = {
        ['0']=2, ['1']=2, ['2']=2, ['3']=2, ['4']=2,
        ['5']=2, ['6']=2, ['7']=2, ['8']=2, ['9']=2,
    },
    /* state 3 — 标识符内部 */
    [3] = {
        ['a']=3, ['b']=3, ['c']=3, ['d']=3, ['e']=3,
        ['f']=3, ['g']=3, ['h']=3, ['i']=3, ['j']=3,
        ['k']=3, ['l']=3, ['m']=3, ['n']=3, ['o']=3,
        ['p']=3, ['q']=3, ['r']=3, ['s']=3, ['t']=3,
        ['u']=3, ['v']=3, ['w']=3, ['x']=3, ['y']=3,
        ['z']=3,
        ['0']=3, ['1']=3, ['2']=3, ['3']=3, ['4']=3,
        ['5']=3, ['6']=3, ['7']=3, ['8']=3, ['9']=3,
    },
};

// yy_accept: 下标从 1 开始
// 1: 分号, 2: 整数, 3: 标识符, 4: 空格
static int yy_accept[5] = {0, 1, 2, 3, 4};

int main(void)
{
    int state = 1;
    char buf[64];
    int i = 0;

    while (1) {
        char c = getchar();
        if (c == EOF) break;

        buf[i++] = c;

        if (c < 128)
            state = yy_nxt[state][(int)c];
        else
            state = 0;  // 扩展 ASCII，无定义

        if (state == 0) {
            // 未定义转移：非法字符
            fprintf(stderr, "Illegal char: <%c>\n", c);
            i = 0;
            state = 1;
        } else if (state < 0) {
            int act = yy_accept[-state];
            buf[i-1] = '\0';
            // pattern 4 是空格，跳过
            if (act != 4)
                printf("Pattern %d found: <%s>\n", act, buf);
            i = 0;
            state = 1;
            ungetc(c, stdin);
        }
    }

    return 0;
}

解析：使用 C99 的指定初始化器（designated initializer）[1] = { ... } 和 ['a'] = 3 来构造转移表，使表格的可读性大大提升。状态 2 和 3 中未指定的字符默认值为 0（未定义转移），当 DFA 读到这些字符时会触发非法字符检测。注意状态 1 中只有 ; 是终止状态（负数），[0-9] 和 [a-z] 是正常转移（正数），空格/制表符/换行是自环（留在状态 1）。

练习 4：支持字符串字面量

在本课的 main 循环基础上，添加对字符串字面量的特殊处理：识别到的字符串 token 输出时自动去掉首尾的双引号。例如输入 "hello world" 输出 Pattern xx found: <hello world>（不含引号）。

提示：在 buf[i-1] = '\0' 之后检查 buf[0] 是否是 '"'，如果是则用指针偏移跳过它。同时检查 buf[strlen(buf)-1] 是否是 '"'。

知识点提示：本课的词法分析器会将 "hello" 的引号也存入 buf。你需要检查 token 的首尾字符是否为引号，如果是则截掉。这与 Lesson 16 中 trim 函数去除空白字符的逻辑类似。

参考解答

string_token.c

// 在 printf 之前添加字符串处理
if (!(act == 1 || act == 21)) {
    char *display = buf;

    // 如果是字符串字面量，去掉首尾引号
    if (buf[0] == '"') {
        display = buf + 1;          // 跳过开头引号
        int len = strlen(display);
        if (len > 0 && display[len-1] == '"')
            display[len-1] = '\0';  // 去掉结尾引号
    }

    printf("Pattern %2d found: <%s>\n", act, display);
}

解析：display = buf + 1 让指针跳过第一个字符（开头的引号）。display[len-1] = '\0' 将结尾引号替换为 \0。注意这个修改会改变 buf 的内容，但在 token 输出后 buf 会被重置（i = 0），所以不影响后续 token 的处理。

练习 5：挑战 — 简单的语法归约

结合本课的词法分析器和第一节课介绍的 BNF 范式，编写一个函数，对词法分析器输出的 token 序列进行简单的语法检查。例如验证赋值语句是否符合「标识符 = 表达式 ;」的模式。

输入 token 序列后，检查：

标识符后面是否跟了 =
= 后面是否有表达式（标识符或数字）
语句是否以 ; 结束

知识点提示：这本质上是递归下降语法分析的简化版。你需要把 token 序列存入数组，然后编写检查函数。回顾 Lesson 14（DFS 回溯），语法分析中处理「多选一」的规则时也会用到类似回溯的思想，但这里简化为线性检查即可。

参考解答

simple_parser.c

#include <stdio.h>
#include <string.h>

#define MAX_TOKENS 256

typedef struct {
    int pattern;
    char lexeme[64];
} Token;

// 简易语法检查: 赋值语句 = IDENTIFIER '=' (NUMBER | IDENTIFIER) ';'
static int check_assignment(Token *tokens, int start, int count)
{
    if (start + 3 >= count) return 0;  // 至少需要 4 个 token

    int pos = start;

    // 1. 标识符
    if (tokens[pos].pattern != 27)  // 假设 27 是 IDENTIFIER
        return 0;
    pos++;

    // 2. '='
    if (tokens[pos].pattern != 49)  // 假设 49 是 '='
        return 0;
    pos++;

    // 3. 表达式: 数字或标识符
    if (tokens[pos].pattern != 24 && tokens[pos].pattern != 27)
        return 0;
    pos++;

    // 4. ';'
    if (tokens[pos].pattern != 60)  // 假设 60 是 ';'
        return 0;

    printf("Valid assignment: %s = %s;\n",
           tokens[start].lexeme, tokens[start+2].lexeme);
    return 1;
}

int main(void)
{
    // ... DFA 主循环（与参考解答相同）...

    // 收集所有 token
    Token tokens[MAX_TOKENS];
    int tcount = 0;

    // 在每次 printf token 时改为:
    // tokens[tcount].pattern = act;
    // strcpy(tokens[tcount].lexeme, buf);
    // tcount++;

    // DFA 循环结束后:
    printf("\n--- Syntax Check ---\n");
    for (int j = 0; j < tcount; j++) {
        if (check_assignment(tokens, j, tcount))
            j += 3;  // 跳过已检查的 token
    }

    return 0;
}

解析：check_assignment 模拟了语法分析器的核心逻辑——按顺序检查 token 类型是否符合语法规则。这相当于手动实现了 BNF 规则 assignment ::= IDENTIFIER '=' expression ';' 的识别器。真实的语法分析器会构建 AST（抽象语法树），这里简化为直接打印有效语句。

参考资料

cppreference: getchar — C 标准库 getchar 函数文档，包括返回值 EOF 的语义和错误处理
cppreference: ungetc — ungetc 函数文档，退回字符到输入流的机制和限制（最多退回一个字符）
cppreference: fprintf — fprintf 函数文档，包括 stderr 的无缓冲特性和格式化输出
flex 官方手册 — Flex（Fast Lexical Analyzer Generator）的完整文档，包含正则规则语法、DFA 生成算法、表格压缩技术
Compilers: Principles, Techniques, and Tools — 「龙书」，编译原理经典教材。第三章详细讲解了词法分析、NFA 到 DFA 的子集构造法、DFA 最小化等核心算法

"The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise." — Edsger W. Dijkstra

Lesson 21: 词法分析器 ​CNB

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 什么是词法分析 ​

1.1 Token 是什么 ​

1.2 编译器的前端流水线 ​

1.3 本课的范围 ​

2. DFA：确定有限自动机 ​

2.1 状态机回顾 ​

2.2 把状态机变成表格 ​

2.3 手工追踪：DFA 如何识别 int ​

3. 转移表的结构：yy_nxt ​

3.1 二维数组作为转移表 ​

3.2 转移表编码规则 ​

3.3 状态的渐进含义 ​

4. 动作表：yy_accept ​

4.1 终止状态到 token 类型 ​

4.2 Pattern 编号的含义 ​

5. 主循环详解 ​

5.1 字符积累与缓冲区 ​

5.2 字符回退：ungetc ​

5.3 空格和换行的过滤 ​

6. debug 宏与调试技巧 ​

6.1 变参宏 ​

6.2 调试 vs 正式输出的分离 ​

7. 机制与策略分离：DFA 的哲学 ​

7.1 两层的分工 ​

7.2 换表实验 ​

7.3 flex 如何生成转移表 ​

7.4 DFA vs NFA：为什么需要确定化 ​

7.5 二维数组 vs 一维索引 ​

7.6 内存中的状态机 ​

参考解答 ​

课堂讨论 ​

讨论题 ​

讨论答案 ​

课后练习 ​

练习 1：追踪状态转移 ​

练习 2：统计 token 分布 ​

练习 3：手动构造小型转移表 ​

练习 4：支持字符串字面量 ​

练习 5：挑战 — 简单的语法归约 ​

参考资料 ​

Lesson 21: 词法分析器 CNB

练习任务

核心知识点

代码框架

深度讲解

1. 什么是词法分析

1.1 Token 是什么

1.2 编译器的前端流水线

1.3 本课的范围

2. DFA：确定有限自动机

2.1 状态机回顾

2.2 把状态机变成表格

2.3 手工追踪：DFA 如何识别 `int`

3. 转移表的结构：yy_nxt

3.1 二维数组作为转移表

3.2 转移表编码规则

3.3 状态的渐进含义

4. 动作表：yy_accept

4.1 终止状态到 token 类型

4.2 Pattern 编号的含义

5. 主循环详解

5.1 字符积累与缓冲区

5.2 字符回退：ungetc

5.3 空格和换行的过滤

6. debug 宏与调试技巧

6.1 变参宏

6.2 调试 vs 正式输出的分离

7. 机制与策略分离：DFA 的哲学

7.1 两层的分工

7.2 换表实验

7.3 flex 如何生成转移表

7.4 DFA vs NFA：为什么需要确定化

7.5 二维数组 vs 一维索引

7.6 内存中的状态机

参考解答

课堂讨论

讨论题

讨论答案

课后练习

练习 1：追踪状态转移

练习 2：统计 token 分布

练习 3：手动构造小型转移表

练习 4：支持字符串字面量

练习 5：挑战 — 简单的语法归约

参考资料