我正在尝试学习与编程语言相关的 Chomsky Hierarchy 的某些方面，但我仍然需要阅读 Dragon Book。
我读过大多数编程语言都可以解析为上下文无关语法（CFG）。就计算能力而言，它等于下推非确定自动机之一。我对吗？
如果是真的，那么一个 CFG 怎么可能持有图灵完备的无限制语法（UG）？我之所以问是因为，即使 CFG 描述了编程语言，它们实际上也用于描述图灵机，因此通过 UG。
我认为这是因为至少有两个不同级别的计算，第一个是 CFG 的解析，侧重于与语言的结构（表示？）相关的语法，而另一个侧重于语义（意义，解释数据本身？）与图灵完备的编程语言的能力有关。同样，这些假设是否正确？
我读过大多数编程语言都可以解析为上下文无关语法（CFG）。就计算能力而言，它等于下推非确定自动机之一。我对吗？
技术上是的。有用的是，不。
至少有两种有用的方法来思考这些问题：
困难在于，虽然大多数编程语言都有一个很容易用上下文无关文法描述的底层结构（Tcl 是一个有趣的例外）， 但很多用上下文无关文法描述的句子实际上并不是“在语言中”。其中“语言”是指“相关语言的有效程序”。这些额外的句子通常被某种形式的静态语义所排除。例如，以下话语是 C 程序的上下文无关文法中的一个句子，但它本身不在有效的 C 程序集中：
int f(void) { return n + 1; }
这里的问题n是不在范围内。C 需要“使用前声明”，并且该属性不能使用上下文无关文法来表达。
真实编程语言的典型决策过程是编译器或解释器前端的一部分，它至少有两个部分：一是解析器，在决策能力上相当于下推自动机；二是解析器。但是第二个进行了额外的检查，排除了许多无效的话语。如果这些检查需要任何类型的使用前定义属性，则它们不能通过下推自动机或上下文无关文法来完成。
如果是真的，那么一个 CFG 怎么可能持有图灵完备的无限制语法（UG）？
CFG 不“持有”任何东西——它只是描述一种语言。
...即使编程语言由 CFG 描述，它们实际上也用于描述图灵机，因此通过 UG。
您在这里跳过了一些重要的间接级别。
我认为这是因为至少有两个不同级别的计算，第一个是 CFG 的解析，侧重于与语言的结构（表示？）相关的语法，而另一个侧重于语义（意义，解释数据本身？）与图灵完备的编程语言的能力有关。同样，这些假设是否正确？
他们对我来说似乎有点混乱，但你在正确的轨道上。一个关键问题是“语言和编程语言之间有什么区别？” 答案是编程语言具有计算解释。计算解释有很多种，但并不是所有的都是图灵完备的。但神奇之处在于解释，而不是语法，因此乔姆斯基层次结构在这里并不是很重要。
为了证明我的观点，举一个极端的例子：常规语言[1-9][0-9]*在以下解释下是图灵完备的：
因此整数文字的语言是图灵完备的。
如果你的头现在不疼，它应该。
这绝对不是真的。大多数编程语言都有可以用 CFG 或 BNG 描述的语法，但符合语法并不能保证程序合法。有各种各样的额外条件，例如“变量必须在使用前声明”或“这个表达式中的类型必须以合法的方式组合”，这些都是语法未涵盖的，这就是使语言成为非上下文的原因-自由。（这有点像 XML，它具有形式上可验证的定义，但通常还有解析器无法验证的额外约束。）
一个非常好的语言示例，它的语法没有 CFG 是 C++。您似乎没有完全了解UG。通用语法是一个解释问题，描述为包含图灵机代码和该图灵机接受的单词的单词语言。因此，您不编码语言本身（一组单词），而是编码它的图灵机。现在到了重点——你可以拥有一种无限词的语言，但你不能拥有一种无限符号的词。这意味着，UG 也包含有限的单词，因此对图灵机的所有描述都是有限的。因此，图灵机的描述（编程语言中的程序）具有有限数量的符号（语句），因此描述语言（编程语言语法语法）甚至可以是规则的。例如在二进制组合逻辑。