Geek Answers Handbook

Chomsky Hierarchy and LL (*)

I want to analyze a programming language. I read a lot about formal languages ​​and the hierarchy of Chomsky and ANTLR. But I could not find information on how to bind the ANTLR v3 languages, since the LL (*) parser of the recursive descent accepts the Chom hierarchy.

How are Chomsky types mixed with LL (*)? Any information (online, books, articles) is welcome.

Edit: how do syntactic / semantic predicates and reverse trace an ANTLR map into this?

+4
source share
2 answers

Chomsky Hierarchy mainly:

  • Regular languages
  • Context-Free Grammar
  • Context Sensitive Grammar
  • Recursively Enumerated (Turing-Complete) Grammars

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 the general context-free parser is O (n ^ 3), which is too slow to parse the program. Indeed, increasing the parser using auxiliary functions makes it stronger. The Wikipedia article on LL parsers explains this. The Dragon Book is considered the leading compiler tutorial and can explain further.

+12
source

LL (*) is a subset of context-free languages. However, another question is what antlr can analyze, given the predicates and backtracking that extend its capabilities.

Note that if we talk about LL (*), this means ANTLR v3, not 2.

+4
source

More articles:


All Articles