Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction
Here now is the algorithm to construct a predictive parsing table.
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 ) |
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.