自动机推导树

推导树是用于给定CFG的给定生产规则推导的图形表示。这是显示如何从一组给定的生产规则中获取某些字符串的推导的简单方法。推导树也称为解析树。
解析树遵循运算符的优先级。最深的子树首先遍历。因此,父节点中的运算符优先于子树中的运算符。
解析树包含以下属性:

  1. 根节点始终是指示开始符号的节点。
  2. 从左到右读取推导。
  3. 叶节点始终是终端节点。
  4. 内部节点始终是非终端节点。
范例1:
生产规则:
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”的推导树如下:
自动机推导树

文章图片

    推荐阅读