Question

Give the predictive parsing table for the following grammar:

E -> T E’                 (Do not forget to consider $)

E’ -> + T E’ | e ( e stand for empty string)

                                       T -> F T’

                                       T’ -> * F T’ | e

                                       F -> ( E ) | id | num

Answer 1

Answer:

Construction of the predictive parsing table involves the following steps.

(1) Identifying FIRST(α): FIRST(α) is the set of terminal symbols that begin the strings derivable from a string of terminal and nonterminal symbols α in a grammar.
If α can derive ε, then ε is also in FIRST(α).

The algorithm to compute FIRST(X):

                          1. If X is a terminal, then FIRST(X) = { X }.

                          2. If X → ε is a production, then add ε to FIRST(X).

                          3. If X → Y1 Y2 ... Yk is a production for k ≥ 1, and
                for some i ≤ k, Y1Y2 ... Yi-1 derives the empty string, and a is in FIRST(Yi), then add   a    to FIRST(X).
               If Y1Y2 ... Yk derives the empty string, then add ε to FIRST(X).

(2) Identifying FOLLOW(A): FOLLOW(A) is the set of terminals that can appear immediately to the right of A in some sentential form in a grammar.
Let us assume the string to be parsed is terminated by an end-of-string endmarker $. Then if A can be the rightmost symbol in some sentential form, the right endmarker $ is also in FOLLOW(A).

Algorithm to compute FOLLOW(A) for all nonterminals A of a grammar:

                           1. Place $ in FOLLOW(S) where S is the start symbol of the grammar.

                           2. If A → αBβ is a production, then add every terminal symbol a in FIRST(β) to FOLLOW(B).

                           3. If there is a production A → αB, or a production A → αBβ, where FIRST(β) contains ε,
                            then add every symbol in FOLLOW(A) to FOLLOW(B).

Consider the grammar:

                           E -> T E’

   E’ -> + T E’ | ε

                           T -> F T’

                           T’ -> * F T’ | ε

                           F -> ( E ) | id | num

Step1: Find their FIRST and FOLLOW sets:

First Follow E->TE {id, ,num( } { $,)} E' -> +TE’ | E { +, { } { $,)} T->FT {id, num,( } { +, $, ) } T'->* FT' € {*, ε} {+,$,)} F->(E) | id num {id, num,( } {*, +, $, ) }

Now create a parsing table with rows are non-terminals and the columns are terminals, as shown below:

* id num ) $ E E-> TE E-> TE' E-> TE' E' E' -> TE' E' -> E E' -> E T T-> FT T-> FT T-> FT T' T'-> T'-> *FT T-> E T-> E F F->id F->id F-> (E)

Thank you.