# Does my grammar contradict LL ⊆ LR(1)?

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.

## 1 Answer

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.

• FWIW, the answer linked by the OP clearly distinguishes between grammar and language world. – Raphael Jul 19 '16 at 15:52
• @Raphael True, though if you don't know to look for it it's really easy to miss this. – templatetypedef Jul 19 '16 at 16:28
• How so? The answer is structured along these lines using big, fat headlines. Can it be made clearer? (Honest question; we could edit the answer.) – Raphael Jul 19 '16 at 17:07
• @Raphael It's primarily the fact that there's a difference between $LL$ languages and $LL$ grammars. If you're only familiar with $LL$ and $LR$ in the context of parsing, you're probably only used to thinking about whether a grammar can be $LL$ and $LR$ and wouldn't recognize the significance of saying that a language would be $LL$ or $LR$. (I've seen a ton of students get really, really confused by this in the past). I don't think it's a clarity issue - if you know these terms, the answer is very clear - as much as a concept issue - you need to know the concept to understand the post. – templatetypedef Jul 19 '16 at 17:23