推导

推导是一系列产生式规则。它用于通过这些产生式规则获得输入字符串。在解析过程中，我们必须做出两个决定。如下所示：

• 我们必须决定要替换的非终结符。
• 我们必须决定使用哪个产生式规则来替换非终结符。

我们有两个选项来决定用产生式规则替换哪个非终结符。

1. 最左推导

在最左推导中，从左到右扫描输入并用产生式规则替换。因此，在最左推导中，我们从左到右读取输入字符串。

示例

推导规则

输入

最左推导是

2. 最右推导

在最右推导中，从右到左扫描输入并用产生式规则替换。因此，在最右推导中，我们从右到左读取输入字符串。

示例

推导规则

输入

最右推导是

当我们使用最左推导或最右推导时，我们可能会得到相同的字符串。这种类型的推导不会影响字符串的获取。

推导示例

示例 1

使用给定的 CFG，为最左推导和最右推导推导出字符串 "abb"。

解决方案

最左推导

最右推导

示例 2

使用给定的 CFG，为最左推导和最右推导推导出字符串 "aabbabba"。

解决方案

最左推导

最右推导

示例 3

使用给定的 CFG，为最左推导和最右推导推导出字符串 "00101"。

解决方案

最左推导

最右推导