next up previous
Next: YACC - Yet Another Compiler Up: Parsing Previous: Non-recursive implementation of predictive parsing

LL(1) Grammars

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

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 Moreover we have the following theorem to characterize LL(1) grammars and show their importance in practice.

Theorem 3   A context-free grammar G = (VT, VN, 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

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.

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


next up previous
Next: YACC - Yet Another Compiler Up: Parsing Previous: Non-recursive implementation of predictive parsing
Marc Moreno Maza
2004-12-02