__ LL(1) GRAMMARS AND LANGUAGES.__ A context-free grammar

- the first
*L*stands for scanning the input from**l**eft to right, - the second
*L*stands for producing a**l**eftmost derivation, - and the 1 stands for using
**one**input symbol of lookahead at each step to make parsing action decision.

- not ambiguous and
- not left-recursive.

- FIRST() FIRST() = ,
- if
then
FIRST() FOLLOW(
*A*) = .

__ LL(K) PARSING TABLES.__ The notion of FIRST sets can be generalized to describe
the first

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

__ LL(K) GRAMMARS.__ Grammars parsable with

- If
*G*is a*LL*(*k*) grammar then*G*is also a*LL*(*k*+ 1) grammar (for every*k*1). - For every
*k*1, if*G*is a*LL*(*k*) grammar the*G*is not ambiguous.

- 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.

2004-12-02