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

Question

我一直在研究自动机理论、编译器和 CS 的基础知识，但有些基础知识我不了解。

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

来自维基百科：

语法语言自动机

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

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

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

在解释/编译过程中，用编程语言（如C，python等）编写的程序的源代码字符串被parsed/translated转换为抽象语法树.

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

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

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

我的假设之一是错误的吗？或者是 memory 在其中发挥作用的事实，并且有一个定理说的是这样的：可以“使用”树 + 堆栈 ?

实现图灵机

这真的很烦我。

任何能启发我的东西都非常感谢！

编辑：

这是我的问题 DUPLICATE :

chomsky hierarchy and programming languages

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

因为 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

您用来定义语言的 'level' 语法决定了识别（解析）该语言所需的自动机，但它与该语言的“功能”无关。

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

举一个更极端的例子，你可以想象使用 Type 3 文法（正则表达式）为 'programming' 图灵机定义语言。

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

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

How can a programming language that is specified using a context-free grammar, be capable of expressing a Turing Machine?

compilation

interpreter

context-free-grammar

automata

turing-machines