# CS606 - Compiler Construction - Lecture Handout 19

User Rating:     / 0
PoorBest

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