1

我一直在阅读：“创建上下文无关语法的提示”帖子以用于学习目的，我几乎理解了这个概念，但我不太明白以下内容。

如果我们有：

L = {a m b n | m >= n}。

我明白这一点：

S --> B
B --> aBb
A  --> aA

但我不明白的是添加到这些特定值末尾的概念，例如：

S --> B | ^
B --> aBb | A
A  --> aA | a

为什么我们在这些行的末尾添加^ (null)、A和a ？他们做什么，我们为什么需要他们？

非常感谢所有帮助。

4

2 回答 2

2

您需要它们能够构造语言中的字符串L。

B --> aBb | A意味着如果你有一个非终结符B，它可以被替换为aBb 或 A。（大写字母代表非终结符，小写字母代表终结符）。

我们来看看语法：

S --> B | ^
B --> aBb | A
A  --> aA | a

为什么我们有一个| ^？您需要它能够生成空字符串。空字符串显然是语言的一部分，L因为它包含相等数量的as 和bs。

为什么我们有| A？为了能够使用规则A。现在您可以替换B为，A 以便您可以插入aA或a。您需要此规则才能生成as 多于bs 的字符串。

为什么我们有| a？能够在不A添加需要替换的新非终结符的情况下替换为。a

当我查看此语法时，我会说您需要更改A --> aA | a为A --> aA | a | ^能够生成具有等量as 和bs 的字符串。（因此您可以A用空字符串（或 null）替换，而不必添加额外的a）

假设您要生成字符串aaabb：

S       //You start with S
B       //Rule: S --> B
aBb     //Rule: B --> aBb
aaBbb   //Rule: B --> aBb
aaAbb   //Rule: B --> A
aaabb   //Rule: A --> a
于 2013-04-13T02:46:29.997 回答
0

额外的 ^,A 和 a 的需要是为了完成语法集。

因此A --> aA负责 [aa, aaa, aaaa, ...]

一个--> aA | a照顾 [a, aa, aaa, aaaa, ...]

B --> aBb负责 [ab, aabb, aaabbb, ...]

所以，B --> aBb | A 应该照顾 [a, ab, aa, aab, aaa, aaab, aabb, ...]

唯一缺少的是^

所以现在用S --> B |完成语法。^ [^, a, aa, ab, aaa, aab, aaaa, aaab, aabb, ...]

如您所见，不可能从前半部分生成后半部分，但它也是语法的一个子集。所以，为了完成语法，第二部分也是至关重要的。查看维基百科文章以获得更清晰的示例。

http://en.wikipedia.org/wiki/Context-free_grammar

于 2013-04-13T02:23:23.030 回答