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 测试用例设计写完代码必须用一组覆盖边界情况的测试用例来验证。我一般会准备下面这些输入期望输出考察点abcIDENTIFIER(abc)基本标识符_tmpIDENTIFIER(_tmp)下划线开头a1_b2IDENTIFIER(a1_b2)字母数字下划线混合ifKEYWORD(if)关键字优先if_elseIDENTIFIER(if_else)关键字前缀不误判123abcNUMBER(123) IDENTIFIER(abc)数字开头abc123IDENTIFIER(abc123)数字结尾_IDENTIFIER(_)单独下划线__IDENTIFIER(__)双下划线a bIDENTIFIER(a) IDENTIFIER(b)空格分隔abIDENTIFIER(a) OP() IDENTIFIER(b)运算符分隔a.bIDENTIFIER(a) OP(.) IDENTIFIER(b)点号分隔中文ERROR 或 IDENTIFIER按规范非 ASCIIabcdefIDENTIFIER(abc) ERROR() IDENTIFIER(def)非法字符恢复这些用例跑一遍基本能覆盖标识符识别的主要边界。如果全过说明你的实现是靠谱的。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 常见问题速查表问题现象可能原因排查方法关键字被识别为标识符关键字表未初始化或判断顺序错误打印 is_keyword 返回值标识符被截断循环条件错误或缓冲区太小检查循环条件和缓冲区大小数字开头处理错误数字分支未正确停止检查数字扫描函数的退出条件下划线开头报错入口条件漏了下划线检查主循环分发条件行列号偏移advance 更新逻辑错误在关键位置打印行列号非 ASCII 字符崩溃字符分类函数未处理明确规范加边界检查内存泄漏lexeme 未释放用 valgrind 或类似工具检查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 错误恢复策略遇到非法字符时词法分析器不能直接崩溃要能恢复。常见策略是跳过非法字符记录错误继续扫描。比如abcdef识别出abc遇到报错并跳过然后识别def。这样一次扫描能报出多个错误而不是遇到第一个就停。错误恢复的质量直接影响编译器的用户体验。7.4 性能优化如果源文件很大标识符识别的性能就重要了。优化点包括减少函数调用开销把 is_letter 内联、用查表代替分支判断、预分配 lexeme 缓冲区、避免不必要的字符串拷贝。对于实验来说这些可能用不上但如果你想把词法分析器写进简历这些优化点值得了解。8. 我个人在实际操作中的体会标识符识别这个实验我前后做过不下五遍每次都有新收获。最大的体会是别小看任何一条看似简单的词法规则。[a-zA-Z_][a-zA-Z0-9_]*这行正则背后涉及最长匹配、关键字优先、错误恢复、字符编码、内存管理、性能优化等一系列工程问题。把它写对不难写健壮很难。另一个体会是测试用例比代码更重要。很多人写完代码随便跑两个用例就交结果边界情况全挂。我建议你花半小时设计一组覆盖各种边界的测试用例比多写一百行代码有用得多。上面那个测试用例表格你可以直接拿去用也可以自己扩展。最后分享一个小技巧如果你不确定某个输入应该怎么处理就去查你目标语言的官方规范或者看看主流编译器比如 GCC、Clang是怎么处理的。用gcc -E或者写个小程序测试一下比猜靠谱得多。编译原理实验不是闭门造车参考真实实现能让你少走很多弯路。这个内容后续还可以这样扩展把标识符识别和符号表构建连起来做一个简单的变量作用域检查或者把词法分析器扩展成能处理字符串字面量和字符字面量再或者用有限自动机的形式化方法重新推导一遍标识符规则加深理解。每一步扩展都会让你对编译器前端的理解更上一层。
