Chomsky层次结构和LL(*)分析器

Question

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

Chomsky类型如何与LL(*)混合？任何信息(在线、书籍、论文)都非常受欢迎。

编辑: ANTLR的语法/语义谓词和回溯是如何映射到这一点的？

Answer 1

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

可枚举的常规languages

• Context-Free Grammars

• Context-Sensitive Grammars

• Recursively (图灵完整)语法

LL文法(和解析器)是上下文无关文法的子集。使用它们是因为常规语言对于编程目的来说太弱了，而且一般的上下文无关解析器是O(n^3)，这对于解析程序来说太慢了。实际上，使用helper函数增强解析器确实会使其变得更强大。The Wikipedia entry on LL parsers解释了其中的一部分，The Dragon Book被认为是一本领先的编译器教科书，可能会进一步解释。

Answer 2

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

请注意，如果我们谈论LL(*)，那意味着ANTLR v3，而不是2。