编译原理实验二：标识符识别从入门到避坑指南

1. 从一段“看起来没问题”的代码说起

如果你正在上编译原理这门课，大概率已经写完了词法分析器的第一个版本，能识别关键字、运算符、界符，甚至能跳过注释和空白符。然后实验二的任务书发下来，标题就一行字：标识符的识别。很多人第一反应是“这不就是字母开头、后面跟字母或数字吗”，然后花十分钟写完正则，跑一遍测试用例，发现全过，就交差了。

但我带过几届学生的实验课，也帮不少人看过代码，实际情况是：标识符识别这一关，挂掉的人比想象中多得多。问题从来不在“字母开头”这个规则本身，而在于它和关键字、数字、下划线、大小写、长度限制、Unicode、错误恢复这些东西搅在一起之后，边界情况会像雨后春笋一样冒出来。更关键的是，标识符识别是后面语法分析、符号表管理、语义分析的地基，这里埋的坑，到实验三、实验四会加倍还回来。

所以这篇东西，我想从一个真正写过、调过、被测试用例折磨过的人的角度，把“标识符的识别”这件事从头到尾拆一遍。不管你是刚拿到实验任务不知道从哪下手，还是已经写完了但心里没底，或者想把它扩展成一个能写进简历的小型词法分析器，下面这些内容应该都能直接用上。

先明确一下范围：这里说的标识符识别，指的是在词法分析阶段，从源程序的字符流中，按照目标语言的词法规则，把标识符这个 token 准确地切出来，并且和关键字、数字、其他符号区分开。它看起来是词法分析里最简单的一类 token，但恰恰因为简单，很多人写得随意，最后在符号表、作用域、类型检查这些环节反复返工。

2. 标识符识别到底在识别什么

2.1 标识符的词法规则不是一句话能说完的

教科书上通常写：标识符是以字母或下划线开头，后跟字母、数字或下划线的字符序列。这句话没错，但它省略了太多工程细节。真正写代码的时候，你至少要回答下面这些问题：

• 字母包不包括大写？包不包括非 ASCII 字母？
• 下划线能不能开头？能不能连续出现？能不能结尾？
• 数字能不能出现在第一个字符之后？有没有长度限制？
• 关键字算不算标识符？如果不算，怎么区分？
• 标识符最大长度是多少？超长怎么办？
• 遇到非法字符怎么恢复？

这些问题没有标准答案，取决于你实现的是哪种语言的词法。C 语言、Java、Python、Go 的标识符规则都不一样。比如 Go 允许 Unicode 字母，Python 3 也允许，但 C 传统上只允许 ASCII 字母和下划线。所以第一步不是写代码，而是把你目标语言的标识符规则用形式化或半形式化的方式写清楚。

我一般会建议学生先写一个类似这样的规则描述：

identifier -> (letter | '_') (letter | digit | '_')* letter -> [a-zA-Z] 或按语言规范扩展 digit -> [0-9]

然后明确：关键字是标识符的子集，但在词法阶段通常优先匹配关键字，匹配不到再归为标识符。这个优先级顺序非常关键，后面会细说。

2.2 为什么标识符识别值得单独做一个实验

有人会问，标识符识别这么简单，为什么编译原理实验要单独列一个？我的理解是，这个实验的真正目的不是让你写一个正则，而是让你理解词法分析器的状态机本质、最长匹配原则、token 边界判定以及错误恢复。标识符恰好是这几件事的交汇点。

举个例子，输入abc123，你要能识别成一个标识符，而不是abc加123。输入123abc，你要能识别出数字123然后发现abc是非法或另一个 token。输入_tmp，你要能识别成标识符。输入if，你要能识别成关键字而不是标识符。输入if_else，你要能识别成标识符而不是if加_else。这些边界情况，才是实验真正想考你的东西。

而且，标识符识别直接决定了符号表的构建。符号表里存的就是标识符的名字、类型、作用域、地址等信息。如果词法阶段把标识符切错了，符号表就是错的，后面的语义分析全盘皆输。所以这个实验虽然小，但它是整个编译器前端的第一块多米诺骨牌。

2.3 适合谁来读这篇内容

如果你属于下面任何一类，这篇内容应该对你有用：

• 正在做编译原理实验二，不知道从哪开始，或者写完了但测试用例过不了；
• 想自己动手写一个简单的词法分析器，但不确定标识符这块怎么处理才规范；
• 已经工作了，想回顾一下词法分析的基础，或者面试前想快速复习；
• 对正则表达式、有限自动机这些概念有基本了解，但没真正把它们落到代码里过。

我不假设你有很深的编译原理背景，但假设你至少知道 token、词法分析、正则这些词大概是什么意思。如果不知道，也没关系，我会在关键地方用生活化的类比解释。

3. 核心思路与方案选型：手写状态机还是正则引擎

3.1 两种主流做法的取舍

实现标识符识别，常见的有两条路：一是用正则表达式或词法分析器生成工具（比如 lex/flex、ANTLR 等），二是手写一个字符扫描循环，也就是手写状态机。两条路都能走通，但适用场景不一样。

用工具的好处是快，写几条规则就能生成一个完整的词法分析器，标识符识别只是其中一条规则。但缺点是，你对底层发生了什么没有控制力，遇到边界情况或者需要自定义错误恢复时，会很被动。而且很多学校的实验明确要求手写，不允许用生成工具。

手写状态机的好处是完全可控，你能精确知道每一个字符是怎么被消费的，错误恢复也能自己设计。缺点是代码量稍大，需要自己处理各种边界。但对于标识符识别这种规则清晰、状态很少的场景，手写其实非常轻松，而且能让你真正理解词法分析的本质。

我的建议是：实验阶段一定手写。哪怕你以后工作用 ANTLR，现在手写一遍，你对 token 边界的理解会完全不一样。

3.2 手写状态机的核心结构

手写标识符识别，核心就是一个循环加一个状态变量。伪代码大概长这样：

Token scan_identifier() { start = current_pos; while (is_letter(peek()) || is_digit(peek()) || peek() == '_') { advance(); } lexeme = source[start..current_pos]; if (is_keyword(lexeme)) { return make_token(KEYWORD, lexeme); } return make_token(IDENTIFIER, lexeme); }

看起来很简单，但这里有几个关键决策点：

第一，入口条件。这个函数只应该在当前字符是字母或下划线时被调用。如果当前字符是数字，应该走数字识别的分支。所以主循环里要先判断首字符类型，再分发到不同的扫描函数。

第二，最长匹配原则。循环条件必须是“只要还是标识符允许的字符就继续”，不能提前退出。比如abc123，不能扫到abc就停，必须把123也吃进来。

第三，关键字优先。扫完之后，先查关键字表，命中就是关键字，否则才是标识符。这个顺序不能反。

第四，位置记录。start 和 current_pos 要准确记录，后面报错、生成符号表都要用。

3.3 为什么不用正则一把梭

有人会说，我用一个正则[a-zA-Z_][a-zA-Z0-9_]*不就行了？在 Python 里re.findall确实能跑。但问题是，词法分析不是独立的字符串匹配，它要和上下文交互。比如if到底是关键字还是标识符，取决于语言规范；比如abc.def里的点号怎么处理；比如错误恢复时怎么跳过非法字符。这些都不是一个孤立的正则能解决的。

更重要的是，正则引擎通常采用回溯或 NFA 模拟，性能和行为不如手写状态机可控。对于编译器这种对性能和确定性要求很高的场景，手写状态机是更专业的选择。当然，如果你只是做个 demo，正则也够用，但实验的目的不是 demo。

4. 核心细节解析：从字符分类到关键字表

4.1 字符分类函数怎么写才不出错

标识符识别依赖三个字符分类函数：is_letter、is_digit、is_underscore。看起来简单，但写错的人不少。

is_letter最容易被写成c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'。这在 ASCII 环境下没问题，但如果你的源文件包含中文注释或 Unicode 标识符，就会出问题。C 语言标准里，标识符的字母范围是实现定义的，但通常只保证 ASCII。如果你要实现一个支持 Unicode 标识符的语言（比如 Go 或 Python 3），就需要用更复杂的判断，比如查 Unicode 类别表。

对于实验来说，我建议先明确你的语言规范。如果任务书没说支持 Unicode，那就老老实实只支持 ASCII，别自己加戏。因为一旦引入 Unicode，字符编码、字节 vs 字符、长度计算这些问题会瞬间复杂十倍。

is_digit要注意的是，不要用isdigit()这种库函数直接判断，因为不同库对 Unicode 数字的处理不一样。自己写c >= '0' && c <= '9'最稳。

is_underscore就是c == '_'，但要注意有些语言允许$作为标识符字符（比如 Java），有些允许@（比如 C# 的特性），这些都要按规范来。

4.2 关键字表的构建与查找

关键字表本质上是一个字符串集合。实现方式有几种：

• 线性数组加循环比较：简单，但关键字多了性能差；
• 排序数组加二分查找：性能好，实现也不复杂；
• 哈希表：性能最好，但需要处理哈希冲突；
• 完美哈希：针对固定关键字集合，可以做到 O(1) 且无冲突，但生成过程复杂。

对于实验来说，关键字通常就几十个，线性比较完全够用。但如果你想写得专业一点，可以用排序数组加二分查找，或者用一个简单的哈希函数。

这里有个细节：关键字表应该在词法分析器初始化时构建一次，而不是每次识别标识符时重新构建。很多人把关键字数组写在函数里面，每次调用都重新初始化，性能很差。正确做法是放在全局或类成员里，初始化一次。

另外，关键字查找是大小写敏感的。if是关键字，IF通常不是（除非语言规范这么规定）。所以比较时要用精确匹配，不要用忽略大小写的比较。

4.3 标识符长度限制与截断策略

很多语言对标识符长度有限制。比如 C89 只保证前 31 个字符有效，C99 扩展到 63 个。有些老编译器只认前 8 个字符。如果你的实验要求模拟这种限制，就需要在扫描时做截断。

截断策略有两种：一是扫描时只保留前 N 个字符，后面的字符仍然消费但不存入 lexeme；二是扫描完整，然后在生成 token 时截断。两种都可以，但要注意，如果两个标识符前 N 个字符相同，它们会被认为是同一个标识符，这可能会影响符号表。所以截断策略要和符号表的设计一致。

对于大多数实验来说，其实不需要长度限制，因为测试用例不会那么长。但如果你想让代码更健壮，可以加一个最大长度检查，超过就报错或截断。

4.4 下划线的特殊处理

下划线在标识符里很常见，但有几个坑：

第一，单独一个下划线_是不是合法标识符？在 C 语言里是合法的，但在某些语言里_被用作通配符或占位符，可能被特殊处理。你要按规范来。

第二，双下划线开头__。C 语言里保留给实现使用，用户不应该定义。但词法阶段通常还是识别为标识符，语义阶段再报错。所以词法阶段不用特殊处理。

第三，下划线在数字里。有些语言允许数字里用下划线分隔，比如1_000_000。这属于数字识别的范畴，但如果你在标识符扫描函数里遇到1_000，首字符是数字，应该走数字分支，不要误入标识符分支。

5. 实操过程：从零写一个标识符识别模块

5.1 定义 Token 结构与词法分析器骨架

先定义 token 的类型和结构。一个简单的设计：

typedef enum { TOKEN_IDENTIFIER, TOKEN_KEYWORD, TOKEN_NUMBER, TOKEN_OPERATOR, TOKEN_EOF, TOKEN_ERROR } TokenType; typedef struct { TokenType type; char *lexeme; int line; int column; } Token;

词法分析器的主循环：

Token next_token() { skip_whitespace_and_comments(); if (is_at_end()) return make_token(TOKEN_EOF, ""); char c = peek(); if (is_letter(c) || c == '_') return scan_identifier(); if (is_digit(c)) return scan_number(); return scan_operator(); }

这个骨架很清晰：先跳过空白和注释，然后根据首字符分发。标识符识别的入口就是is_letter(c) || c == '_'。

5.2 实现 scan_identifier 函数

Token scan_identifier() { int start = current; int start_line = line; int start_column = column; while (!is_at_end() && (is_letter(peek()) || is_digit(peek()) || peek() == '_')) { advance(); } int length = current - start; char *lexeme = copy_substring(source, start, length); TokenType type = is_keyword(lexeme) ? TOKEN_KEYWORD : TOKEN_IDENTIFIER; Token token; token.type = type; token.lexeme = lexeme; token.line = start_line; token.column = start_column; return token; }

这里有几个细节：

• start记录起始位置，current是当前扫描位置，advance()负责移动 current 并更新行列号。
• 循环条件里!is_at_end()必须放在最前面，防止越界。
• copy_substring要分配新内存，不能直接指向 source，因为 source 可能会被修改或释放。
• 关键字判断在扫描完成后进行，这是最长匹配原则的体现。

5.3 关键字表的实现

static const char *keywords[] = { "if", "else", "while", "for", "return", "int", "float", "void", NULL }; int is_keyword(const char *lexeme) { for (int i = 0; keywords[i] != NULL; i++) { if (strcmp(keywords[i], lexeme) == 0) return 1; } return 0; }

如果关键字多，可以改成二分查找。但要注意，二分查找要求数组有序，所以关键字数组要按字典序排列。

5.4 字符分类函数的实现

int is_letter(char c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } int is_digit(char c) { return c >= '0' && c <= '9'; } int is_at_end() { return current >= source_length; } char peek() { if (is_at_end()) return '\0'; return source[current]; } char advance() { char c = source[current++]; if (c == '\n') { line++; column = 1; } else { column++; } return c; }

这些函数看起来简单，但advance里的行列号更新很容易漏。如果后面要报错，行列号不对，调试会很痛苦。

5.5 测试用例设计

写完代码，必须用一组覆盖边界情况的测试用例来验证。我一般会准备下面这些：

这些用例跑一遍，基本能覆盖标识符识别的主要边界。如果全过，说明你的实现是靠谱的。

6. 常见问题与排查技巧实录

6.1 关键字被误识别为标识符

这是最常见的问题。原因通常是关键字判断放在了标识符扫描之前，或者关键字表没初始化。排查方法：在scan_identifier里打印 lexeme 和 is_keyword 的返回值，看关键字判断是否生效。

另一个可能的原因是关键字表里有空格或大小写不一致。比如"if "带了个空格，或者"If"和"if"混用。检查关键字表定义，确保没有多余字符。

6.2 标识符被截断

如果输入abcdef只识别出abc，说明循环条件写错了。常见错误是循环条件里用了&&但优先级搞错，或者is_letter只判断了小写字母。检查字符分类函数和循环条件。

还有一种可能是缓冲区大小限制。如果你用固定大小的数组存 lexeme，超长标识符会被截断。改用动态分配或加大缓冲区。

6.3 数字开头的标识符处理错误

输入123abc，期望是数字123然后标识符abc，但有些实现会直接报错或把整个123abc当成非法。这是因为主循环里数字分支没有正确处理后续字母。数字扫描函数应该在遇到非数字字符时停止，然后让主循环继续处理。如果数字后面紧跟字母，有些语言会报错（比如 C 语言里123abc是非法预处理数字），有些语言会分开处理。按你的语言规范来。

6.4 下划线开头被拒绝

如果_tmp报错，说明入口条件只判断了is_letter，漏了_。检查主循环的分发条件。

6.5 行列号不对

报错时行列号偏移，通常是advance里更新逻辑有问题，或者start_line、start_column记录时机不对。建议在scan_identifier开头就记录行列号，而不是在advance之后。

6.6 常见问题速查表

6.7 几个我踩过的坑

第一个坑是用char判断 EOF。char可能是有符号的，EOF通常是 -1，直接比较可能出问题。建议用int存字符，或者明确用'\0'作为结束符。

第二个坑是字符串比较用==。C 语言里字符串不能用==比较，必须用strcmp。这个错误很低级，但调试时容易忽略。

第三个坑是忘记释放 lexeme。每次识别标识符都分配新内存，如果不在合适的地方释放，长时间运行会内存泄漏。建议在 token 使用完后统一释放，或者用内存池。

第四个坑是忽略注释里的标识符。如果注释跳过逻辑写错，注释里的if、abc会被当成真正的 token。检查skip_whitespace_and_comments的实现，确保注释被完整跳过。

7. 从实验到实战：标识符识别的扩展思路

7.1 支持 Unicode 标识符

如果你想让词法分析器支持中文标识符或 emoji，就需要处理 Unicode。核心是把is_letter扩展成按 Unicode 类别判断。可以用现成的库，比如 ICU，或者自己查表。但要注意，Unicode 字符可能占多个字节，所以扫描时不能按字节走，要按码点走。这会涉及 UTF-8 解码，复杂度不低。建议先明确需求，如果实验不要求，别自己加戏。

7.2 标识符的哈希与符号表

识别出标识符后，通常要插入符号表。符号表可以用哈希表实现，键是标识符字符串，值是类型、作用域等信息。哈希函数可以用经典的 djb2 或 FNV-1a。插入时要处理哈希冲突，可以用链地址法或开放地址法。这部分内容很多，这里不展开，但它是标识符识别的自然延伸。

7.3 错误恢复策略

遇到非法字符时，词法分析器不能直接崩溃，要能恢复。常见策略是跳过非法字符，记录错误，继续扫描。比如abc@def，识别出abc，遇到@报错并跳过，然后识别def。这样一次扫描能报出多个错误，而不是遇到第一个就停。错误恢复的质量直接影响编译器的用户体验。

7.4 性能优化

如果源文件很大，标识符识别的性能就重要了。优化点包括：减少函数调用开销（把 is_letter 内联）、用查表代替分支判断、预分配 lexeme 缓冲区、避免不必要的字符串拷贝。对于实验来说，这些可能用不上，但如果你想把词法分析器写进简历，这些优化点值得了解。

8. 我个人在实际操作中的体会

标识符识别这个实验，我前后做过不下五遍，每次都有新收获。最大的体会是：别小看任何一条看似简单的词法规则。[a-zA-Z_][a-zA-Z0-9_]*这行正则，背后涉及最长匹配、关键字优先、错误恢复、字符编码、内存管理、性能优化等一系列工程问题。把它写对不难，写健壮很难。

另一个体会是，测试用例比代码更重要。很多人写完代码随便跑两个用例就交，结果边界情况全挂。我建议你花半小时设计一组覆盖各种边界的测试用例，比多写一百行代码有用得多。上面那个测试用例表格，你可以直接拿去用，也可以自己扩展。

最后分享一个小技巧：如果你不确定某个输入应该怎么处理，就去查你目标语言的官方规范，或者看看主流编译器（比如 GCC、Clang）是怎么处理的。用gcc -E或者写个小程序测试一下，比猜靠谱得多。编译原理实验不是闭门造车，参考真实实现能让你少走很多弯路。

这个内容后续还可以这样扩展：把标识符识别和符号表构建连起来，做一个简单的变量作用域检查；或者把词法分析器扩展成能处理字符串字面量和字符字面量；再或者用有限自动机的形式化方法重新推导一遍标识符规则，加深理解。每一步扩展，都会让你对编译器前端的理解更上一层。