MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Every deterministic context free grammar can be represented by a LR(1) grammar, so this question can be rephrased as: can I build an equivalent LL(k) grammar from every LR(k) grammar? Can I have an example of deterministic context free language that can not have an LL(k) grammar?

share|cite|improve this question
up vote 2 down vote accepted

I’m not an expert on this topic, but I found these course notes (including some bibliographical references) which state that the language L = {xn : n ∈ ℕ} ∪ {xnyn : n ∈ ℕ} has no LL(k) parser, while being deterministic context-free (see pp. 24 and 27).

Edit: I found a better reference. The paper Two iteration theorems for the LL(k) languages by J.C. Beatty contains a proof that the LR language L = {anbn, ancn : n ≥ 1} is not LL (see Theorem 5.2).

share|cite|improve this answer

Your Answer


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.