推导

引言

规则 x -> y 被称为产生式规则，应用产生式规则称为推导。

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

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

示例 1

让我们考虑以下语法。

A = {a, b, c}

然后 A* 的语法可以用以下 4 个产生式来描述

产生式规则的集合是

S -> aS

S -> bS

S -> cS

S -> γ

解决方案

S => aS

S => aaS

S => aacS

S => aacbS

S => aacb

字符串的所需推导是 aacb。

示例 2

让我们考虑以下语法。

G = ({ S } , { a, b }, S, P }

然后 A* 的语法可以用以下 2 个产生式来描述

产生式规则的集合是

S -> aSb

S -> γ

解决方案

S => aSb

S => aaSbb

S => aabb

S => aabb

字符串 aabb 是由 G 生成的语言中的一个句子，而 aabb 是一个句子。

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

最左推导

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

示例

推导规则

输入

a - b + c

最左推导是

说明

• 最初，我们从产生式规则 S = S + S 开始。
• 接下来，我们将 S 替换为产生式规则 S -> S - S 以匹配输入字符串中的非终结符 a。
• 接下来，我们将 S 替换为产生式规则 S -> a 以匹配输入字符串中的第一个字符 "a"。
• 接下来，我们将 S 替换为产生式规则 S -> b 以匹配输入字符串中的第二个字符 "b"。
• 接下来，我们将 S 替换为产生式规则 S -> c 以匹配输入字符串中的第二个字符 "c"。

最右推导

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

示例

输入

a - b + c

最右推导是

说明

• 最初，我们从产生式规则 S = S - S 开始。
• 接下来，我们将 S 替换为产生式规则 S -> S + S 以匹配输入字符串中的非终结符 a。
• 接下来，我们将 S 替换为产生式规则 S -> c 以匹配输入字符串中的第一个字符 "c"。
• 接下来，我们将 S 替换为产生式规则 S -> b 以匹配输入字符串中的第二个字符 "b"。
• 接下来，我们将 S 替换为产生式规则 S -> a 以匹配输入字符串中的第二个字符 "a"。