推导树是用于给定CFG的给定生产规则推导的图形表示。这是显示如何从一组给定的生产规则中获取某些字符串的推导的简单方法。推导树也称为解析树。
解析树遵循运算符的优先级。最深的子树首先遍历。因此,父节点中的运算符优先于子树中的运算符。
解析树包含以下属性:
- 根节点始终是指示开始符号的节点。
- 从左到右读取推导。
- 叶节点始终是终端节点。
- 内部节点始终是非终端节点。
生产规则:
E = E + E
E = E * E
E = a | b | c
输入值
a * b + c
步骤1:
文章图片
第2步:
文章图片
第2步:
文章图片
步骤4:
文章图片
步骤5:
文章图片
注意:我们可以逐步或直接一步一步绘制推导树。范例2:
从以下给出的CFG中为字符串“ bab”绘制一个推导树
S → bSb | a | b
【自动机推导树】解:
现在,字符串“ bbabb”的推导树如下:
文章图片
上面的树是为推导字符串bbabb而绘制的推导树。通过简单地读取叶节点,我们可以获得所需的字符串。同一棵树也可以表示为
文章图片
范例3:
为给定的CFG的字符串aabbabba构造一个推导树,
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
解:
要绘制一棵树,我们将首先尝试获取字符串aabbabba的推导
文章图片
现在,推导树如下:
文章图片
范例4:
用以下语法显示字符串“ aabbbb”的推导树。
S → AB | ε
A → aB
B → Sb
解:
要绘制一棵树,我们首先将尝试获取字符串aabbbb的推导
文章图片
现在,字符串“ aabbbb”的推导树如下:
文章图片
推荐阅读
- 自动机语法中的歧义
- 自动机推导
- 自动机之Mealy机
- 自动机之Moore机
- 从Mealy机到Moore机的转换
- 从Moore机到Mealy机的转换
- 自动机上下文无关语法(CFG)
- Arden定理
- RE到FA的自动机转换