Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?


Here's one pattern for an LR(k) grammar which is not LR(k-1). I didn't fill in the definition of $A$; there's nothing particularly special about it. It might have an empty right-hand side, or it might match any LR(k) subgrammar. $a^k$ represents $k$ instances of $a$.

$$ \begin{align}S&\to B a^{k-1} b\\ S&\to C a^{k-1} c\\ B&\to A\\ C&\to A\\ A&\to \text{see above} \end{align} $$

Clearly, it is not possible to determine whether $A$ should be reduced to $B$ or to $C$ without knowing what the $k$ following token is. So the grammar is not LR(i) for any $i \lt k$. The reduction can be determined using $k$ lookahead tokens, so the grammar is LR(k) provided that $A$ is.

| cite | improve this answer | |

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.