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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
I’m not an expert on this topic, but I found these course notes (including some bibliographical references) which state that the language L = {x^{n} : n ∈ ℕ} ∪ {x^{n}y^{n} : n ∈ ℕ} has no LL(k) parser, while being deterministic contextfree (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 = {a^{n}b^{n}, a^{n}c^{n} : n ≥ 1} is not LL (see Theorem 5.2). 

