User Rating: / 0
**Related Content:** CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

Note that productions output are tracing out a lefmost derivation. The grammar symbols
on the stack make up left-sentential forms.

## LL(1) Table Construction

Top-down parsing expands a parse tree from the start symbol to the leaves. It always
expand the leftmost non-terminal. Consider the state

### S ? * bAg

with b the next token and we are trying to match bbg. There are two possibilities

- b belongs to an expansion of A.

Any A ? a can be used if b can start a string derived from a. In this case we say
that b Î FIRST(a)
- b does not belong to an expansion of A. Expansion of A is empty, i.e., A ? e
and b belongs an expansion of g, e.g., bw. which means that b can appear after A
in a derivation of the form S ? * bAbw. We say that b Î FOLLOW(A).

Any A ? a can be used if a expands to e. We say that e Î FIRST(A) in this case.

## Definition

FIRST(X) = { b | X ? * ba } È { e | X ? * e }