DHARM314 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
A 3 → A 3 A 1 A 3 A 2
and further A 2 is replaced through b[∴ A 2 → b] so A 3 → A 2 A 3 A 2 becomes
A 3 → bA 3 A 2
Since, (–) A 3 → A 2 A 3 A 2
(+) A 3 → A 3 A 1 A 3 A 2 and
(+) A 3 → bA 3 A 2
thus grammar has following ILR productions
A 3 → A 3 A 1 A 3 A 2 | bA 3 A 2 | aA 2 | c [ILR non-terminal is A 3 ]
with other productions
A 1 → A 2 A 3 | a
A 2 → A 3 A 1 | b
Step 3
l remove ILR productions i.e.
A 3 → A 3 A 1 A 3 A 2 | bA 3 A 2 | aA 2 | c
[By assuming that A 1 A 3 A 2 is α; bA 3 A 2 is β 1 ; aA 2 is β 2 ; c is β 3 ; so clear ILR production are
A 3 → A 3 α | β 1 | β 2 | β 3
which are connected on A 3 → β 1 | β 2 | β 3 | β 1 C | β 2 C| β 3 C and C → α | α C where C is a new
non terminal
Substitute the values we get
(–) A 3 → A 3 A 1 A 3 A 2 | bA 3 A 2 | aA 2 | c
(+) A 3 → bA 3 A 2 | aA 2 | c | bA 3 A 2 C | aA 2 C | c C
and (+) C → A 1 A 3 A 2 | A 1 A 3 A 2 C
(So, we find GNF productions derived from A 3 )
Now the grammar has following GNF productions
A 3 → bA 3 A 2 | aA 2 | c | bA 3 A 2 C | aA 2 C | c C and
remaining non GNF productions
A 1 → A 2 A 3 | a
A 2 → A 3 A 1 | b
l Modify non GNF productions to GNF where A 3 (ILR non terminal) is left most on
right side (A 2 → A 3 A 1 | b) by substituting GNF derived symbols
A 2 → bA 3 A 2 A 1 | aA 2 A 1 | c A 1 | bA 3 A 2 C A 1 | aA 2 C A 1 | c C A 1 | b
l Now A 2 derived GNF productions so non GNF production A 1 → A 2 A 3 | a is modified
to GNF through replacing A 2 by GNF derived symbols as
A 1 → bA 3 A 2 A 1 A 3 | aA 2 A 1 A 3 | c A 1 A 3 | bA 3 A 2 C A 1 A 3 | aA 2 C A 1 A 3
| c C A 1 A 3 | bA 3 | a
l Since, A 1 derived GNF productions so remaining non GNF productions where A 1 is in
the left most on right side (C → A 1 A 3 A 2 | A 1 A 3 A 2 C) are modified to GNF through
replacing A 1 by GNF derived symbols as
C → bA 3 A 2 A 1 A 3 A 3 A 2 | aA 2 A 1 A 3 A 3 A 2 | cA 1 A 3 A 3 A 2 | bA 3 A 2 CA 1 A 3 A 3 A 2 | aA 2
CA 1 A 3 A 3 A 2 | cCA 1 A 3 A 3 A 2 | bA 3 A 3 A 2 | aA 3 A 2