词法分析器实现

词法分析器架构

词法分析器（Scanner）的核心组件：

• 输入缓冲：管理源程序字符流
• 预处理：过滤注释、空白字符、宏展开
• 扫描器：基于 DFA 识别单词
• 符号表：存储标识符等属性信息
• 属性字：输出单词的二元组 $⟨$ 种别码, 属性值 $⟩$

两种实现方法

表驱动法（数据驱动）

用状态转移矩阵 + 子表 + 三个寄存器实现：

• 状态寄存器：记录当前 DFA 状态
• 输入寄存器：存放当前输入字符
• 指针寄存器：指向输入串当前位置

主表（状态转移矩阵）+ 子表（不同词法单元的子 DFA），查表完成状态转移。优点是灵活易修改，缺点是查表开销大。

程序中心法（程序驱动）

将每个状态实现为一个函数或代码段，状态转移通过函数调用或 goto 实现：

state0:
    c = nextchar();
    if (is_digit(c)) goto state1;
    if (is_letter(c)) goto state2;
    ...

优点是执行效率高，缺点是状态增加时代码维护困难。

重点 两种实现方法的对比：表驱动法灵活、程序中心法高效。

最长匹配规则

当多个正规式匹配同一前缀时，选择匹配最长输入串的词法单元。

示例（$+$、$++$、$+=$ 三个正规式的合并 DFA）：

• 输入 + $\to$ 匹配 $+$
• 输入 ++ $\to$ 匹配 $++$（不是先匹配 $+$ 再匹配 $+$）
• 输入 += $\to$ 匹配 $+=$

实现方式：合并各词法单元 DFA，读入字符尽可能多，直到无法继续转移时确定匹配。

重点 最长匹配规则解决多正规式冲突，尽可能多地读入字符。