Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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).

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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'$.

Sadly, I was not able to find a freely downloadable copy of this paper online. (ACM journal papers are usually licensed for free distribution for scholarly purposes. If a copy comes to light, I will link it here.)

Here is a possibly relevant se.cs thread: Language theoretic comparison of LL and LR grammars

share|improve this answer

Possibly also of interest is Peter Pepper's detailed presentation of how to perform simple transformations on a CFG to end up with an LL grammar (if the original was LR(k)). LR Parsing = Grammar Transformation + LL Parsing

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.