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

Question

我想解析一种编程语言。我阅读了很多关于形式语言、乔姆斯基层次和ANTLR的内容。但是我找不到有关如何将ANTLR v3接受的语言与乔姆斯基层次相关联的信息。

乔姆斯基类型如何与LL(*)混合？任何信息（在线、书籍、论文）都将不胜感激。

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

- meelow

Answer 1

乔姆斯基的语言层次结构基本上包括：

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

LL语法（和解析器）是上下文无关语法的子集。它们被使用是因为正则语言在编程目的上过于弱小，而一般的上下文无关解析器是O(n^3)的，这对于解析程序来说太慢了。实际上，用辅助函数增强解析器可以使其更强大。 维基百科上关于LL解析器 解释了其中一些内容。龙书 被认为是编译器领域的一本主要教材，可能会进一步解释。

- Yuval F

Answer 2

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

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

- jpalecek