LL(k)

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

There are in general two ways to proceed. Start from $u$, and proceed backward to find $v$ such that $v\Rightarrow u$. Keep going until a derivation $\sigma {\Rightarrow }^{*}u$ is found. This procedure is known as the bottom-up parsing of $u$. The other method the top-down approach: begin with the starting symbol $\sigma$, and work its way down to $u$, so $\sigma {\Rightarrow }^{*}u$.

As with the bottom-up approach, finding a derivation of $u$ from the top-down may be time consuming, if one is lucky enough to find a derivation at all.

There is a class of grammars, known as the $LL(k)$ grammars, which make the top-down parsing of a word natural and direct. The first $L$ in $LL(k)$ means scanning the symbols of $u$ from left to right, the second $L$ stands for finding a leftmost derivation (${\Rightarrow }_L$) for $u$, and $k$ means having the allowance to look at up to $k$ symbols ahead while scanning.

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\in L(G)$ with a $X\to U_1$ a production in a leftmost derivation of $u$:

$$\sigma {\Rightarrow }_L^{*}UX{U}_2{\Rightarrow }_{L}U{U}_1{U}_2{\Rightarrow }_L^{*}u.$$

Let $n=|U|+k$ and $v$ be the prefix of $u$ of length $n$ (if , then set $v=u$).

Then $G$ is said to be $LL(k)$ if for any $w\in L(G)$, with $v$ as a prefix, such that there is a production $X\to W_1$ in a leftmost derivation of $w$:

$$\sigma {\Rightarrow }_L^{*}UX{W}_2{\Rightarrow }_{L}U{W}_1{W}_2{\Rightarrow }_L^{*}w,$$

implies that $W_1=U_1$.

In a leftmost derivation $D_u$ of a word $u$, call a prefix $v$ of $u$ is a leftmost descendant of a production $P\to U$ if $\sigma {\Rightarrow }^{*}vP{U}^{\prime }\Rightarrow vU{U}^{\prime }{\Rightarrow }^{*}u$ is $D_u$. Then the definition above can be restated in words as follows:

Given a leftmost derivation $D_u$ of a word $u$, a production used in $D_u$ is uniquely determined up to $k$ symbols beyond the prefix of $u$ which is a leftmost descendant of the production. In other words, if $D_u$ and $D_w$ are leftmost derivations of $u$ and $w$ which agree on $k$ symbols beyond the common prefix $v$, where $v$ is both a leftmost descendant of $X\to U$ used in $D_u$, and a leftmost descendant of $X\to W$ used in $D_w$, then $X\to U$ and $X\to W$ are the same production, i.e. $U=W$.

Every $LL(k)$ is unambiguous. Furthermore, every $LL(k)$ grammar is $LR(k)$ (http://planetmath.org/LRk).

Given a context-free grammar $G$ and $k\ge 0$, there is an algorithm deciding whether $G$ is $LL(k)$.

Examples

• The grammar $G$ over $\mathrm{\Sigma }=\{a,b\}$, with productions $\sigma \to a^2\sigma b^2$, $\sigma \to a$ and $\sigma \to \lambda$ is $LL(2)$ but not $LL(1)$. It is not hard to see that $L(G)$ is the set $\{a^m{b}^n\mid n\text{ is even, and }n\le m\le n+1\}$. On the other hand, the grammar $G^{\prime }$ over $\mathrm{\Sigma }$, with productions

  $$\sigma \to aX,\sigma \to \lambda ,X\to aYb,X\to \lambda ,Y\to aXb,Y\to b$$

  also generates $L(G)$, but is $LL(1)$ instead.

• The grammar $G$ over $\{a,b,c\}$, with productions

  $$\sigma \to X,\sigma \to Y,X\to aXb,X\to ab,Y\to aYc,Y\to ac$$

  is not $LL(k)$ for any $k\ge 0$.

Definition A language is said to be $LL(k)$ if it is generated by an $LL(k)$ grammar. The family of $LL(k)$ languages is denoted by $ℒℒ(k)$.

It is easy to see that an $LL(0)$ contains no more than one word. Furthermore, it can be shown that

$$ℒℒ(0)\subset ℒℒ(1)\subset \mathrm{\cdots }\subset ℒℒ(k)\subset \mathrm{\cdots },$$

and the inclusion is strict. If $ℒℒ{(k)}^{\prime }$ denotes the family of $\lambda$-free $LL(k)$ languages, then

$$ℒℒ{(0)}^{\prime }=ℒℒ{(1)}^{\prime }=\mathrm{\cdots }=ℒℒ{(k)}^{\prime }=\mathrm{\cdots }.$$

Given two $LL(k)$ grammars $G_1$ and $G_2$, there is an algorithm that decides if $L(G_1)=L(G_2)$.

Title	LL(k)
Canonical name	LLk
Date of creation	2013-03-22 19:00:54
Last modified on	2013-03-22 19:00:54
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q05
Classification	msc 68Q42
Classification	msc 03D10
Related topic	LRk