Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

1 Answer 1

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