2 Fixing the productions of A and B. edited Jun 17 at 5:34 Pseudonym 10.5k11 gold badge2121 silver badges4343 bronze badges 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}\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. 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. 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. 1 answered Jun 17 at 3:34 rici 5,37688 silver badges2424 bronze badges 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.