Question

4. (4 marks) Use left-factoring and/or eliminate left-recursion to transform each of the below eight grammars into a form where the immediate problems preventing the use of recursivedescent parsing have been removed. As usual capital letters denote variables and lower case letters are terminals.

(a) S⟶Scb∣ daa ∣Sad∣ε
(b) S⟶dcSb∣bcaSa∣bcda∣caa
(c) S⟶Sa∣Sbc∣cc∣ε
(d) S⟶dbcSd∣dbddS∣cdabS∣cdbb∣cd
(e) S⟶ccdSa∣ccaSb∣ccbSa∣abc
(f) S⟶SB∣ε
B⟶Bb∣a
(g) S⟶Sba∣Sbcd∣ε
(h) S⟶Sdb∣Sdc∣a∣c
Hint for (g) and (h) : Here after elimination of left recursion you need to use also leftfactoring (or vice versa).

Answer 1

To transform the given grammars into a form suitable for recursive-descent parsing, we need to remove left-recursion and apply left-factoring.

Step-by-step explanation:

Recursive-descent parsing is one of the simplest parsing techniques that is used in practice. Recursive-descent parsers are also called top-down parsers, since they construct the parse tree top down (rather than bottom up).

To transform the given grammars into a form suitable for recursive-descent parsing, we need to remove left-recursion and apply left-factoring.

Here are the transformations for each grammar:

(a) S ⟶ cbS' | daaS' | ε
S' ⟶ adS' | ε

(b) S ⟶ dS'b | bcaSa' | bcdS'' | caa
S' ⟶ cS'b | cdS'' | ε
S'' ⟶ aSa'' | ε

(c) S ⟶ bcS' | c
S' ⟶ aS' | ε

(d) S ⟶ dbS'' | cdaS' | cdb | cd
S' ⟶ bddS' | ε
S'' ⟶ cS'' | ε

(e) S ⟶ aSbSa' | ccbSa' | ε
S' ⟶ bS'' | cSa' | ε
S'' ⟶ cS'' | a

(f) S ⟶ B | ε
B ⟶ Ba' | a
a' ⟶ a'

(g) S ⟶ bS' | bcdS' | ε
S' ⟶ aS' | ε

(h) S ⟶ dbS' | dcS' | a | c
S' ⟶ bS' | cS' | ε