Examples: Top Down Parsing | Compiler Design - Computer Science Engineering (CSE) PDF Download

Example 2:
Construct a predictive parsing table for the given grammar or Check whether the given grammar is LL(1) or not.
S → iEtSS^I | a
S^I → eS | ∈
E → b
 

Solution: 1. Computation of First () set:

1. First (E) = first (b) = {b}

2. First (SI) = first (eS) È ∪ first (e) = {e, e}

3. first (S) = first (iEtSSI) È∪ first (a) = {i, a}

2. Computation of follow() set:

1. follow (S) = {$} È∪ first (SI)  {e} È ∪ follow (S) È ∪ follow (SI) = {$} È {e} = {e, $}

2. follow (SI) = follow  ∪ (S) = {e, $}

3. follow (E) = first (tSSI) = {t} 
 

3. The parsing table for this grammar is:
 

As the table multiply defined entry. The given grammar is not LL(1). 
 

Example 3:
Construct the FIRST and FOLLOW and predictive parse table for the grammar:
S→ AC$
C → c | Î A → aBCd | BQ | Î B → bB | d Q → q

Solution:
1. Finding the first () sets:
First (Q) = {q}
First (B) = {b, d} 
First (C) = {c, e}
First (A) = First (aBCd) È First (BQ) È First (e)
= {a} È First (B) È First (d) È{e}
= {a} È First (bB) È First (d) È {e}
= {a} È {b} È {d} È {e}
= {a, b, d, e} First (S) = First (AC$)
= (First (A)  {e}) È (First (C)  {e}) È First (e)
= ({a, b, d, e}  {e}) È ({c, e}  {e}) È {e}
= {a, b, d, c, e} 

2. Finding Follow () sets: Follow (S) = {#}
Follow (A) = (First (C) – {e}) È First ($) = ({c, e}  {e}) È {$}
Follow (A) = {c, $} Follow (B) = (First (C)  {e}) È First (d) È First (Q)
= {c} È {d} È {q} = {c, d, q} Follow (C) = (First ($) È First (d) = {d, $}
Follow (Q) = (First (A) = {c, $}

3. The parsing table for this grammar is: 
 

4. Moves made by predictive parser on the input abdcdc$ is: