0
$\begingroup$

It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And the opposite? Is there a LL(K) Grammar which is not LALR(K) Grammar? Do you have an example?

Related:

  1. Are regular expressions $LR(k)$?
  2. https://stackoverflow.com/questions/14674912/why-are-there-lr0-parsers-but-not-ll0-parsers
  3. https://stackoverflow.com/questions/36652221/relationship-between-lr0-ll0-lalr1-etc
$\endgroup$
  • $\begingroup$ This question is answered in cs.stackexchange.com/questions/43/…, but without an example. (It's marked as a "simple exercise".) I provided an answer with an example, but you might still want to take a little time to try to come up with your own. $\endgroup$ – rici Jun 17 at 3:39
6
$\begingroup$

Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$.

There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen

$$\begin{align}S &\to a A a \mid b A b \mid a B b \mid b B a\\ A &\to c \\ B &\to c \end{align}$$

The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $LL(3)$.) The grammar is also $LR(1)$. However, the grammar is not $LALR(k)$ for any value of $k$.

The canonical $LR(k)$ machine has two states with $LR(0)$ itemsets $\{[A\to c \cdot], [B\to c\cdot]\}$. These two states have different lookahead sets in each item, corresponding to the two different predecessor states before shifting $c$. The $LALR$ algorithm merges these two states, thereby losing the distinction between the lookahead sets. This produces two reduce-reduce conflicts. Since there is only one token of lookahead at this point, increasing $k$ would make no difference.

$\endgroup$

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.