锐客网

  1. 首页 > 睿知 > it技术 > >

自动机推导

自动机教程自动机推导

本文概述

  • 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机

    下一篇：自动机推导树