The $LL(k)$ Parsers

In general we can define a class of grammars known as the $LL(k)$ grammars, where $k$ represents the number of lookahead symbols needed to eliminate any element of choice from a parse.

L

= Scanning the input from Left to right

L

= Conducting a Leftmost derivation

k

= Using $k$ symbols of lookahead

Any (regular) grammar constructed from a DFA will be $LL(0)$ since we do not need to use FIRST or FOLLOW.

The class of grammars for which we need only one symbol of lookahead are called$LL(1)$ grammars - the definitions for FIRST and FOLLOW given earlier correspond to this case.

Sometimes when we construct an parse table there will be two or more rules in the same box. In this situation we say that the grammar is ``not $LL(1)$'', since the algorithm has clearly failed to indicate a non-deterministic parse in all cases.

For any $k$ in $\{2,3,4,\ldots\}$, we can adjust the definitions of FIRST and FOLLOW so that they use $k$ symbols of lookahead; this will give us an $LL(k)$ parse table. We say that a language is $LL(k)$ if there are no duplicate entries in its $LL(k)$ parse table.

Making $k$ greater means that we will be able to parse more languages, but it also means that the algorithm will be more complex, and the resulting parse table will be larger. In general $LL(1)$ grammars represent the most acceptable compromise between power of expression and ease of implementation for top-down parsers.