词法分析原理：正则表达式、有限自动机、Token定义
好，咱们今天聊聊词法分析。这是Verilog解析器的第一道关卡，说白了就是把源代码那串长长的字符流，拆成一个个有意义的“单词”——也就是Token。
我刚开始做编译器时，觉得词法分析挺简单的，不就是字符串匹配嘛。后来踩了不少坑才明白，这里面门道深着呢。尤其是Verilog这种硬件描述语言，关键词多、操作符杂、还有各种奇怪的数字格式，稍不留神就会解析出错。
正则表达式：词法规则的“速记本”
正则表达式，我们通常叫它regex。它是描述字符串模式的利器。在词法分析中，我们用正则来定义每个Token的“长相”。
举个例子，Verilog里的标识符（identifier）规则是：以字母或下划线开头，后面跟字母、数字、下划线或美元符号。用正则写就是：
[a-zA-Z_][a-zA-Z0-9_$]*是不是很直观？我个人习惯把常用的Token规则先列个表，这样写解析器时心里有数。
| Token类型 | 正则表达式 | 示例 |
|---|---|---|
| 标识符 | [a-zA-Z_][a-zA-Z0-9_$]* |
clk, rst_n, data_bus |
| 整数常量 | \d+ 或 \'[bdh][0-9a-fA-F]+ |
42, 8'hFF, 4'b1010 |
| 操作符 | \+|-|\*|\/|&&|\|\||==|!= |
+, &&, == |
| 关键词 | module|endmodule|input|output|wire|reg|always |
module, always |
这里有个坑：关键词和标识符的正则其实是冲突的。比如 module 既匹配关键词规则，也匹配标识符规则。怎么办？
优先级原则：关键词优先于标识符。在实现时，先匹配关键词列表，匹配不上再走标识符规则。
有限自动机：正则背后的“状态机”
正则表达式写起来爽，但计算机不认识啊。它需要把正则转换成有限自动机（Finite Automaton, FA）才能执行。
有限自动机分两种：
- NFA（非确定有限自动机）：同一个输入可能走到多个状态，实现简单但效率低。
- DFA（确定有限自动机）：每个输入只有一个确定的下一个状态，效率高，但构造复杂些。
实际工程中，我们通常先把正则转成NFA，再把NFA转成DFA。这个过程叫“子集构造法”。
我记得有一次，团队里有人直接用NFA做词法分析，结果大文件解析慢得像蜗牛。换成DFA后，速度提升了十几倍。嗯，这里要注意：生产环境一定要用DFA。
下面这张图展示了从正则到DFA的完整流程：
小技巧：实际开发中，我们很少手写DFA。用Lex或Flex这类工具，你写正则，它自动生成C代码。但理解原理很重要——遇到性能瓶颈时，你知道该从哪里优化。
Token定义：词法分析的“输出格式”
Token是词法分析器吐出来的东西。每个Token至少包含两个信息：类型和值。
在Verilog解析器中，我通常这样定义Token：
// 伪代码示例
typedef struct {
TokenType type; // 比如 TOKEN_MODULE, TOKEN_IDENTIFIER
char* lexeme; // 原始字符串，比如 "module", "clk"
int line; // 行号，用于报错
int column; // 列号，精确定位
union {
int int_val; // 如果是数字常量
char* str_val; // 如果是字符串
} value;
} Token;TokenType是个枚举，把所有可能的Token类型列出来。Verilog的Token类型大概有这些：
- 关键词：module, endmodule, input, output, wire, reg, always, assign, if, else, case, begin, end 等
- 标识符：用户自定义的变量名、模块名
- 数字常量：整数、实数、带基数的数字（如 8'hFF）
- 操作符：+ - * / & | ~ ^ && || == != < > <= >= << >> 等
- 分隔符：; , . ( ) [ ] { } # @
- 注释：// 和 /* */，通常词法分析时直接丢弃
- 空白符：空格、制表符、换行，同样丢弃
避坑指南：我曾经在解析Verilog的基数数字时栽过跟头。比如 8'hFF，有人写成 8'hff，还有人写成 8'HFF。大小写都要支持！另外，位宽和基数之间的单引号不能丢，丢了就是另一个意思了。
词法分析器的实现策略
写词法分析器，有两种主流做法：
- 手写递归下降：自己写一个状态机，逐个字符读，根据当前状态决定下一步。适合语法简单的语言。
- 自动生成：用Lex/Flex工具，写正则规则，工具帮你生成DFA代码。适合复杂语言，效率也高。
我个人偏好第二种。为什么呢？因为Verilog的词法规则实在太多了。手写状态机，光数字格式那部分就能让你写到怀疑人生。用Flex，几十行规则就搞定了。
但不管用哪种方式，核心逻辑都一样：
// 词法分析主循环（伪代码）
Token getNextToken() {
skipWhitespaceAndComments(); // 跳过空白和注释
if (isEndOfFile()) return TOKEN_EOF;
char c = peekChar();
// 根据首字符判断Token类型
if (isLetter(c) || c == '_') {
return readIdentifierOrKeyword();
}
if (isDigit(c)) {
return readNumber();
}
if (c == '\'') {
return readBasedNumber(); // 处理 8'hFF 这种
}
if (isOperatorStart(c)) {
return readOperator();
}
// ... 其他情况
}关键点：词法分析器要支持“回退”操作。有时候读多了字符，发现不是预期的Token，得能退回去。比如读到 <，可能是 < 本身，也可能是 <=。先读一个字符，发现后面是 =，就合并成 <=；否则退回。
嗯，说到回退，我记得有个经典bug：某次解析 a<=b 时，词法分析器把 <= 拆成了 < 和 =，结果语法分析阶段报错说“非法的赋值语句”。查了半天才发现是词法分析器没处理好最长匹配原则。
所以这里要记住：词法分析采用“最长匹配”原则。能匹配 <= 就不要只匹配 <。能匹配 module 就不要只匹配 mod。
好了，词法分析这块的核心内容就这些。正则表达式是规则描述工具，有限自动机是执行引擎，Token定义是输出格式。三者环环相扣，缺一不可。
实际写代码时，建议先把Token类型定义好，再写正则规则，最后生成DFA。顺序别搞反了，不然返工很痛苦的。
公众号:蓝海资料掘金营，微信deep3321