说实话我当年刚开始做编译器前端相关的东西时对“词法分析器”这三个字是有些发怵的。直到有人甩给我一个工具名——lex/flex——我才发现原来大多数场景根本不需要手动去写那一大堆逐字符匹配的状态机代码。你只要把“什么样的文本算一个token”这件事用正则表达式的形式描述清楚工具就会自动帮你生成一个C语言的扫描器这就是词法分析器的生成器。如果你要写一门小语言、做一个配置文件解析器或者从日志里按规则抽取字段lex/flex大概率能让你省下大量时间。它适合所有愿意写一点C代码的人也适合刚接触编译原理的初学者。这篇文章我会把工作原理、常用写法、编译事项和踩坑经历一次性讲透尽量做到你照着抄就能跑通。1. 词法分析器到底在解决什么问题1.1 编译器里的第一站从字符流到token流任何一门语言的编译过程最前面那一站几乎都是词法分析。它做的事情说人话就是把一大段字符串切成一个个有意义的“小零件”。比如你读到一个while (i 10)人类一看就知道while是关键字(是左括号i是一个标识符10是一个数字。但机器拿到的是裸的字符序列它需要有一个程序来回答“这段文本里的每一个片段属于什么类型”。这个“片段”就是token。词法分析器的职责不是判断语法对不对而是把输入切成合理粒度的零件并给每个零件打上一个类型标签。比如原始字符token类型备注while关键字不能被当成普通标识符i标识符变量名运算符关系比较10整型字面量后续交给语法层去计算你可以把词法分析器想象成流水线最前端的“分拣员”它不管箱子里面装的东西是否合法只负责按标签把货物分到不同传送带上。语法分析器才是下一个环节的“质检员”负责检查货物的组合顺序是否合理。1.2 手写分析器与生成器这笔账要算清楚很多教材会让你手写词法分析器这也是一种必要的练习能帮你理解状态转移到底是怎么回事。但实际项目中手写一个覆盖几十种token类型的词法分析器代码量和维护成本都非常可观。你要管理状态、处理最长匹配、考虑各种边界情况稍不留神就会写出一个吞掉换行符或者死循环的bug。lex/flex这类生成器的逻辑其实不复杂你把词法规则写成.l文件用工具转换成一张确定型有限自动机的状态转移表最终生成一个 C 语言的yylex()函数。这个函数反复被调用每次返回一个token类型值。遇到复杂规则时生成器还会自动处理状态合并、转移表压缩这些事情省心得多。我个人的经验是教科书里的手写练习值得做但真实工程里最好还是先用工具把框架搭起来再去研究自动机细节。除非你的token类型极少、规则极其固定否则手写带来的控制感很快会被维护成本抵消。2. lex与flex选型前先把概念理清2.1 老牌lex与开源增强flex的关系lex是上世纪七十年代出现的经典工具是最早把正则表达式转成词法分析器的开创者之一。flexFast Lexical Analyzer是在lex的基础上发展出来的开源增强版兼容大部分lex语法同时又增加了很多现代特性比如更灵活的选项、可重入扫描器、更好的调试支持。现在绝大多数场景下你实际用的都是flex只是大家还习惯把这一类工具统称为lex。如果你在一些老文档里看到lex命令的写法拿到flex环境里跑通常也没问题。反过来如果你用了flex独有的高级特性那就不能指望传统的lex还能兼容了。我平时新建项目只考虑flex原因也很简单它还在活跃维护工具链成熟遇到问题网上能查到的资料也最多。既然功能向上兼容没必要跟自己过不去。2.2 环境准备装好之后先跑一个hello world安装flex并不复杂常见的Linux发行版一行命令就能搞定macOS用户用包管理器安装也很快。Windows用户我建议先装好一个类Unix的开发环境或者直接用现成的发行版工具包同样能在命令行里调用flex。装好之后你可以在任意目录建一个最简单的minimal.l文件%{ #include stdio.h %} %% hello printf(got hello\n); \n /* skip */ . printf(unknown: %s\n, yytext); %% int main(void) { yylex(); return 0; }然后在命令行执行flex minimal.l gcc lex.yy.c -o minimal你能看到一个名为lex.yy.c的文件被生成出来编译后运行程序随便输入几行文本程序就会根据规则打印出对应的信息。这一步跑通之后后面学什么都踏实。注意如果编译时提示yywrap未定义说明你的flex版本默认认为需要这个函数。最简单的解法是把规则区后面的用户代码里加上int yywrap(void) { return 1; }或者用%option noyywrap把这个依赖去掉。3. 最小可运行工程从.l文件到可执行程序3.1 三段式结构定义区、规则区、用户代码区任何一个.l文件都由三部分组成用%%分界线隔开结构如下定义区 %% 规则区 %% 用户代码区定义区里可以放C语言的头文件引用、宏定义、全局变量也可以定义一些flex特有的选项比如后面会讲到的start condition。规则区是核心每一行由“正则表达式 动作代码”组成。用户代码区则可以放你自己写的辅助函数比如main()、yywrap()这些内容会被原样复制到生成的C文件里。我第一次写的时候其实有点困惑为什么main()不放定义区后来理解了定义区的内容是放在生成的C文件的前部规则区在中间用户代码区的所有内容会追加到文件末尾。如果你的main()写在定义区它会被放在一堆宏和声明之间编译倒是不一定出错但逻辑上很乱也容易踩到重复定义的问题。3.2 一个能识别数字、标识符和运算符的demo你不需要一上来就写复杂规则。我建议先写一个能同时识别整数、浮点数、变量名和运算符的小扫描器这样你对token类型就会有直观感觉。%{ #include stdio.h %} %% [0-9] { printf(INT : %s\n, yytext); } [0-9]\.[0-9] { printf(FLOAT : %s\n, yytext); } [a-zA-Z_][a-zA-Z0-9_]* { printf(IDENT : %s\n, yytext); } |-|*|/ { printf(OP : %s\n, yytext); } [ \t\n] { /* skip whitespace */ } . { printf(OTHER : %s\n, yytext); } %% int yywrap(void) { return 1; } int main(void) { yylex(); return 0; }保存成lexer.l然后flex lexer.l gcc lex.yy.c -o lexer echo area 3.14 * 2 | ./lexer输出结果大致是IDENT : area OTHER : FLOAT : 3.14 OP : * INT : 2注意我故意把浮点数的规则放在整数规则后面但程序依然识别出了3.14作为一个整体而不是先匹配到3再匹配到.14。这就是flex著名的“最长匹配”原则在起作用我后面会专门讲。3.3 编译链路flex和gcc各自干了什么很多人第一次用的时候会好奇flex到底生成了什么gcc又在编译什么flex输入.l文件输出lex.yy.c。这个C文件里包含一张自动机的状态转移表和一个yylex()函数yylex()每调用一次就从上一次扫描的位置继续读输入并在匹配到最长的可用规则后执行对应的动作代码。gcc编译的就是这个生成出来的C文件不是你的.l文件本身。所以debug的时候思路要转换一下报错信息如果指向lex.yy.c那多半是你写的规则有问题或者动作代码里调用了未声明的东西。你可以直接看lex.yy.c去理解flex是怎么翻译规则的虽然里面的状态表很吓人但结构上无非是“读字符、查表、跳转、执行动作”这几个环节。用flex -d还能生成带调试信息的扫描器运行时会打印当前状态和读入的字符这对排查规则匹配异常特别有用。我平时遇到诡异的匹配问题第一反应就是开调试模式而不是盯着正则表达式盯着看半个钟头。4. 规则进阶最长匹配、状态机与易错正则4.1 常用正则语法与三个反直觉的坑flex支持的正则语法非常接近你熟悉的正则表达式的样子*表示零个或多个表示一个或多个[]表示字符集合()用于分组?表示可选|表示或^在文本头部表示行首$表示行尾...表示某个字符的字面量。三个坑值得单独拿出来说。第一个坑是转义。flex里的*和\*是两回事前者表示匹配一个星号字符本身后者在部分场景下也可以但我更推荐对单个符号统一用双引号括起来可读性好也少踩转义符的雷。第二个坑是点号。.在flex里匹配除换行符以外的任意单个字符如果某个输入片段意外落到.规则里它不会吞掉换行这通常是你想要的。但如果你在.的动作里啥也没干这个字符就被丢弃了有时候丢着丢着你才发现某些不该丢的字符不见了。第三个坑是中括号里的^。[^abc]表示匹配除了a、b、c以外的任意字符这个语法在排除字符时很常用但它跟行首的^不是一回事。别搞混。一个很容易让新手懵掉的细节是flex的模式是按最长匹配来决定选用哪条规则的。这跟你脑补的“从上往下第一个匹配到的规则生效”不一样。比如你有两条规则%% if { printf(KW\n); } [a-z] { printf(ID\n); } %%输入if时两条规则都能匹配但长度一样这时flex会优先选择先出现的规则所以会输出KW。但输入ifx时第一条规则只能匹配到前两个字符第二条规则能完整匹配整个ifx按最长匹配原则最终执行的是第二条规则输出ID。这个机制在书写规则时特别关键。你想让关键字优先匹配不能只靠规则顺序通常的做法是把关键字规则放在前面并且配合词边界。更稳的写法是用分隔符限定范围%% if { printf(KW\n); } [a-z] { printf(ID\n); } %%因为if用双引号括起来后是字面量而[a-z]匹配的是连续的字母串输入if时长度相同先出现的规则胜出这就能让关键字正常识别。如果你还是担心标识符里混入关键字可以在动作里查表也可以后续在语义层处理。4.2 最长匹配与规则顺序第一个规则不是优先级最高我再把这个点展开讲一下因为它是flex使用中最重要的思维转变。你写规则的时候会自然觉得“排前面的规则优先”。flex确实有这个规则但它的前提是在匹配长度相同的情况下。实际扫描时flex会先把当前扫描位置开始的所有字符都试一遍看哪条规则能从当前点匹配出最长的子串。只有长度完全一致时才会用规则定义的先后顺序来做裁决。举个例子%% [a-z] { printf(LOWER\n); } [a-z0-9] { printf(ALNUM\n); } %%输入abc123第一条规则匹配到abc就停了因为后面遇到数字第二条规则能一直匹配到abc123。虽然第一条写在前面但最终执行的是第二条规则。这解释了很多人的困惑为什么我把最简单的规则写在最上面反而匹配出来的不是我想要的结果。那么实际写规则时应该怎么排我的一般习惯是把空字符、注释这些必须优先丢弃的模式放前面。字面量精确匹配的关键字放前面防止被通配规则抢走。再放能匹配出较长内容的复杂规则。最后放单字符的兜底规则和错误处理规则。顺序不是唯一决定因素最长匹配才是。4.3 start condition处理注释、字符串与多行上下文有时候词法规则跟“当前处于什么上下文”强相关。比如C语言注释/* ... */不是一个单行能解决的事情你不能简单地用一条正则匹配到换行符为止。这时候就需要flex的start condition起始条件它本质上为扫描器引入了简单的状态。写法上先定义%x COMMENT%x声明了一个排他性的状态意思是当扫描器处于COMMENT状态时只匹配那些显式标记了COMMENT的规则其他普通规则全部失效。然后在规则区用BEGIN(COMMENT)来切换状态%{ #include stdio.h %} %x COMMENT %% /* { BEGIN(COMMENT); } COMMENT*/ { BEGIN(INITIAL); } COMMENT\n { /* skip */ } COMMENT. { /* skip */ } [a-z] { printf(WORD: %s\n, yytext); } [ \t\n] { /* skip whitespace */ } . { printf(OTHER: %s\n, yytext); } %%这个例子的思路是遇到/*就进入注释状态在注释状态下所有普通规则都被忽略直到看见*/再切回初始状态。INITIAL是flex内置的默认起始状态BEGIN(INITIAL)就是回到正常扫描。start condition还能用来做字符串字面量、模板嵌套、heredoc这类“进入某个状态后规则完全不同”的场景。它是flex里最实用的进阶功能我建议你上手第一周就试一遍。5. 和bison/yacc搭档拼一个完整的小编译器前端5.1 谁能拿到token词法与语法的交接很多场景下flex不会单独出场它会跟语法分析器生成器bison或经典叫法yacc配合。分工是这样flex负责把字符流切成tokenbison负责消费这些token并按语法规则归约。bison在生成代码时会用到一个外部函数yylex()这个函数的实现正是flex生成的。所以你在写.y文件时会声明一堆token类型比如%token NUMBER %token IDENTbison会把这些token定义写进一个头文件默认是parser.tab.h然后在flex的.l文件里直接include这个头文件通过return NUMBER;这样的方式把token类型返回给语法分析器。5.2 在flex里返回token与语义值这里有两个维度需要理清。第一个是token的类型也就是“我遇到了什么”用整数表示对应bison里的NUMBER、IDENT这些宏。第二个是token的语义值也就是“这个token的具体内容”通常通过全局变量yylval传递。bison生成的语法分析器会在每次调用yylex()后检查yylval把它作为非终结符的属性值。一个典型的flex片段长这样%{ #include stdio.h #include parser.tab.h %} %% [0-9] { yylval atoi(yytext); return NUMBER; } [a-zA-Z_][a-zA-Z0-9_]* { strcpy(yylval_str, yytext); return IDENT; } { return ; } [ \t\n] { /* skip */ } . { return yytext[0]; } %%如果你在bison里声明了%union那yylval会是一个联合体访问方式变成yylval.num atoi(yytext)这样的形式。这些细节在不同项目中略有差异但核心思路不变token类型用返回值表达语义内容用yylval传递。5.3 一个最小计算器前端的词法层长这样我在这里给一个完整可跑的最小例子。bison部分只做框架重点看flex里怎么跟bison对接。先写parser.y%{ #include stdio.h %} %token NUMBER %left - %% expr: NUMBER { printf(number: %d\n, $1); } | expr expr { printf(plus\n); } | expr - expr { printf(minus\n); } ; %% int main(void) { yyparse(); return 0; } int yyerror(char *s) { fprintf(stderr, error: %s\n, s); return 0; }然后在同一个目录创建lexer.l%{ #include stdio.h #include parser.tab.h %} %% [0-9] { yylval atoi(yytext); return NUMBER; } [ \t\n] { /* skip */ } . { return yytext[0]; } %%编译命令大致是bison -d parser.y flex lexer.l gcc parser.tab.c lex.yy.c -o calc运行./calc输入12你会发现语法分析器正确拿到了token并触发了对应的规则动作。这就是一个完整的、由生成器拼出来的编译器前端雏形。注意如果你忘了执行bison -d那就不会生成parser.tab.hflex代码include这个文件时就会报错。这个步骤顺序是实战中特别容易踩的。6. 疑难杂症排查实录从编译到运行的坑6.1 Windows下编译lex.yy.c报错在Windows环境编译lex.yy.c时最典型的报错是找不到unistd.h。这是历史遗留问题早期flex生成的代码默认包含这个Unix头文件但Windows默认没有。解法有好几种。如果你用的是较新版flex可以在生成代码时加参数跳过flex --nounistd lexer.l如果这个参数不存在就在.l文件定义区强行定义一个宏%{ #define YY_NO_UNISTD_H #include stdio.h %}还有一种办法是自己提供一个假的unistd.h但我不推荐绕开它更干净。这个问题的本质是flex生成的代码不够跨平台你需要在构建脚本里针对Windows做特殊处理而不是改生成的C代码。6.2 规则写错导致的无限循环flex扫描器本身是前进的但如果你的规则匹配到了空字符串扫描器位置不往前移动就会在同一个位置反复执行规则看起来就像死循环。比较常见的写法是把空白规则写成%% [ \t]* { /* do nothing */ } %%如果输入里恰好有换行符而你的空白规则没有匹配到\n那换行符就会落到后面的兜底规则里。反过来如果后面兜底规则也是.*这种能匹配空串的模式就可能卡住。排查这种问题一是看是否有某个规则匹配了yyleng 0的输入二是直接用flex -d开启调试观察扫描位置有没有推进。我自己的经验是任何规则都应该在动作里注意“输入是否被消费”尤其在处理空白和注释时宁可动作里什么都不做也要确保规则至少能消费掉一个字符。6.3 多个扫描器同时使用的符号冲突如果你在同一个程序里同时用两套flex生成的扫描器默认的符号都是yylex、yytext、yyleng这些链接时必然冲突。flex提供了一个前缀修改选项flex -Pmy_ lexer.l这样生成的函数名就会变成my_lex、my_text你可以在C代码里通过宏或者直接调用my_lex来使用第二套扫描器。这个功能在插件系统、多语言解析器里非常有用。需要注意前缀改了之后yywrap这些相关符号也会跟着变别漏了。当然如果你用%option reentrant生成可重入扫描器每个扫描器实例会有独立的上下文状态不会互相污染这是更现代的解法但复杂度也更高一点。6.4 调试工具与实践心法调试flex规则时我的习惯流程是这样的先用最小的输入片段复现问题比如只输入一个if、一个3.14、一个注释开头。用flex -d看每个字符进入的状态判断匹配路径是否符合预期。在规则动作里临时加打印语句输出yytext和yyleng确认到底是什么内容被匹配到了。一旦确认问题来自规则本身再回到正则表达式那行仔细看优先怀疑转义、字符集边界、最长匹配顺序这三个点。还有一个小技巧如果你不确定某条正则到底匹配了什么可以单独写一个只包含该规则的.l文件用最简形式做实验。这个“规则隔离”法能节省大量查资料时间。6.5 换行、空白和注释的边界处理语法规则里最容易被忽略的就是行尾和注释。比如你用.做兜底规则它不会匹配换行符但如果你的输入里连续出现多个\r\n不同平台的换行符也不一样最好在空白规则里显式写明%% [ \t\r\n] { /* skip */ } %%有些老项目在Windows和Linux之间切换时会发现行为不一致往往就是\r没被处理。我习惯从一开始就把\r\n都放进空白规则里不要依赖平台的默认行为。注释的处理也不只是“跳过”这么简单。你可以选择把注释内容通过另一个token类型暴露给上层也可以直接丢弃。对大多数项目丢弃是合理的但如果后续你想做源码映射、lint工具注释内容还是值得保留的。这个决策取决于你的项目目标而不是flex本身。7. 一些个人体会与使用建议用flex时间久了我觉得它最大的价值不是省掉了手写那个状态机的体力活而是强制你用“规则 动作”的角度去思考文本结构。以前我看一段文本只看到一整块字符串现在不自觉就会想这里该切成哪些token、哪些字符要当空白跳过、哪些字符串需要进入特殊状态去处理。这种思维方式对做工具链、做语言处理很有帮助。写到这里我想起一个比较实用的口头建议给新人不要一上来就追求写出一个全功能的flex配置。先跑通最简单的整数识别再逐步加标识符、字符串、注释每一步都保证能编译能运行。等规则多到你开始觉得维护困难时再去研究start condition和跟bison的对接自然水到渠成。flex这个工具老归老但直到今天它仍然是处理词法问题一个很可靠的起点。