2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ FWIW, the answer linked by the OP clearly distinguishes between grammar and language world. $\endgroup$ – Raphael Jul 19 '16 at 15:52
  • $\begingroup$ @Raphael True, though if you don't know to look for it it's really easy to miss this. $\endgroup$ – templatetypedef Jul 19 '16 at 16:28
  • $\begingroup$ 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.) $\endgroup$ – Raphael Jul 19 '16 at 17:07
  • $\begingroup$ @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. $\endgroup$ – templatetypedef Jul 19 '16 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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