Converting a context-free grammar into a LL(1) grammar

2
votes

First off, I have checked similar questions and none has quite the information I seek.

I want to know if, given a context-free grammar, it is possible to:

  • Know if there exists or not an equivalent LL(1) grammar. Equivalent in the sense that it should generate the same language.
  • Convert the context-free grammar to the equivalent LL(1) grammar, given it exists. The conversion should succeed if an equivalent LL(1) grammar exists. It is OK if it does not terminate if an equivalent does not exists.

If the answer to those questions are yes, are such algorithms or tools available somewhere ? My own researches have been fruitless.

Another answer mentions that the Dragon Book has an algorithms to eliminate left recursion and to left factor a context-free grammar. I have access to the book and checked it but it is unclear to me if the grammar is guaranteed to be LL(1). The restriction imposed on the context-free grammar (no null production and no cycle) are agreeable to me.

1
parsingcompiler-constructiongrammar
it's not Dragon Book - why uppercase?. Just a not-so-easy topic... – CapelliC
@chac: I didn't understand your sentence at all. Anyway, I said Dragon Book because I didn't remember the proper name of the book (it's "Compiler: Principles, Techniques, and Tools"). I didn't really think about using uppercase. – Norswap

1 Answers

2
votes

From university compiler courses I took I remember that LL(1) grammar is context free grammar, but context free grammar is much bigger than LL(1). There is no general algorithm (meaning not NP hard) to check and convert from context-free (that can be transformed to LL(1)) to LL(1).

Applying the bag of tricks like removing left recursion, removing first-follow conflict, left-factoring, etc. are similar to mathematical transformation when you want to integrate a function... You need experience that is sometimes very close to an art. The transformations are often inverse of each other.

One reason why LR type grammars are being used now a lot for generated parsers is that they cover much wider spectrum of context free grammars than LL(1).

Btw. e.g. C grammar can be expressed as LL(1), but C# cannot (e.g. lambda function x -> x + 1 comes to mind, where you cannot decide if you are seeing a parameter of lambda or a known variable).