乔姆斯基层次结构和 LL(*) 解析器
我想解析一种编程语言。 我读了很多关于形式语言、乔姆斯基层次结构和 ANTLR 的内容。 但我找不到有关如何将 ANTLR v3 作为 LL(*) 递归下降解析器接受的语言与乔姆斯基层次结构相关联的信息。
乔姆斯基类型如何与 LL(*) 混合？ 非常感谢任何信息（在线、书籍、论文）。
编辑：ANTLR 的句法/语义谓词和回溯如何映射到此？
I want to parse a programming language. I read a lot about formal languages and the Chomsky hierarchy and ANTLR. But I could not find information on how to relate the languages ANTLR v3 as an LL(*) recursive descent parser accepts to the chomsky hierarchy.
How do the Chomsky types mix with LL(*)? Any information (online, books, papers) are greatly appreciated.
Edit: How do syntactic / semantic predicates and backtracking of ANTLR map into this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
乔姆斯基层次结构基本上是：
LL 语法（和解析器）是上下文无关语法的子集。 使用它们是因为常规语言对于编程目的太弱，并且一般的上下文无关解析器的时间复杂度为 O(n^3)，这对于解析程序来说太慢。
事实上，用辅助函数增强解析器确实会使其变得更强大。
有关 LL 解析器的 Wikipedia 条目对此进行了一些解释。The Dragon Book 被认为是编译器方面的领先教科书，并且可以进一步解释。
The Chomsky Hierarchy is basically:
LL Grammars (and parsers) are a subset of context-free grammars. They are used because regular languages are too weak for programming purposes and because a general context-free parser is O(n^3) which is too slow for parsing a program.
Indeed, augmenting a parser with helper functions does make it stronger.
The Wikipedia entry on LL parsers explains some of this.The Dragon Book is considered a leading textbook on compilers, and may explain further.
LL(*) 是上下文无关语言的子集。 然而，一个不同的问题是，在给定谓词和回溯的情况下，antlr 可以解析什么，这扩展了它的能力。
请注意，如果我们谈论 LL(*)，则意味着 ANTLR v3，而不是 2。
LL(*) is a subset of context-free languages. However, a different question is what antlr can parse, given predicates and backtracking, which extend its abilities.
Note that if we talk about LL(*), that means ANTLR v3, not 2.