parsing - Chomsky 层次结构和 LL(*) 解析器

Question

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

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

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

Answer 1

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

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

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

Answer 2

LL(*) 是上下文无关语言的一个子集。然而，一个不同的问题是 antlr 可以解析什么，给定谓词和回溯，这扩展了它的能力。

请注意，如果我们谈论 LL(*)，则表示 ANTLR v3，而不是 2。