Algorithm for construction of predictive parsing table (MCA 4)

---

Algorithm for construction of predictive parsing table:

 

 

Input : Grammar G

 

Output : Parsing table M

 

Method :

 

1. For each production A → α of the grammar, do steps 2 and 3.

 

1. For each terminal a in FIRST(α), add A → α to M[A, a].

 

1. If ε is in FIRST(α), add A → α to M[A, b] for each terminal b in FOLLOW(A). If ε is in FIRST(α) and $ is in FOLLOW(A) , add A → α to M[A, $].

 

1. Make each undefined entry of M be error.

 

Example:

 

Consider the following grammar :

 

E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | id

 

---

---