Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 17

User Rating:  / 0
PoorBest 

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

  1. 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)
  2. 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 }