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 回答