乔姆斯基的层次结构和编程语言

Question

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

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

如果这是真的,那么CFG怎么能保持一个不受限制的语法(UG),这是完整的？我问,因为即使编程语言由CFG描述,它们实际上也用于描述图灵机,所以通过UG.

我认为这是因为至少有两个不同的计算级别,第一个,即CFG的解析侧重于与语言结构(表示？)相关的语法,而另一个侧重于语义(意义,解释)数据本身？)与编程语言的功能有关,这是完整的.再次,这些假设是对的吗？

Answer 1

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

技术上是的.有用,没有.

至少有两种有用的方法可以考虑这些问题:

• 如果您正在考虑一组字符串,那么您就拥有了一种语言.
• 如果您正在考虑使用算法来确定字符串是否在某种语言中,那么您就会遇到决策问题.

困难在于,虽然大多数编程语言都有一个可以通过无上下文语法轻松描述的底层结构(Tcl是一个有趣的例外), 但是由无上下文语法描述的许多句子实际上并不是"在语言中".其中"在语言中"是指"有问题的语言中的有效程序".这些额外的句子通常由某种形式的静态语义排除.例如,以下话语是C程序的无上下文语法中的一个句子,但它本身并不属于有效的C程序集:

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

这里的问题n是不在范围内.C需要"使用前声明",并且该属性不能使用无上下文语法表达.

实际编程语言的典型决策过程是编译器或解释器前端的一部分,它至少有两个部分:一个是解析器,它与下推自动机的决策权相当; 但是第二个做了额外的检查,排除了许多话语无效.如果这些检查需要任何类型的使用前定义属性,则无法通过下推自动机或无上下文语法来完成它们.

如果这是真的,那么CFG怎么能保持一个不受限制的语法(UG),这是完整的？

CFG不会"持有"任何东西 - 它只是描述一种语言.

...即使编程语言由CFG描述,它们实际上也用于描述图灵机,因此通过UG.

你在这里跳过了一些重要的间接层.

我认为这是因为至少有两个不同的计算级别,第一个,即CFG的解析侧重于与语言结构(表示？)相关的语法,而另一个侧重于语义(意义,解释)数据本身？)与编程语言的功能有关,这是完整的.再次,这些假设是对的吗？

他们似乎对我有些混乱,但你走在正确的轨道上.一个关键问题是" 语言和编程语言之间有什么区别？" 答案是编程语言具有计算解释.计算解释有许多优良品种,并非所有这些都是图灵完整的.但神奇的是解释,而不是语法,所以乔姆斯基的层次结构在这里并不是很相关.

为了证明我的观点,一个极端的例子:常规语言[1-9][0-9]*是图灵完成的,其解释如下:

• SK-combinator语言是图灵完成的.
• 只有相当多的SK计划.
• 它们可以很容易地被唯一且确定地枚举.
• 因此,我们可以将每个正整数与SK程序相关联.
• 如果我们以标准方式将数字序列解释为正整数,我们同样可以很好地解释与SK程序相同的数字序列,而且,任何 SK程序都可以使用有限的数字序列来表达.

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

如果你的头现在没有受伤,它应该.