乔姆斯基层次结构和 LL(*) 解析器

Question

我想解析一种编程语言。我读了很多关于形式语言、乔姆斯基层次结构和 ANTLR 的内容。但我找不到有关如何将 ANTLR v3 作为 LL(*) 递归下降解析器接受的语言与乔姆斯基层次结构相关联的信息。

乔姆斯基类型如何与 LL(*) 混合？非常感谢任何信息（在线、书籍、论文）。

编辑：ANTLR 的句法/语义谓词和回溯如何映射到此？

Answer 1

乔姆斯基层次结构基本上是：

1. 常规语言
2. 上下文无关语法
3. 上下文相关语法
4. 递归可枚举（图灵完备）语法

LL 语法（和解析器）是上下文无关语法的子集。使用它们是因为常规语言对于编程目的太弱，并且一般的上下文无关解析器的时间复杂度为 O(n^3)，这对于解析程序来说太慢。事实上，用辅助函数增强解析器确实会使其变得更强大。LL 解析器的 Wikipedia 条目 解释了其中的一些内容。龙之书 被认为是编译器方面的领先教科书，并且可以进一步解释。

Answer 2

LL（*）是上下文无关语言的子集。然而，一个不同的问题是什么ANTLR可以解析，给定的谓词和回溯，延伸它的能力。

请注意，如果我们谈论LL（*），这意味着ANTLR V3，而不是2。