context-free-grammar - What is the relationship between derivation and derivation trees?

Question

It was written in ullmans book but i did not under stand well how it works. Can anybody explain even in simple context? I'd be really glad.

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

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