3
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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