How to create a LR(k) grammar for an arbitrary k

Question

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

Answer 1

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.