推导规则

推导是一系列生产规则。它用于通过这些生产规则获取输入字符串。在解析期间, 我们必须做出两个决定。这些如下:

  • 我们必须确定要替换的非终端。
  • 我们必须确定替换非终端设备的生产规则。
我们有两个选择来决定用生产规则替换哪个非终端。
最左边的导数
在最左侧的派生中, 将扫描输入, 并用生产规则从左到右替换输入。因此, 在大多数派生语言中, 我们从左到右读取输入字符串。
例:
生产规则:
S = S + SS = S - SS = a | b |c

输入:
a - b + c

最左边的推导是:
S = S + SS = S - S + SS = a - S + SS = a - b + SS = a - b + c

最右派生在最右边的派生中, 将扫描输入并从右到左用生产规则替换输入。因此, 在大多数派生词中, 我们从右到左读取输入字符串。
例:
S = S + SS = S - SS = a | b |c

输入:
a - b + c

【推导规则】最右边的推导是:
S = S - SS = S - S + SS = S - S + cS = S - b + cS = a - b + c

    推荐阅读