语法树

推导序列按时间记录“先展开哪个非终结符”，语法树则只保留最终的层次结构。两个推导若只是交换独立子树的展开顺序，会得到同一棵树；真正影响语法含义的是节点如何分组。树的叶序列还原输入，内部节点解释输入怎样由文法构造。它比 AST 更贴近具体文法，可能保留括号和辅助非终结符；编译器随后常把这些表面层次压缩成抽象语法。

对文法 $S\to aSb\mid \epsilon$ 和字 aabb，根用 $S\to aSb$，中间的 $S$ 再用 $aSb$，最内层用 ε；叶从左到右为 a a ε b b，产出 aabb。无论先展开外层树中哪个已经出现的非终结符，固定树对应的最左推导仍唯一。

边界是把“两个不同推导序列”直接当作歧义。只有得到不同语法树，等价地得到不同最左推导或最右推导，才构成文法歧义。语法树也不自动包含标识符绑定、类型和源位置，这些通常是后续 AST 注解。

文法歧义公理库文法歧义Grammar ambiguity某个字存在两个不同语法树或最左推导时文法具有的性质。以一个字是否拥有两棵不同语法树定义。Chomsky 范式公理库Chomsky 范式Chomsky normal form · CNF for grammars除空字特殊规则外，每条产生式只形如 A→BC 或 A→a 的上下文无关文法标准形。把内部节点限制为二叉结构，使 CYK 动态规划可按区间构造可能的树根。

解析器生成的具体语法树经消除辅助节点得到抽象语法树公理库抽象语法树Abstract syntax tree · AST把抽象语法构造表示为有根有序树的常见编译器数据结构。；属性文法、语义动作和类型检查再沿树传播信息。