推导树

推导树是给定上下文无关文法(CFG)的推导规则的图形表示。它是一种简单的方式，用于展示如何从给定的一组推导规则中获得某个字符串。推导树也被称为解析树。

解析树遵循运算符的优先级。首先遍历最深的子树。因此，父节点中的运算符的优先级低于子树中的运算符。

解析树包含以下属性

1. 根节点始终是一个指示开始符号的节点。
2. 推导是从左到右读取的。
3. 叶节点始终是终结符节点。
4. 内部节点始终是非终结符节点。

示例 1

推导规则

输入

步骤 1

步骤 2

步骤 2

步骤 4

步骤 5

注意：我们可以逐步或直接一步绘制推导树。

示例 2

从给定的 CFG 中为字符串 "bab" 绘制推导树

解决方案

现在，字符串 "bbabb" 的推导树如下所示

上图是为推导字符串 bbabb 绘制的推导树。通过简单地读取叶节点，我们可以获得所需的字符串。同一棵树也可以表示为，

示例 3

为字符串 aabbabba 构建推导树，用于给定的 CFG，

解决方案

要绘制树，我们首先尝试获得字符串 aabbabba 的推导

现在，推导树如下所示

示例 4

使用以下语法显示字符串 "aabbbb" 的推导树。

解决方案

要绘制树，我们首先尝试获得字符串 aabbbb 的推导

现在，字符串 "aabbbb" 的推导树如下所示