LL(1) Grammars

LL(1) GRAMMARS AND LANGUAGES. A context-free grammar G = (V_T, V_N, S, P) whose parsing table has no multiple entries is said to be LL(1). In the name LL(1),

• the first L stands for scanning the input from left to right,
• the second L stands for producing a leftmost derivation,
• and the 1 stands for using one input symbol of lookahead at each step to make parsing action decision.

A language is said to be LL(1) if it can be generated by a LL(1) grmmar. It can be shown that LL(1) grammars are

• not ambiguous and
• not left-recursive.

Moreover we have the following theorem to characterize LL(1) grammars and show their importance in practice.

Theorem 3   A context-free grammar G = (V_T, V_N, S, P) is LL(1) if and if only if for every nonterminal A and every strings of symbols $\alpha$,$\beta$ such that $\alpha$ $\neq$ $\beta$ and A  $\longmapsto$  $\alpha$  |  $\beta$ we have

1. FIRST($\alpha$)  $\cap$  FIRST($\beta$)  =  $\emptyset$,
2. if $\alpha$$\;\stackrel{{\ast}}{{\Longrightarrow}}\;$$\varepsilon$ then FIRST($\beta$)  $\cap$  FOLLOW(A)  =  $\emptyset$.

LL(K) PARSING TABLES. The notion of FIRST sets can be generalized to describe the first k tokens of a string (with k $\geq$ 1). This leads to LL(k) parsing tables where

• the rows are labelled by non-terminals and
• we have a column for every sequence of k terminals.

This is rarely done in practice since these tables are so large.

LL(K) GRAMMARS. Grammars parsable with LL(k) parsing tables are called LL(k) grammars. The LL(k) grammars have the following properties.

• If G is a LL(k) grammar then G is also a LL(k + 1) grammar (for every k $\geq$ 1).
• For every k $\geq$ 1, if G is a LL(k) grammar the G is not ambiguous.

Remark 7   Here are some practical observations on the use of LL(1) grammars and predictive parsing.

• The main difficulty in using predictive parsing is in writing a LL(1) grammar for the source language.
• The parser of a compiler often uses
  • predictive parsing methods for control constructs and
  • bottom-up parsing methods for expressions.