CS606 - Compiler Construction - Lecture Handout 19

User Rating:  / 0

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

LL(1) Table Construction

Here now is the algorithm to construct a predictive parsing table.

  1. For each production A? a
    1. for each terminal a in FIRST(a), add A? a to M[A,a].
    2. If e is in FIRST(a), add A? a to M[A,b] for each terminal b in FOLLOW(A). If e is in FIRST(a), and $ is in FOLLOW(A), add A? a to M[A,$].

  2. Make each undefined entry of M be error.

Let us apply the algorithm to the expression grammar. Since FIRST(TE ') = FIRST(T ) = { (, id }, the production E ? TE' cause M[E,(] and M[E,id] to get E ? TE'. The production E' ? +TE' causes M[E',+] to get E' ? +TE'. The production E' ? e causes M[E',)] and M[E',$] to get E' ? e since FOLLOW (E' ) = { ), $ }. And so on. The final parsing table produced is:

  id + * ( ) $
E E ? TE'     E ? TE'    
E'   E' ? +TE'     E' ? e E' ? e
T T ? FT'     T ? FT'    
T'   T' ? e T ? *FT'   T' ? e T' ? e
F F ? id     F ? (E )    

Left Factoring

Consider the grammar

E ? T + E | T
T ? int | int* T | (E)

It is impossible to predict because for T, two productions start with int. For E, it is not clear how to predict; the two productions start with the non-terminal T. A grammar must be left factored before use for predictive parsing. The procedure to left-factor a grammar is as follows:

If a ยน e, replace all productions

replace all productions

Example: consider following fragment of expression grammar

Factor ? id
| id [ ExprList ]
| id ( ExprList )

After left factoring, the grammar becomes

Factor ? id Args
Args ? [ ExprList ]
| ( ExprList )
| e

Given a CFG that does not meet the LL(1) condition, it is undecidable whether or not an equivalent LL(1) grammar exists.