语法树

推导序列记录“先做哪一步替换”，语法树记录“哪一部分由哪条规则产生”。前者包含操作顺序，后者保留最终的层次和分组。两次推导若只是交换彼此独立的子树的展开顺序，可以得到完全相同的树。

每一步推导都能在待展开的叶子处接上对应产生式，逐步建成树；反过来，按某个合法顺序展开树中的非终结符，就能得到产出相同的推导。这解释了上面的等价关系。固定一棵树后，总展开最左非终结符便得到唯一最左推导，总展开最右者则得到唯一最右推导。

从局部产生式还原整个字符串 ​

对文法 $S\to aSb\mid \epsilon$，字符串 aabb 的语法树为：

        S
      / | \
     a  S  b
       /|\
      a S b
        |
        ε

外层 $S$ 和中层 $S$ 都使用 $S\to aSb$，最内层使用空产生式。叶从左到右是 a a ε b b，删去 $\epsilon$ 得到 aabb。对应推导为

这个例子每一步只有一个待展开的非终结符，适合说明嵌套结构，却不能用来展示“两个独立子树可以交换展开顺序”。

两个不同推导，可以是同一棵树 ​

改用文法 $S\to AB$、$A\to a$、$B\to b$。下面两个推导不同：

前者先展开 $A$，后者先展开 $B$；最终都得到同一棵树：

    S
   / \
  A   B
  |   |
  a   b

因此，发现两个一般推导序列不足以证明文法有歧义。这里的差别只在完成独立工作的先后，并不改变句子的结构。

真正的歧义：分组发生变化 ​

取文法 $E\to E+E\mid E\ast E\mid a$。同一个字符串 a+a*a 有两棵不同的完整语法树：

      E                      E
    / | \                  / | \
   E  +  E                E  *  E
   |    /|\              /|\    |
   a   E * E            E + E   a
       |   |            |   |
       a   a            a   a

左树的根使用加法产生式，右侧子树是乘法，对应分组 $a+(a\ast a)$；右树的根使用乘法产生式，左侧子树是加法，对应 $(a+a)\ast a$。两棵树的终结符叶序列相同，内部组合却不同，这才构成文法歧义公理库文法歧义Grammar ambiguity同一终端字有不同语法树的性质；通过完整推导区分展开次序、消歧改写、固有歧义与解析器冲突。。

这里的括号只用于说明分组，并没有出现在原字符串中。语法树表达组合结构；它是否对应数值加乘、如何求值，还需要给运算符指定语义。

用文法表达优先级 ​

希望乘法比加法结合得更紧，可以把文法分层：

表达式 $E$ 由加法连接“项” $T$，项内部再由乘法连接“因子” $F$。因此 a+a*a 的右侧乘法必须先组成一个项，再与左侧相加；左递归的结构还确定了同级运算的左结合。括号作为因子允许显式改变分组。

这是一种针对算术表达式的文法设计，不是把任何歧义文法自动变成无歧义文法的通用步骤。解析工具也可以在原文法之外使用优先级、结合性声明来选择解析结果，需要区分“文法本身无歧义”和“解析器有消歧规则”。

语法树也常称为具体语法树。它严格对应所选文法，可能保留括号、分隔符及 $E,T,F$ 这样的辅助层次。抽象语法树公理库抽象语法树Abstract syntax tree · AST把抽象语法构造表示为有根有序树的常见编译器数据结构。则突出程序结构，通常把纯辅助节点和可由结构恢复的标点省掉。二者不是同义词，也不必与源代码字符逐个对应：经过词法分析后，语法树叶子通常是 token，token 再携带原始词素与源位置。

从输入串构造本页的树，可以使用预测栈公理库LL(1) 预测分析LL(1) parsing · Predictive parsing以一个向前看token和无冲突预测表执行最左推导的确定解析算法。或移进归约栈公理库LR(0) 项目自动机与移进归约LR(0) parsing · LR(0) item automaton用项目自动机总结可行前缀，并以状态栈执行不依赖向前看的移进归约。；若文法有歧义，共享打包森林公理库广义 LR 与图结构栈Generalized LR parsing · GLR parsing以图结构栈共享冲突分支，并以打包森林保存多种语法树的LR泛化方法。会在同一输入区间下保留不同分组。类型、变量绑定与符号表信息不会由一棵未加注解的树自动出现，仍需语义动作、属性传播或后续遍历。

对已经给定的候选树，有限树自动机公理库有限树自动机Finite tree automaton · Bottom-up tree automaton · NFTA有限有序树上的状态汇总支持确定化、空性和语言差判定；可达闭包寻找有限运行，按节点数的动态规划构造最小反例树，并区分树与共享DAG的大小。可以自底向上检查固定文法的局部展开。接入固定秩字母表前，需要按“符号、孩子数”区分可能具有不同元数的标签；本页的空产生式仍保留零元的 $\epsilon$ 叶子，其非终结符父节点有一个孩子。这是检查树，不是把其产出字符串改用字 DFA 解析。

Chomsky 范式公理库Chomsky 范式Chomsky normal form · CNF for grammars除空字特殊规则外，每条产生式只形如 A→BC 或 A→a 的上下文无关文法标准形。的非终结符展开主要为 $A\to BC$，终结符产生式为 $A\to a$，另按约定处理开始符号的空串。因此分割非空区间的骨架是二叉的，但完整语法树仍含 $A\to a$ 的单孩子节点，不能笼统说“每个内部节点都有两个孩子”。CYK 算法公理库CYK 算法Cocke–Younger–Kasami algorithm用区间动态规划判定给定字是否属于 Chomsky 范式文法生成的语言。利用这个二分骨架，按子串区间记录哪些非终结符能作为根；保存分割点与产生式后，还可以恢复相应语法树。