programming-languages - 乔姆斯基层次结构和编程语言

Question

我正在尝试学习与编程语言相关的 Chomsky Hierarchy 的某些方面，但我仍然需要阅读 Dragon Book。

我读过大多数编程语言都可以解析为上下文无关语法(CFG)。就计算能力而言，它等于下推非确定自动机之一。我对吗？

如果是真的，那么一个 CFG 怎么可能持有图灵完备的无限制语法(UG)？我之所以问是因为，即使 CFG 描述了编程语言，它们实际上也用于描述图灵机，因此通过 UG。

我认为这是因为至少有两个不同级别的计算，第一个是 CFG 的解析，侧重于与语言的结构(表示？)相关的语法，而另一个侧重于语义(意义，解释数据本身？)与图灵完备的编程语言的能力有关。同样，这些假设是否正确？

Answer 1

I've read that most programming languages can be parsed as a context free grammar (CFG). In term of computational power, it equals the one of a pushdown non deterministic automaton. Am I right?

技术上是的。有用的是，不。

至少有两种有用的方法来思考这些问题:

如果您正在考虑一组字符串，那么您就有了一种语言。

如果您正在考虑一种算法来确定一个字符串是否属于某种语言，那么您就有了一个决策问题。

困难在于，尽管大多数编程语言都有一个可以用上下文无关文法轻松描述的底层结构(Tcl 是一个有趣的异常(exception))， 许多由上下文无关语法描述的句子实际上并不是“在语言中”，其中“语言”是指“相关语言的有效程序”。这些额外的句子通常被某种形式的静态语义排除。例如，以下话语是 C 程序的上下文无关文法中的一个句子，但它本身不在有效的 C 程序集中:

int f(void) { return n + 1; }

这里的问题是 n不在范围内。 C 需要“使用前声明”，并且该属性不能使用上下文无关文法来表达。

一个真正的编程语言的典型决策过程是编译器或解释器前端的一部分，它至少有两个部分:一个是解析器，在决策能力上等同于下推自动机；但是第二个进行了额外的检查，排除了许多无效的话语。如果这些检查需要任何类型的使用前定义属性，则它们不能通过下推自动机或上下文无关文法来完成。

If it's true, then how could a CFG hold an unrestricted grammar (UG), which is turing complete?

CFG 不“持有”任何东西——它只是描述一种语言。

... even if programming languages are described by CFGs, they are actually used to describe turing machines, and so via an UG.

您在这里跳过了一些重要的间接级别。

I think that's because of at least two different levels of computing, the first, which is the parsing of a CFG focuses on the syntax related to the structure ( representation ? ) of the language, while the other focuses on the semantic ( sense, interpretation of the data itself ? ) related to the capabilities of the programming language which is turing complete. Again, are these assumptions right?

他们对我来说似乎有点困惑，但你在正确的轨道上。一个关键问题是“语言和编程语言之间有什么区别？”答案是编程语言具有计算解释。计算解释有很多种，但并不是所有的都是图灵完备的。
但神奇之处在于解释，而不是语法，因此乔姆斯基层次结构在这里并不是很重要。

为了证明我的观点，举一个极端的例子:正则语言 [1-9][0-9]*在以下解释下是图灵完备的:

SK-combinator 语言是图灵完备的。

SK程序只有可数的多。

它们可以很容易地被唯一地和确定地枚举。

因此，我们可以将每个正整数与一个 SK 程序相关联。

如果我们以标准的方式将数字序列解释为正整数，我们同样可以将相同的数字序列解释为 SK 程序，此外，任何 SK 程序都可以使用有限的数字序列来表示。

因此整数文字的语言是图灵完备的。

如果你的头现在不疼，它应该。