使用上下文无关语法指定的编程语言如何能够表达图灵机？

Question

我一直在研究自动机理论、编译器和计算机科学的基础知识，但有一些基础知识我不明白。

我看到了乔姆斯基语言层次结构，其中具有不同表达能力的不同类别的语言与同等强大的自动机“相关联”。

来自维基百科：

语法语言自动机

• Type-0 递归可枚举图灵机
• Type-1 上下文相关的线性有界非确定性图灵机 -
• Type-2 上下文无关非确定性下推自动机
• Type-3 正则有限状态自动机

我已经看到每种编程语言都是图灵完备的，并且编程语言的语法规范（以 BNF 等形式化）可以表示为上下文无关语法。

上下文无关语法没有等效的“关联”图灵机。

在解释/编译期间，用编程语言（如 C、Python 等）编写的程序源代码的字符串被解析/翻译为抽象语法树。

（据我了解，这就像在将字符串与正则表达式匹配时从字符串中提取数组，只不过这里的模式不是正则表达式，它是上下文无关语法，更强大，因此提取的树结构包含比线性数组（来自正则表达式的捕获组）更多的信息。）

因此，编写的程序（可能实现图灵机）被转换为抽象语法树，并且原始程序中包含的所有信息现在都合并到树中。然后，在执行过程中，程序将完成一些像图灵机一样复杂的计算。

我的问题是： 在上下文无关语法规定的规则范围内表达的字符串如何实现图灵机，而等价语法/语言/自动机和乔姆斯基层次结构表明上下文无关语法的表达能力不够这样做？

我的假设之一是错误的吗？ 或者是记忆在其中发挥了作用，并且有一个定理说： 图灵机可以“使用”树+堆栈来实现？

这真让我烦恼。

任何可以启发我的东西都非常感激！

编辑：

这是我的问题的重复：

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

为什么我错误地认为编程语言的语法规范定义了它的语义？

因为 YACC 的作用：（语法导向翻译）

https://en.wikipedia.org/wiki/Syntax-directed_translation

它将用于解析编程语言（用于制作抽象语法树）的上下文无关语法的规则与操作相关联。 这就是我困惑的根源。

例如，这里是perl5解释器源代码摘录的复制粘贴。这是文件 perly.y，yacc 使用它来进行第一次编译。

   /* Binary operators between terms */
    termbinop:  term[lhs] ASSIGNOP term[rhs]   /* $x = $y, $x += $y */
                { $$ = newASSIGNOP(OPf_STACKED, $lhs, $ASSIGNOP, $rhs); }

        |   term[lhs] POWOP term[rhs]           /* $x ** $y */
            { $$ = newBINOP($POWOP, 0, scalar($lhs), scalar($rhs)); }

        |   term[lhs] MULOP term[rhs]           /* $x * $y, $x x $y */
                {   if ($MULOP != OP_REPEAT)
                    scalar($lhs);
                    $$ = newBINOP($MULOP, 0, $lhs, scalar($rhs));
                }

这显示了派生规则与其关联操作（大括号内的内容）之间的一一对应关系。

Answer 1

用于定义语言的语法“级别”决定了识别（解析）该语言所需的自动机，但它与该语言的“能力”无关。

例如，如果您使用 2 型语法 (CFG) 来定义一种语言，乔姆斯基层次结构会告诉您需要一个下推自动机来识别它，但该语言可能是图灵完备的编程语言，也可能是是一种正则表达式的语言，或者它可能是一种根本没有计算“能力”的语言。

举一个更极端的例子，您可以想象使用 Type 3 语法（正则表达式）来定义一种用于“编程”图灵机的语言。

一种语言的力量（特别是它是否是图灵完备的）取决于它的语义，而不是它的语法。

Answer 2

考虑一个简单的情况，

whitespace是一种常规语言，它甚至不是上下文无关语法（CFG）。然而，这种语言能够表达图灵机——前提是你需要找到一台可以运行空白的机器，而这台机器显然必须是图灵完备的。