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

解析树

解析树是一种层次结构,它定义了语法的推导以产生输入字符串。在解析中,字符串是使用开始符号派生的。解析树的根是那个开始符号。它是符号的图形描述,可以是终端或非终端。解析树遵循运算符的优先级。首先遍历最深的子树。因此,父节点中的运算符优先级低于子树中的运算符。

CFG G = (V, Σ, P, S) 的解析树是满足以下条件的树 -

  • Root 具有标签 S,其中 S 是开始符号。

  • 解析树的每个顶点都有一个标签,该标签可以是变量 (V)、终端 (Σ) 或 ε。

  • 如果 A → C 1 , C 2 ... ... 。C n是一个产生式,然后是 C 1,C 2 ……。C n是标记为 A 的节点的子节点。

  • 叶节点是终端节点(Σ),内部节点是变量(V)。

  • 内部顶点的标签始终是一个变量。

  • 如果一个顶点 A 有 k 个标签为 A 1 , A 2 ... ... 的孩子。A k,然后 A → A 1,A 2 ……。A k将是上下文无关文法 G 中的产生式。

语法树

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

表达式的语法树如下 -

示例- 构造

  • 解析树

  • 语法树

  • 使用您知道的任何语法对输入字符串 1 * 2 + 3 的完整解析树进行注释。

解决方案

让我们看看 Parse tree 和 Syntax Tree 之间的比较。

解析树语法树
It can contain operators & operands at any

node of the tree, i.e., either interior node or

leaf node.

它包含叶节点处的操作数和操作符作为树的内部节点。
It contains duplicate or redundant

information.

它不包括任何冗余数据。
Parse Tree can be changed to Syntax Tree by the elimination of redundancy, i.e., by compaction.语法树不能更改为解析树。
Example− 1 *2 + 3.示例- 1 * 2 + 3。

以上是 解析树和语法树有什么区别? 的全部内容, 来源链接: utcz.com/z/363435.html

回到顶部