推导和推导树是什么关系？

Question

它是在 ullman 的书中写的，但我不太了解它是如何工作的。即使在简单的上下文中，任何人都可以解释吗？我会很高兴。

Answer 1

推导是一些序列，以起始符号 S 开始，以语言中的字符串结束，中间步骤可能包含终结符和非终结符。序列中的每一步都使用产生式规则扩展一个非终结符。

解析树以起始符号为根，以终止符号为叶子，节点的子节点对应于产生式规则。

例如，对于语法 S -> a | 1 | S + S，a + a + 1 的推导可能是

S -> S + S -> a + S -> a + S + S -> a + S + 1 -> a + a + 1

对应的解析树可能是

   S
 / | \
S  +  S
|    /|\
a   S + S
    |   |
    a   1

此时要问的一些问题是：对于给定的语言或语法，特定的字符串是否只有一个解析树？只有一个推导？对于一个特定的推导，是否有一个唯一的解析树，或者反之亦然？