问为什么我们要用上下文无关的语言编写程序呢？程序不应该是递归可枚举的语言才是图灵完备的吗？

EN

你混淆了程序的规范和它的输出。

例如，可以接受递归可枚举语言的图灵机仍然由有限转移函数或“规则表”指定。规则表本身可以用常规语言表示。

话又说回来，只有现代编程语言的基本语法完全由上下文无关语法定义。一个有效的程序必须满足许多语法不能捕获的条件:标识符必须在使用前声明，一个函数只能定义一次，程序必须通过类型检查器，等等。

“大部分上下文无关”没有任何意义，就像“轻微怀孕”没有任何意义一样。这个属性要么存在，要么不存在，对于我使用过的任何编程语言，它都不存在。

但这并不是你可以在其中编写任意算法的原因。一种语言的源代码语法可能可以用特定的语法来描述，也可以不用来描述，但重要的是输入/输出行为。例如，打印形式为A^iB^iC^i的字符串的程序可以用Pascal编写，即使这些字符串不构成上下文无关语言。但这之所以可能，并不是因为Pascal语法比上下文无关强(尽管这是真的)，而是因为Pascal中构造的语义(最终，程序将在其上运行的von Neumann机器的概念)。