LL(k)
Given a word $u$ and a contextfree 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 bottomup parsing of $u$. The other method the topdown approach: begin with the starting symbol $\sigma $, and work its way down to $u$, so $\sigma {\Rightarrow}^{*}u$.
As with the bottomup approach, finding a derivation of $u$ from the topdown 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 topdown 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 contextfree 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 contextfree 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 $\mathcal{L}\mathcal{L}(k)$.
It is easy to see that an $LL(0)$ contains no more than one word. Furthermore, it can be shown that
$$\mathcal{L}\mathcal{L}(0)\subset \mathcal{L}\mathcal{L}(1)\subset \mathrm{\cdots}\subset \mathcal{L}\mathcal{L}(k)\subset \mathrm{\cdots},$$ 
and the inclusion is strict. If $\mathcal{L}\mathcal{L}{(k)}^{\prime}$ denotes the family of $\lambda $free $LL(k)$ languages, then
$$\mathcal{L}\mathcal{L}{(0)}^{\prime}=\mathcal{L}\mathcal{L}{(1)}^{\prime}=\mathrm{\cdots}=\mathcal{L}\mathcal{L}{(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})$.
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Title  LL(k) 

Canonical name  LLk 
Date of creation  20130322 19:00:54 
Last modified on  20130322 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 