World's most popular travel blog for travel bloggers.

, ,
Problem Detail:

This answer claims that $LL \subseteq LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$.

But is this true? Is this grammar a valid counterexample?

$S \rightarrow a | Aaa$, $A \rightarrow \varepsilon$

It's easy to show that this grammar is not $LR \left( 1 \right )$, but I think that it is in $LL(2)$ - the longest string that can be derived is two letters so a lookahead of two tokens should be sufficient.

Confusingly, the terms $LL$ and $LR$ are overloaded. There are two related but fundamentally different classes of objects that we'd call $LL$ or $LR$:

• The sets of all grammars that are $LL(k)$ or $LR(k)$ for some choice of $k$. Let's call these sets $LL_{CFG}$ and $LR_{CFG}$.
• The sets of all languages that have an $LL(k)$ or $LR(k)$ grammar for some choice of $k$. Let's call these sets $LL_{LANG}$ and $LR_{LANG}$.

The example you've given is a grammar that is $LL(2)$ (I believe) but not $LR(1)$. This shows that $LL_{CFG} \not\subseteq LR(1)_{CFG}$. However, there is a different grammar that you could pick for the same language that is $LR(1)$, which follows because $LL_{LANG} \subseteq LR(1)_{LANG}$. This happens because $LR(1)_{LANG}$ is precisely the set of all deterministic context-free languages and all $LL$ languages are deterministic.