正确或错误:上下文无关语法识别的任何单词也可以通过最右边的派生词识别?

我认为这里的困惑围绕着语法“识别句子”意味着什么的问题。

事实上,上下文无关语法是对 生成 而不是识别句子。也就是说,语法中的每一个规则都定义了一个派生步骤,它可以通过用右手边替换左手边的任何一个实例来应用于句子形式。如果我们从语法的起始符号开始形成这个运算的闭包,那么我们就有了一组句子形式;语法的语言是这个集合与语法的结束字母的克莱恩闭包的交集。

(我们所说的“句子形式”指的是语法符号字母表中克莱恩闭包的一个元素,而“句子”则仅限于终端字母表中克莱恩闭包的元素。我相信,这种区别来自于克努斯,但目前我仍在关注诺姆·乔姆斯基的开创性论文 语法的某些形式性质 ,写于1959年。)

碰巧,我们可以递归地枚举语言(作为一个集合)。因此,我们可以通过开始枚举并等待句子出现来“识别”一个句子。这将适用于任何生成语法,而不仅仅是上下文无关语法,但与乔姆斯基的无限制(0型)语法,它有一个问题,我们永远不知道什么时候放弃等待。(也就是说,它和一般的图灵机有着相同的停顿问题。)但是使用受限语法,我们可以生成一个枚举,在这个枚举中,较短的句子在较长的句子之前生成,因此,在我们枚举了目标句子长度的所有句子之后,我们肯定可以停止查看。(这在实践中仍然不太令人满意,但在理论上是很好的。这是乔姆斯基论文中的定理3。)这是递归集和递归可枚举集之间的根本区别。

在实践中,我们希望创建一个基于语法的解析自动机,更重要的是,我们希望自动机能够保证在明确定义的时间和空间限制内工作。对于类型2和类型3语法,这是绝对可能的(对于类型3,线性时间和常量空间;对于类型2语法,多项式时间和空间的指数为<3;对于类型2语法,线性时间和空间的指数为<3;对于类型2语法的限制子集,称为确定性语法)

但是让我们回到语法识别(或生成)一个句子意味着什么的问题。由于语言是派生步骤运算符的闭包,因此语言中的每个句子都是派生步骤的有限序列的结果,从起始符号开始。一系列派生步骤被称为派生,如果一个句子是用语法派生的,那么这个语法就被称为派生那个句子。这和我们将要讨论的语法识别句子的概念一样接近。

理想情况下,我们希望减少由大量可能的句子派生产生的噪音。除了线性语法,总是会有很多可能的派生,因为每当句子形式中有两个或更多的非终结符时,就有两个或更多可能的派生步骤可以应用,而在上下文无关(类型2)语法中,“工作”可以以任何顺序应用。这是一个简单的方式来思考“上下文无关”在这种情况下意味着什么。(我鼓励所有读者尽量使前面的陈述更加准确。我只是想提供一些直觉,而不是数学证明。)

在乔姆斯基的论文中,他展示了如何将派生词视为一棵树的遍历,而这棵树实际上表达了派生句的句法结构。因为我们真正感兴趣的是树而不是派生序列,所以我们想合并所有派生序列,它们是同一棵树的遍历。如果一个给定的句子只有一个这样的树,那么我们可以说语法是明确的。

不幸的是,正如乔姆斯基也指出的那样,类型1语法仍然太强大,无法实现这一点,而类型2语法还不足以表示乔姆斯基感兴趣的语言(即人类语言)。尽管他对未能定义一个适用于人类语言的语法范畴感到沮丧,但他的工作在现代形式语言理论的发展中具有深远的意义。

现在,让我们把自己限制在类型2语法中,其中派生步骤的应用顺序是不相关的。在这种情况下,我们可以使用一个非常简单的算法将给定的解析树与一个派生序列关联起来:我们只允许派生序列对应于从右向左遍历的深度优先的前序。(也就是说,我们从右到左访问孩子们。)这与规则相对应,在派生序列中,每个派生步骤都适用于句子形式中最右边的非终结句。(从左到右遍历似乎更为自然,这将始终对应于扩展最左侧的非端点。从从解析树生成唯一派生的角度来看,这也是可行的。但结果却不那么方便。)

这些见解来自另一篇开创性的论文,Donald Knuth的 论语言从左到右的翻译 (1965).

因此,我们现在应该对以下声明感到满意:

• 这个句子是用语法G的语言写成的。
• G导出Î。
• G只使用最右边的派生步骤进行派生。

都说同样的话。但同时,我们也为几十年的句法研究奠定了基础。

很容易找到我在这里引用的这两篇论文,这是值得的,因为它们都很容易阅读,而且它们包含了很多真正理解LR解析所必需的见解。