《Crafting Compilers》中Switch实现的Tokenizer与形式化等概念的关联困惑

1. 先把核心概念掰扯清楚 #

• 词法语法（Lexical Grammar）：说白了就是一套规则，规定怎么把输入的字符流拆成一个个合法的token。比如“标识符必须以字母或下划线开头，后面可以跟字母、数字或下划线”“整数是一串连续的数字”，这些都是词法语法的具体规则。
• 正则语言（Regular Language）：是一类可以用正则表达式描述的语言，对应的计算模型是有限状态自动机（FSM）。它最大的特点是处理不了嵌套/递归结构，只能搞定扁平的字符序列——这也是为什么它刚好适合做词法分析：毕竟token都是扁平的（比如单个运算符、一串数字、一个标识符），不需要嵌套逻辑；但像(1+(2*3))这种带嵌套括号的表达式，正则语言就无能为力了，得靠后面的上下文无关文法来处理。

2. Switch-Case分词器就是正则语言的“代码实现版” #

你看到的Java switch case分词器，本质上是手写的有限状态自动机，而有限状态自动机正是正则语言的实现载体——换句话说，那段switch case代码，就是把词法语法的规则（属于正则语言范畴）用硬编码的方式写了出来，只是没给你写形式化的正则表达式而已。

拿书中处理数字的逻辑举例：
当读到一个数字字符时，代码会进入“收集数字”的逻辑，循环读取后续所有数字字符，直到碰到非数字的字符才停下，然后生成一个NUMBER token。这个过程对应的正则规则就是[0-9]+，而switch case的分支判断（比如判断当前字符是数字、字母还是符号），就是在模拟有限状态自动机的状态转移：

• 初始状态：等着读下一个字符
• 读到数字：切换到“数字收集状态”
• 在“数字收集状态”继续读到数字：保持状态，接着收集
• 读到非数字：退出状态，生成token，回到初始状态

再比如处理标识符：初始状态读到字母/下划线，就切换到“标识符收集状态”，后续只要是字母、数字或下划线就继续收集，直到碰到其他字符为止，生成IDENTIFIER token——对应的正则规则就是[a-zA-Z_][a-zA-Z0-9_]*。

书中没直接给形式化的词法语法定义，是因为它用代码逻辑替代了形式化描述，每一段switch分支、每一次状态跳转，都是在表达词法语法的规则，而这些规则全都是正则语言能覆盖的范围。

3. 为什么它适合扁平token，搞不定嵌套？ #

因为switch case实现的有限状态自动机，没有“记录嵌套层级”的能力。比如读到左括号(，它只能生成一个LEFT_PAREN token，但没法记住现在是第几层嵌套；而表达式的嵌套（比如((a+b)*c)）需要跟踪嵌套深度，这得用到栈结构，而正则语言的模型里没有栈——所以词法分析只负责拆出扁平的token，嵌套逻辑是后面语法分析的活儿。

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