3

我可以在 Wikipedia 上阅读Production的正式定义，但是当您开始阅读该文章时，它会假设先验知识。

维基百科是这样定义的：

计算机科学中的产生式或产生式规则是一种重写规则，它指定可以递归执行以生成新符号序列的符号替换。

这假设我知道并理解什么是重写规则。我没有，如果我点击链接，我会进入另一个相当技术性的解释。

有人可以用简单的英语向我解释一下Production实际上是什么吗？

注意：我已经做了很多尝试来理解这一点，但我认为我没有成功。据我所知，它会根据语法规则重写给定的字符串。不确定我是否正确。

4

2 回答 2

4

为了解释什么是作品，我想先介绍一下背景。

龙书指出上下文无关语法有 4 个组成部分：

  • 一组终端符号（令牌）
  • 一组非终结符号（句法变量）
  • 一组形式的产生：非术语->终端和非终端的序列
  • 指定为起始符号的非终结符号

也有人说，解析是获取一串终结符（源代码）并弄清楚从语法的开始符号导出这串终结符所需的步骤的问题。

既然已经说过，生产本质上是一个可能的（中间）步骤。我说可能是因为某些符号可以派生为不同的序列。

例如，让我们编写一个简单的语法来表示以 a 结尾的任意长的 a 序列。该语法的 4 个组成部分是：

  • 终端：a、b
  • 非终端：S，X
  • 规则：S --> X, X --> aX, X --> ab
  • 开始符号：S

从我上面给出的描述中，“aaaab”应该是从这个语法推导出来的。让我们看看这是否成立。我们从开始符号开始，然后应用产生式，直到 a）我们得到最终序列，b）我们用尽所有可能性但没有成功（意味着序列不是“语法正确”）。

S
X (after applying S --> X)
aX (after applying X --> aX)
aaX (after applying X --> aX)
aaaX (after applying X --> aX)
aaaab (after applying X --> ab)

我们完成了，我们得到了原始序列。如您所见，我们通过应用规则（其中一个我们递归应用）重新编写了非终结符号，这些规则在每一步都将序列转换为新的符号序列，我们这样做直到得到最终序列。

于 2013-08-20T09:27:22.857 回答
1

重写规则是一种将公式的子项替换为其他项的方法。在最基本的形式中，它们由一组对象以及如何转换这些对象的关系组成。

重写规则的示例可能如下所示：

A → B

现在至于这实际上是做什么的！你的笔记是对的，例如一个事物列表（和 2 个重写规则）：

X, Y, Z
X → Y
Y → Z

这将导致：

Z, Z, Z

生产规则是重写规则，因为它是一种替换公式子项的方法（在您的情况下可能是字符串）。生产规则可能如下所示：

X, Y, Z
X → aX

通过以这种方式使用规则，可以应用递归（创建新序列），因为它将不断替换自身：

aX, Y, Z
aaX, Y, Z
aaaX, Y, Z

至于您要问的问题，您可以说：“生产规则是使用递归创建新序列的公式的替换规则”。

于 2013-08-20T09:27:11.623 回答