7.1 具体语法树与抽象语法树
语法分析器(parser)首先证明词法单元(token)能组成合法句子,但后续阶段不一定要保存同一种树。具体语法树(CST)几乎逐字记录文法产生式、关键字、分隔符和辅助规则;抽象语法树(AST)保留后续真正需要的程序结构。
let total = price * count + 3; 的 CST 可能含 LetKeyword、ExprTail、Semicolon;AST 可写成:
LetStmt(total,
Binary(Binary(Name(price), *, Name(count)), +, Int(3)))AST 没丢失优先级(precedence):乘法位于加法左子树内。分号不再是语义子节点,但它的源码范围(source range)仍可用于诊断(diagnostic)。
从 CST 到 AST,谁会被保留
| 元素 | CST 中 | AST 中 | 原因 |
|---|---|---|---|
关键字(let、if) | 节点 | 通常是节点类型,非子节点 | 角色由节点种类表达 |
标点(;、,) | 节点 | 丢弃(范围可留) | 结构已知后不再是语义子节点 |
辅助规则(Term、ExprTail) | 节点 | 丢弃 | 文法脚手架,非程序含义 |
| 括号 | 节点 | 分组编码后丢弃 | 树形已记录优先级 |
| 标识符 / 字面量 | 叶子 | 叶子 | 携带真实程序数据 |
运算符(+、*) | 节点 | 节点种类/字段 | 决定计算方式 |
每一行的判断问题都是:删掉它会不会改变后续阶段的计算。只为帮语法分析器证明合法性的东西可以丢;任何消费者(consumer)还要读的东西必须留。
按消费者选择树
格式化器(formatter)、重构工具、源到源工具常需要注释、空白、原始括号和拼写,适合 CST/无损树;名字解析器(resolver)、类型检查器(type checker)、中间表示(IR)更需要声明(declaration)、表达式、语句、控制流,适合 AST。不是谁更正确,而是服务对象不同。
不要因为语法看似标点就删掉它。只有分组已由树形表达时才能删括号;类型注解即使不影响运行时(runtime),也可能是类型检查器必需信息。规则是:只有所有后续消费者都不需要时,语法才真正冗余。
解糖要保持语义
for init; test; step { body } 可降低为包含初始化的代码块与 while;while 主体末尾执行步进。这样后续只需实现一种循环,但必须保持作用域(scope)、continue、求值顺序和诊断。合成节点应保留原 for 的起始范围,否则错误会指向用户没写过的 while。
提示
打印同一程序的 CST/AST。若 AST 仍有 ExprTail、分号,通常太具体;若分不出 a+b*c 与 (a+b)*c,则太抽象。
例子对比:括号与注释
比较 a + (b * c) // subtotal 与 a + b * c。由于乘法优先级已经决定分组,某门语言可能为这两个表达式生成同一个 AST。但若格式化器承诺保留注释的位置,就不能只依赖该 AST:它还需要附着在词法单元上的琐碎信息(trivia),或一棵无损语法树。相反,类型检查器不应在抵达二元表达式前先遍历注释节点。这正是生产级工具往往同时保留两种相关表示、而不强迫一棵树承担互不兼容职责的原因。
解糖也有类似的边界。x += f() 可以降级为 x = x + f(),前提是读取 x 一次、赋值 x 一次与原语义等价。对于 array[index()] += f(),朴素的降级可能会执行两次 index()。安全的降级应引入临时变量,保持表达式的求值次数和求值顺序。
删除节点前要问的问题
- 移除它会不会丢掉用户可见的分组、注释、类型语法或错误位置?
- 降级后的形式会不会比原代码多求值任何一个源表达式?
- 格式化器或重构工具能否用收到的表示无损地往返还原该结构?