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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ FWIW, the answer linked by the OP clearly distinguishes between grammar and language world. $\endgroup$
    – Raphael ♦
    Jul 19, 2016 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, 2016 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, 2016 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, 2016 at 17:23

Your Answer

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

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