词法分析器的Token粒度划分：单阶段还是多阶段处理？

核心原则 #

Token粒度的选择，本质是明确词法分析与语法分析的职责边界：

• 词法分析负责无上下文的字符分组：把连续的、语义相关的字符打包成有意义的最小单元，这个过程不需要依赖Token的前后关系。
• 语法分析负责有上下文的结构组合：用Token构建符合语法规则的树状结构，需要依赖Token的顺序和上下文关系。

优先选择：单个Lexer生成粗粒度Token #

对于绝大多数场景（比如你提到的xy = 1.23），直接在单个Lexer里生成粗粒度Token是最优解，原因如下：

• 细粒度Token（比如letter、digit）完全是冗余的，后续Parser还要重新组合，既浪费性能又增加代码复杂度。
• 词法分析本来就该完成这类无上下文的分组：
  • 把连续字母拼成IDENTIFIER(xy)
  • 把数字+小数点+数字拼成DECIMAL(1.23)
  • 把=直接识别为EQ_SIGN
• 空白符处理：如果语法中空白符不参与语义（比如多数编程语言），直接在Lexer阶段过滤掉即可，无需生成Token；如果空白符有语义（比如Python缩进），再保留对应的Token类型。

示例（xy = 1.23的最优Token流）：

IDENTIFIER(xy) → EQ_SIGN → DECIMAL(1.23)

仅在特定场景考虑两阶段Lexer #

只有当字符分组需要简单的顺序上下文，但又不想让Parser承担过多非语法逻辑时，才需要拆分两阶段Lexer：

• 典型场景比如HTML标签：<b>test</b>的细粒度Token（lt、string、gt）需要组合成粗粒度的OPEN_TAG(b)、CLOSE_TAG(b)，这个过程需要依赖Token的顺序（比如lt后面跟着string再跟着gt才是开标签），但又不属于语法分析的核心职责（语法分析负责处理标签嵌套、文本内容的结构）。

两阶段Lexer的分工建议

• 第一阶段（细粒度Lexer）：生成最小单元的Token，比如单个符号（LT、GT、SLASH）、字符串片段（STRING(b)、STRING(test)），逻辑简单，状态机容易实现。
• 第二阶段（Token转换器）：遍历细粒度Token流，把相关序列组合成粗粒度语义Token，比如：
  • LT + STRING(b) + GT → OPEN_TAG(b)
  • LT + SLASH + STRING(b) + GT → CLOSE_TAG(b)

替代方案：单个Lexer处理复杂Token

如果你的场景（比如HTML标签）的分组逻辑可以用状态机实现，优先选择单个Lexer直接生成粗粒度Token。比如HTML开标签的识别逻辑：

1. 遇到<，进入标签状态
2. 读取直到>的所有字符，拆分出标签名和属性
3. 直接生成OPEN_TAG(name=b, attrs={...})

这种方式避免了多阶段的复杂度，代码更紧凑。

决策步骤总结 #

1. 梳理所需的粗粒度Token类型：比如标识符、关键字、运算符、字面量、标签等，判断每个Token的生成是否完全无上下文。
   • 是：直接用单个Lexer生成粗粒度Token，这是最简洁高效的方案。
2. 检查是否存在需要弱上下文的Token：比如需要依赖Token顺序才能确定语义的分组（如HTML标签）。
   • 是：如果单个Lexer的状态机过于复杂，再考虑拆分两阶段；否则优先用单个Lexer处理。
3. 绝对避免无意义的细粒度Token：不要为了「灵活」而刻意生成letter、digit这类Token，这会让Parser的工作量暴增，属于重复造轮子。

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