什么是语法树？

其中每个叶子节点描述一个操作数，每个内部节点描述一个运算符。语法树是语法分析树的简写形式。

示例 1 - 为字符串 a + b ∗ c − d 绘制语法树。

构建语法树的规则

语法树中的每个节点都可以作为具有多个字段的数据执行。在运算符的节点中，一个字段识别运算符，其余字段包含指向操作数节点的指针。运算符称为节点的标签。以下函数用于为具有二元运算符的表达式创建语法树的节点。每个函数都返回指向最近生成的节点的指针。

mknode (op, left, right) - 它生成一个带有标签 op 的运算符节点，以及两个包含指向左节点和右节点的指针的字段。
mkleaf (id, entry) - 它生成一个带有标签 id 的标识符节点，以及包含 entry 的字段，entry 是指向标识符符号表条目的指针。
mkleaf (num, val) - 它生成一个带有标签 num 的数字节点，以及包含 val 的字段，val 是数字的值。例如，为表达式 a − 4 + c 构建语法树。在这个序列中，p₁、p₂、……p₅分别是指向标识符 'a' 和 'c' 的符号表条目的指针。

p₁− mkleaf (id, entry a);
p₂− mkleaf (num, 4);
p₃− mknode ( ′−′, p₁, p₂)
p₄− mkleaf(id, entry c)
p₅− mknode(′+′, p₃, p₄);

树以自底向上的方式生成。函数调用 mkleaf (id, entry a) 和 mkleaf (num 4) 为 a 和 4 构造叶子节点。指向这些节点的指针使用 p₁ 和 p₂ 存储。然后，调用 mknodes (′−′, p₁, p₂ ) 创建内部节点，其中 a 和 4 的叶子作为子节点。语法树将是

语法树的语法制导翻译

产生式	语义动作
E → E⁽¹⁾ + E⁽²⁾	{E. VAL = Node (+, E⁽¹⁾. VAL, E⁽²⁾. VAL)}
E → E⁽¹⁾ ∗ E⁽²⁾	{E. VAL = Node (∗, E⁽¹⁾. VAL, E⁽²⁾. VAL)})
E → (E⁽¹⁾)	{E. VAL = E⁽¹⁾. VAL}
E → E⁽¹⁾	{E. VAL = UNARY (−, E⁽¹⁾. VAL}
E → id	{E. VAL = Leaf (id)}