parsing - 什么是简单英语的 "Production"？

Question

我可以在维基百科上阅读 Production 的正式定义，但是当您开始阅读那篇文章时，它会对先验知识做出假设。

维基百科是这样定义的:

A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences.

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

有人可以用简单的英语向我解释什么是生产吗？

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

Answer 1

为了解释什么是制作，我想先介绍一些上下文。

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

一组终端符号( token )

一组非终结符(语法变量)

一组形式的产生式:非术​​语 --> 终结符和非终结符序列

指定为起始符号的非终结符

也有人说，解析是取一串终结符(源代码)并找出从语法的起始符号推导出这串终结符所需的步骤的问题。

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

例如，让我们用一个简单的文法来表示一个以 b 结尾的任意长序列。该语法的 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)

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