第2章：词法分析与有限自动机

token 与模式

词法分析将字符流分成标识符、字面量、关键字和运算符，并保留源位置。正则表达式适合描述多数单词模式，例如标识符可以采用字母或下划线开头、后接字母数字下划线的规则。

字符串转义、注释和不同词法模式需要明确规定。任意深度嵌套括号不是有限自动机能够独立识别的语言；若语言允许任意嵌套注释，扫描器就要使用额外计数或栈等机制。

正则表达式可按连接、选择和闭包构造带 $\epsilon$ 边的 NFA。确定化把一组可能的 NFA 状态作为一个 DFA 状态：先取 $\epsilon$ 闭包，再对输入字符计算可到达状态集合。

若 NFA 有 $n$ 个状态，DFA 最坏可能有 $2^n$ 个状态。实践中不必假定所有集合都可达，可在构造时只生成实际可到达部分。

DFA 扫描每个字符只需一次状态转移，但生成器的构造规模和最终表大小仍需单独考虑。

多个规则能匹配时，通常取最长前缀；等长时使用规则优先级。例如输入 ifx 应作为一个标识符，而不是关键字 if 后接标识符 x。

扫描 a<=b 时，读到 < 已经处于一个接受状态，但还要继续尝试 <=。实现需要记录最后一次接受的位置，走到无法继续时回退到该位置，然后输出 token。

关键字可以作为高优先级规则，也可以先识别标识符再查关键字表。这两种实现都必须与语言的命名规则一致。

遇到非法字符时，诊断应指出源文件位置和无法识别的范围。若只报“解析失败”，后续语法分析很难定位真正原因。

Unicode 还带来字节偏移、码点和显示列的区别；制表符、组合字符也会影响显示。内部位置表示可以用字节偏移，但向用户展示时必须经过正确转换。