What is a LL(1) grammar

The basic idea of a recursive descent parser is to use the current input symbol to decide which alternative to choose. Grammars which have the property that it is possible to do this are called LL(1) grammars.

First we introduce an end marker $\$, for a given $G=(V,\Sigma,S,P)$ we define the augmented grammar $G^\$=(V',\Sigma',S',P')$ where

• $V'=V\cup \{S'\}$ where $S'$ is chosen s.t. $S' \notin V\cup\Sigma$,
• $\Sigma' = \Sigma\cup \{\$\}$ where $\$ is chosen s.t. $\$ \notin V\cup\Sigma$,
• $P'=P\cup\{S'\to S \$\}$

The idea is that

$$L(G^\$) = \{ w\$ \mid w\in L(G) \}$$

Now for each nonterminal symbol $A\in V'\cup \Sigma'$ we define

$$\textrm{First}(A) = \{ a \mid a\in\Sigma \wedge A \Rightarrow ^* a\beta \}$$

$$\textrm{Follow}(A) = \{ a \mid a\in\Sigma \wedge S' \Rightarrow ^* \alpha A a \beta \}$$

i.e. $\textrm{First}(A)$ is the set of terminal symbols with which a word derived from $A$ may start and $\textrm{Follow}(A)$ is the set of symbols which may occur directly after $A$. We use the augmented grammar to have a marker for the end of the word.

For each production $A\to\alpha\in P$ we define the set $\textrm{Lookahead}(A\to\alpha)$ which are the set of symbols which indicate that we are in this alternative.

$$\textrm{Lookahead}(A\to B_1 B_2 \dots B_n) = \bigcup \{ \textrm{First}(B_i) \mid \forall 1\leq k < i.B_k\Rightarrow ^* \empty \}$$

$$\cup \left\{ \begin{array}{ll}\textrm{Follow}(A) & \textrm{if $B_... ...k \Rightarrow \epsilon$} \ \emptyset & \textrm{otherwise} \end{array}\right.$$

We now say a grammar $G$ is LL(1), iff for each pair $A\to\alpha,A\to\beta\in P$ with $\alpha\not=\beta$ it is the case that $\textrm{Lookahead}(A\to\alpha)\cap\textrm{Lookahead}(A\to\beta)=\emptyset$