本文概述
- 1.最左推导
- 2.最右推导
- 推导示例
- 我们必须确定要替换的非终端。
- 我们必须确定替换非终端设备的生产规则。
1.最左推导在最左侧的推导中,将扫描输入,并用生产规则从左到右替换输入。因此,在最左侧的推导中,我们从左到右读取输入字符串。
例:
生产规则:
E = E + E
E = E - E
E = a | b
输入值
a - b + a
最左边的推导是:
E = E + E
E = E - E + E
E = a - E + E
E = a - b + E
E = a - b + a
2.最右推导在最右边的推导中,将扫描输入,并用从右到左的生产规则替换输入。因此,在最右推导中,我们从右到左读取输入字符串。
例
生产规则:
E = E + E
E = E - E
E = a | b
输入值
a - b + a
最右边的推导是:
E = E - E
E = E - E + E
E = E - E + a
E = E - b + a
E = a - b + a
当我们使用最左边的导数或最右边的导数时,我们可能会得到相同的字符串。这种推导类型不影响字符串的获取。
推导示例范例1:
使用给出的CFG推导字符串“ abb”表示最左派和最右派,
S → AB | ε
A → aB
B → Sb
解:
最左边的导数:
文章图片
最右边的推导:
文章图片
范例2:
使用由给出的CFG推导字符串“ aabbabba”,以表示最左派和最右派,
S → aB | bA
S → a | aS | bAA
S → b | aS | aBB
解:
最左边的导数:
S
aBS → aB
aaBBB → aBB
aabBB → b
aabbSB → bS
aabbaBS → aB
aabbabSB → bS
aabbabbAS → bA
aabbabbaA → a
最右边的推导:
S
aBS → aB
aaBBB → aBB
aaBbSB → bS
aaBbbAS → bA
aaBbbaA → a
aabSbbaB → bS
aabbAbbaS → bA
aabbabbaA → a
范例3:
使用由给出的CFG推导字符串“ 00101”,用于最左派和最右派,
S → A1B
A → 0A | ε
B → 0B | 1B | ε
解:
最左边的导数:
S
A1B
0A1B
00A1B
001B
0010B
00101B
00101
【自动机推导】最右边的推导:
S
A1B
A10B
A101B
A101
0A101
00A101
00101
推荐阅读
- 自动机推导树
- 自动机之Mealy机
- 自动机之Moore机
- 从Mealy机到Moore机的转换
- 从Moore机到Mealy机的转换
- 自动机上下文无关语法(CFG)
- Arden定理
- RE到FA的自动机转换
- 自动机正则表达式的例子