# Determining if a grammar can be converted to LL(1)/LL(k)

(This is a cross-post of http://cstheory.stackexchange.com/questions/11676/determining-if-a-grammar-can-be-converted-to-ll1-llk in the hopes of gaining a wider audience.)

I'd like to know if there is a way to determine if a context-free grammar can be converted to

• a LL(1) grammar
• a LL(k) grammar, whatever the value of k (so the algorithm should give the value of k)

By "can be converted to", I mean that the new (LL) grammar must generate the same language as the old grammar.

If it can't be done, I'd appreciate some references. I'm also interested in ways to achieve the same result under more restrictive conditions (for instance only for non-ambiguous context-free grammars).

-
Try dl.acm.org/citation.cfm?id=805431: it proves both your problems undecidable in general, and proves the second decidable if your grammar is LR(k') for some k'. –  Alex ten Brink Jun 8 '12 at 23:58
Thanks a lot :) –  Norswap Jun 10 '12 at 8:51

Copying this answer from @AlextenBrink's comment:

Try Properties of deterministic top down grammars by D.J. Rosenkrantz and R.E. Stearns. It proves both your problems undecidable in general, and proves the second decidable if your grammar is LR($k'$) for some $k'$.