0

我目前正在研究编译器，主题是“乔姆斯基层次结构和 4 种语言”。但它让我不知道这一切的实际目的是什么？

如果我能看到 4 种语法的真实示例，那就太好了：Unrestricted、CSG、CFG、Regular Grammer。

我在网上发现，乔姆斯基层次结构和 4 种语法被用来评估认知科学中的建议，但这超出了我的想象。如果有人能帮我分解一下，那就太好了，非常感谢！

4

1 回答 1

1

没有实用价值。这就是重点。

让我试着把它分解一下。记住乔姆斯基是一位语言学家——研究人类语言的人——并且他在 1950 年代后期写作，当时计算理论还没有今天这样发达，这一点很有用。（说得委婉些。）他的目标是找到一个数学模型，可以为人类生成和理解句子的机制提供一些见解，他以一个特别简单的句子生成模型为起点。

在这个模型中，语法是一个函数F，它将元素从某个字母表中的任意符号序列转换为同一字母表中的另一个符号序列。F由一组有限的对（称为产品）定义α → β。然后我们说 F(ω) = F(ζ) 如果 的定义F包含一些对α → β，它α是 的 子串是用替换 的单个实例ω的结果。ζαωβ

这本身并不是很有趣。我们通过从一些指定的起始序列开始将其变成完整的语言，通常表示为单个符号S，并根据需要重复应用F多次。（在所有有趣的语法中，如此构造的集合是无限的，因此实际上无法构造它。但我们可以想象从起点开始，直到找到我们想要生成的句子。）

这个模型的问题在于它可以用来描述任意的图灵机。或者，如果您愿意，可以使用任意计算机程序，尽管使用图灵机更容易看出等价性。换句话说，至少在理论上可以构造一个有限文法，该文法将识别由图灵机（即用某种编程语言编写的程序）的描述组成的字符串，然后是输入和输出，前提是图灵机应用于输入将产生输出。换句话说，存在（在数学意义上）这种形式的语法，它在计算上等同于通用计算机。

不幸的是，如果我们的目标是理解句子，这实际上并不是很有用，因为实际上没有用于向后运行计算机的算法。作为一般解决方案，我们能做的最好的事情是枚举所有可能的输入并在每个输入上运行程序，直到找到我们希望的输出。这实际上不起作用，因为程序产生输出所花费的时间没有限制，甚至无法知道程序是否最终会结束。（这被称为“停止问题”。）所以我们可能会卡在一些可能的输入上，并且我们永远不会知道其他一些输入是否会产生所需的输出。

结果，我们无法判断所提供的输入是否“符合语法”，即它是否符合所提供的语法。这不仅仅是我们为模拟图灵机而构建的特定语法的情况。这意味着我们没有信心从任意语法中识别句子，即使我们偶然发现了答案，我们也无法限制到达那里可能需要多长时间。

显然，这不是人类相互理解的方式。因此，如果要服务于实际目的，我们必须以某种方式限制可能的语法，使它们在计算上可行。

另一方面，人们对有限状态机了解很多。有限状态机是没有磁带的图灵机；也就是说，它只是状态的有限集合。在每个状态中，机器读取一个输入符号并使用它来决定下一个状态是什么。事实证明，有限状态机可以使用仅限于非常简单的产生式的语法（如上）来建模，每个产生式的形式要么是 要么A → a B，A → a其中a是来自“终端字母表”的符号（即一个词) 和A和B是单一的语法符号。这些语法被称为“正则语法”，它们在计算上等同于数学家所说的“正则表达式”（这是“正则表达式”库识别的一小部分，但这是另一个讨论）。

正则文法很容易解析。所需要的只是通过状态机进行跟踪，因此无需在与输入长度成正比的时间上回溯即可完成。但是常规语法太弱了，无法表示人类语言，甚至大多数计算机语言。举个简单的例子，带括号的代数表达式不能用正则文法（或有限状态机）识别，因为没有办法计算括号深度；有限状态机根本没有记忆（除了知道它处于哪个状态，并且只有有限数量的状态）。

因此，不受限制的语法太强大而无法解析，而常规语法太弱而无法使用。（对复杂的解析问题有用，即正则表达式有一定的应用，但解析完整的计算机程序不是其中之一。）

然后，下一步是尝试找到对语法的限制，该限制仍然足够强大以表示人类语言，而不会强大到无法进行解析。

最后，这就是乔姆斯基等级制度的起源。在上述两个极端（类型 0 和类型 3 文法）之间，乔姆斯基提出了两种可能的中间限制——类型 1 和类型 2 文法——并证明了它们各自的许多重要性质。

虽然这项工作被证明是形式语言理论发展的基础，但不能说它真的回答了乔姆斯基开始提出的问题。类型 2 文法——上下文无关文法——确实在计算上易于处理；它们可以在多项式时间内用简单的算法进行解析，并且可以表示大量有用的语言。但它们仍然太弱，无法代表人类语言。特别是，上下文无关文法不能表示像“所有字符串都包含相同子字符串的两个实例”这样简单的语言。第一类文法——上下文相关文法-- 可能可以表示任何有用的语言，并且不像不受限制的语法那样不守规矩，但它们仍然太强大而无法解析。（由于上下文相关语法中的推导步骤永远不会变短，因此可以按长度顺序从起点枚举所有可能的推导，这意味着您可以确定句子是否由语法生成，而不会遇到停止问题。但这已经很好了；该过程需要指数级的时间，并且对于非平凡的输入是不可行的。）

自从乔姆斯基发表他的开创性论文以来的 6 年里，已经做了很多工作来试图在类型 1 和类型 2 语法之间找到有用的中间限制。并且已经对用于解析上下文无关语言的算法进行了大量有用的研究，这在构建编译器方面具有巨大的实用性。所有这些都建立在乔姆斯基和其他计算理论家所做的重要工作之上——马尔可夫、图灵、丘奇和克莱恩，仅举几个值得研究的例子。但乔姆斯基最初的项目仍未解决。

因此，如果您的目标是为编程语言构建一个简单的解析器，那么乔姆斯基层次结构可能只是一个有趣的脚注。但如果你对形式语言理论的学术研究感兴趣，还有很多有趣的未解决问题需要研究。

于 2022-02-20T17:50:38.697 回答