什么是语法树？

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

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

构造语法树的规则

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

• mknode (op, left, right) - 它生成一个带有标签 op 和两个字段的运算符节点，包括指向左右的指针。

• mkleaf (id, entry) - 它生成一个带有标签 id 的标识符节点和包含条目的字段，一个指向标识符符号表条目的指针。

• mkleaf (num, val) - 它生成一个带有标签 num 的数字节点和一个包含数字值 val 的字段。例如，为表达式 a − 4 + c 构建语法树。在这个序列中，p ₁，p ₂，...。. p ₅是分别指向标识符“a”和“c”的符号表条目的指针。

p1− mkleaf (id, entry a);
p2− mkleaf (num, 4);
p3− mknode ( ′−′, p1, p2)
p4− mkleaf(id, entry c)
p5− mknode(′+′, p3, p4);

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

语法树的语法定向翻译

节点(+,