Q2Compiler Design
Question
4 marks
Describe the construction of Predictive Parsing Table.
Answer
The Predictive Parsing Table M[A,a] is constructed using FIRST and FOLLOW sets; entry M[A,a] specifies which production to use when the current non-terminal is A and the lookahead is a.
- Step 1: Eliminate left recursion from the grammar (if any).
- Step 2: Apply left factoring (if needed) to ensure each non-terminal's alternatives begin with distinct terminals.
- Step 3: Compute FIRST sets for all grammar symbols and strings.
- Step 4: Compute FOLLOW sets for all non-terminals.
- Step 5: For each production A → α: (a) For each terminal a ∈ FIRST(α), add A → α to M[A, a]. (b) If ε ∈ FIRST(α), then for each terminal b ∈ FOLLOW(A), add A → α to M[A, b]; if ].
- Step 6: All undefined entries are error entries.
- Step 7: If any entry has multiple productions, the grammar is not LL(1).
Example for E' → +TE' | ε: FIRST(+TE') = {+}, so M[E', +] = E'→+TE'. Since ε ∈ FIRST(E'→ε) and FOLLOW(E') = {), $}, we add M[E', )] = E'→ε and M[E', $] = E'→ε. This table is then used by the LL(1) parser to make deterministic parsing decisions.