Lex令牌匹配机制解析：为何file.yy.c中找不到定义的令牌？

Lex生成的词法分析器并不会直接存储你写的令牌字符串（比如你的"Hello"），而是把正则表达式（包括字面量）转换成表驱动的确定有限自动机（DFA）——这就是你在file.yy.c里看到的各种矩阵/表的作用。下面一步步拆解这个过程：

1. 从正则表达式到状态机 #

当你运行lex file.l时，Lex会完成以下核心转换：

• 把每条规则（这里是"Hello"）转换成非确定有限自动机（NFA）：用节点表示状态，边表示字符触发的状态转移。比如从初始节点出发，遇到'H'就进入下一个节点，依次对应'e'、'l'、'l'、'o'，最终到达一个「接受节点」（代表匹配成功）。
• 将NFA优化为更高效的确定有限自动机（DFA）：合并等价状态、消除不确定性，得到一个「当前状态+输入字符」对应唯一目标状态的状态机。

2. 状态机的表编码 #

Lex会把DFA转换成两个核心表（不同版本的Lex/Flex表名可能略有差异）：

• 状态转移表：这是一个二维数组，行代表当前状态，列代表输入字符的ASCII值，数组值代表转移后的目标状态。比如你的"Hello"规则会被编码成：初始状态下输入'H'对应状态1；状态1输入'e'对应状态2；状态2输入'l'对应状态3；状态3输入'l'对应状态4；状态4输入'o'对应状态5（接受状态）。
• 动作/接受表：记录每个接受状态对应的执行动作。你的puts("response\n");就存在这里，和状态5直接绑定。

这就是你看不到明文"Hello"的原因——它的匹配逻辑已经被编码成状态转移表中的数值关系，而非存储字符串本身。

3. 运行时的匹配流程 #

生成的词法分析器运行时，会按以下逻辑工作：

• 从输入流逐个读取字符；
• 从初始状态开始，根据当前字符和状态转移表，持续切换状态；
• 当走到某个接受状态时，触发对应的动作（也就是你的puts语句）；
• 如果遇到无法转移的字符，则回溯到最近的接受状态（如果存在），执行对应动作后，从下一个字符重新开始匹配。

关于你推测的switch语句 #

你提到的switch分支匹配是手写词法分析器的常见方式，但Lex选择表驱动DFA的原因是：

• 当规则数量多、正则表达式复杂时，表驱动方式比大量switch分支更高效；
• 可以自动处理Lex的核心规则——最长匹配原则，而手写switch很难高效实现这一点。

内容的提问来源于stack exchange，提问作者Maslin