LR(k)

Given a word $u$ and a context-free grammar $G$, how do we determine if $u\in L(G)$?

One way is to look for any subword $v$ of $u$ such that there is a production $A\to v$. If this is successful, we may replace $v$ with $A$ in $u$ to obtain a word $w$, so that $w\Rightarrow u$. We may then repeat the process on $w$ to obtain another word $x$ such that $x\Rightarrow w$ (if successful). In the end, if everything works successfully, we arrive at the starting non-terminal symbol $\sigma$, and get a derivation $\sigma {\Rightarrow }^{*}u$ as a result, so that $u\in L(G)$. This procedure is known as the bottom-up parsing of the word $u$.

In general, unless one is very lucky, successfully finding a derivation $\sigma {\Rightarrow }^{*}u$ requires many trials and errors, since at each stage, for a given word $u$, there may be several words $w$ such that $w\Rightarrow u$.

Nevertheless, there is a particular family of context-free grammars, called the $LR(k)$ grammars, which make the bottom-up parsing described above straightforward in the sense that, given a word $u$, once a word $w$ is found such that $w{\Rightarrow }_{R}u$, any other word $w^{\prime }$ such that $w^{\prime }{\Rightarrow }_{R}u$ forces $w^{\prime }=w$. Here, ${\Rightarrow }_R$ is known as the rightmost derivation (meaning that $u$ is obtained from $w$ by replacing the rightmost non-terminal in $w$). The $L$ in $LR(k)$ means scanning the symbols of $u$ from left to right, $R$ stands for finding a rightmost derivation for $u$, and $k$ means having the allowance to look at up to $k$ symbols ahead while scanning.

The details are as follows:

Definition. Let $G=(\mathrm{\Sigma },N,P,\sigma )$ be a context-free grammar such that $\sigma \to \sigma$ is not a production of $G$, and $k\ge 0$ an integer. Suppose $U$ is any sentential form over $\mathrm{\Sigma }$ with the following setup: $U=U_1{U}_2{U}_3$ where

• $U_3$ is a terminal word,

• $X\to U_2$ a production, and

• $\sigma {\Rightarrow }_R^{*}{U}_{1}X{U}_3{\Rightarrow }_{R}U$.

Let $n=|U_1{U}_2|+k$, and $Z$ the prefix of $U$ of length $n$ (if , then set $Z=U$).

Then $G$ is said to be $LR(k)$ if $W$ is another sentential form having $Z$ as a prefix, with the following setup: $W=W_1{W}_2{W}_3$, where

• $W_3$ is a terminal,

• $Y\to W_2$ is a production, and

• $\sigma {\Rightarrow }_R^{*}{W}_{1}Y{W}_3{\Rightarrow }_{R}W$,

implies that

$$W_1=U_1,Y=X,\text{and}\mathit{\hspace{1em}\hspace{1em}}{W}_2=U_2.$$

Simply put, if $D_U$ and $D_W$ are the rightmost derivations of $U$ and $W$ respectively, and if the prefix of $U$ obtained by including $k$ symbols beyond the last replacement in $D_U$ is also a prefix of $W$, then the prefix of $U^{\prime }$ obtained by including $k$ symbols beyond the last replacement in $D_U$ is also a prefix of $W^{\prime }$, where $U^{\prime }$ and $W^{\prime }$ are words at the next to the last step in $D_U$ and $D_W$ respectively. In particular, if $U=W$, then $U^{\prime }=W^{\prime }$. This implies that any derivable in an $LR(k)$ grammar has a unique rightmost derivation, hence

Proposition 1.

Any $L\mathit{}R\mathit{}\mathrm{(}k\mathrm{)}$ grammar is unambiguous.

Examples.

• Let $G$ be the grammar consisting of one non-terminal symbol $\sigma$ (which is also the final non-terminal symbol), two terminal symbols $a,b$, with productions

  $$\sigma \to a\sigma b,\sigma \to \sigma b\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}\sigma \to b.$$

  Then $G$ is not $LR(k)$ for any $k\ge 0$.For instance, look at the following two derivations of $U=a^2\sigma b^3$:

  $$\sigma {\Rightarrow }^{*}a\sigma b^2\Rightarrow a^2\sigma b^3\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}\sigma {\Rightarrow }^{*}{a}^2\sigma b^2\Rightarrow a^2\sigma b^3$$

  Here, $U_1=a$, $U_2=\sigma b$. Let $k=1$. Then the criteria in the definition are satisfied. Yet, $W_1=a^2\ne U_1$. Therefore, $G$ is not $LR(1)$.

• Note that the grammar $G$ above generates the language $L=\{a^m{b}^n\mid n>m\}$, which can also be generated by the grammar with three non-terminal symbols $\sigma ,X,Y$, with $\sigma$ the final non-terminal symbol, where the productions are given by

  $$\sigma \to XY,X\to aXb,X\to \lambda ,Y\to Yb,\text{and}\mathit{\hspace{1em}}Y\to b.$$

  However, this grammar is $LR(1)$.

Determining whether a context-free grammar is $LR(k)$ is a non-trivial problem. Nevertheless, an algorithm exists for determining, given a context-free grammar $G$ and a non-negative integer $k$, whether $G$ is $LR(k)$. On the other hand, without specifying $k$ in advance, no algorithms exist that determine if $G$ is $LR(k)$ for some $k$.

Definition. A language is said to be $LR(k)$ if it can be generated by an $LR(k)$ grammar.

Theorem 1.

Every $L\mathit{}R\mathit{}\mathrm{(}k\mathrm{)}$ language is deterministic context-free. Every deterministic context-free language is $L\mathit{}R\mathit{}\mathrm{(}\mathrm{1}\mathrm{)}$.

Hence, deterministic context-free languages are the same as $LR(1)$ languages.