编译课程02
语法树
语法树的定义
句型结构的图示表示，是有向图
与推导式的对应大概有如下关系
-
结点：符号
- 根结点：识别符号
- 中间结点：非终结符
- 叶节点：终结符或非终结符（不一定推导完全，有可能只是某个句型对应的语法树）
-
有向边：结点间的派生关系。
其自顶向下的生成关系大致如下
推导关系相当于语法树的生成过程。每一步的推导等同于语法树的一支，最终生成句型w的语法树
注意，有些句子会有不同的推导过程(最左、最右、一般)，因此语法树的生成过程也会不同。但是最后生成的树的形状可能相同，也可能不同。（有无二义性的区别，具体会在后文提到）
例子如下：
子树和短语
- 子树：语法树中的一个结点及其所有后代结点的集合。此时那个结点就为子树的根。
- 短语：子树的末端结点按从左向右的顺序为句型中的符号串，则该符号串为该句型相对于该子树根的短语。
- 简单短语：所有叶子结点到子树根的路径为1的短语
- 句柄：最左边出现的简单短语
