语法树和解析树有什么区别？

解析树

解析树是一种分层结构，它定义了语法推导产生输入字符串的过程。在解析过程中，字符串是使用开始符号推导出来的。解析树的根节点就是该开始符号。它是符号的图形描述，这些符号可以是终结符或非终结符。解析树遵循运算符的优先级。最深的子树首先被遍历。因此，父节点中的运算符优先级低于子树中的运算符。

对于一个上下文无关文法 G = (V, Σ, P, S)，其解析树满足以下条件：

根节点的标签为 S，其中 S 是开始符号。
解析树的每个顶点都有一个标签，该标签可以是变量 (V)、终结符 (Σ) 或 ε。
如果 A → C₁, C₂ … … . C_n 是一个产生式，那么 C₁, C₂ … … . C_n 是标记为 A 的节点的子节点。
叶子节点是终结符 (Σ)，内部节点是变量 (V)。
内部顶点的标签始终是变量。
如果一个顶点 A 有 k 个子节点，其标签为 A₁, A₂ … … . A_k，那么 A → A₁, A₂ … … . A_k 将是上下文无关文法 G 中的一个产生式。

语法树

语法树是一棵树，它显示程序的语法结构，同时忽略解析树中存在的无关分析。因此，语法树只不过是解析树的简化形式。解析树中的运算符和关键字节点被移到其父节点，并且一组单独的产生式被单个链接替换。例如，对于给定字符串 id + id * id 的解析树。

该表达式的语法树如下：

示例 - 构造

解决方案

让我们看看解析树和语法树之间的比较。

解析树	语法树
它可以在树的任何节点（即内部节点或叶子节点）包含运算符和操作数。	它在叶子节点包含操作数，在树的内部节点包含运算符。
它包含重复或冗余信息。	它不包含任何冗余数据。
通过消除冗余（即通过压缩）可以将解析树更改为语法树。	语法树不能更改为解析树。
示例 - 1 *2 + 3。	示例 - 1 *2 + 3。

Ginni

更新于： 2021年11月5日

23K+ 浏览量

通过完成课程获得认证