programming-languages - 我们为什么用上下文无关语言编写程序？为了图灵完备，程序不应该使用递归可枚举语言吗？

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

9年前关闭。




Improve this question




如果我们主要使用上下文无关语言进行编码，我真的无法理解我们如何模拟图灵机(它接受递归可枚举语言)的输出。

Answer 1

您将程序的规范与其输出混淆了。

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

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