形式陈述

上下文无关文法 $G=(V,\Sigma,R,S)$$G=(V,\mathrm{\Sigma },R,S)$ 的解析树是一棵有根有序树：根标为 $S$$S$；内部节点标为非终结符；若节点 $A$$A$ 的有序子节点标签为 $X_1,\ldots,X_k$$X_1,\dots ,X_k$，则 $A\to X_1\cdots X_k\in R$$A\to X_1\cdots X_k\in R$；终结符或 $\varepsilon$$\epsilon$ 出现在叶处。按从左到右读取叶标签并删除 $\varepsilon$$\epsilon$ 得到树的产出。每棵解析树对应同一产生式偏序下的一族推导，其中最左推导和最右推导各自唯一。

直觉

推导序列记录“先展开哪个非终结符”，解析树则丢弃无关的操作顺序，只保留句子的层次组合结构，因此更接近程序的抽象语法结构。

例子与边界

表达式文法 $E\to E+E\mid E*E\mid a$$E\to E+E\mid E\ast E\mid a$ 对 a+a*a 可产生把加法置于根或把乘法置于根的两棵树，体现不同结合优先级。树的叶序必须与输入一致；任意标号树并非解析树。两个不同推导可能只是独立子树展开顺序不同，却对应同一解析树；因此歧义应比较解析树或最左推导，而不是比较任意推导序列。

两棵树的叶序同为 a + a * a，但根使用不同产生式，因此文法有歧义。

推论与应用

解析树是语法分析、编译器中间表示、属性文法和语义解释的入口；CNF 中的二叉解析树还使区间动态规划能够枚举所有可能切分。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。