Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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:
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.
