DHARM312 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
(–) A → A a | b
(+) A → b | b A′
(+) A′ → a | a A′
Or, in general
(–) A → A a 1 | A a 2 | A a 3 |......| A an | b 1 | b 2 | b 3 |......| bn
then (+) A → b 1 | b 2 | b 3 |......| bn | b1 A’ | b2 A’| b3 A’| ..........| bn A’
and (+) A′ → a 1 | a 2 | a 3 |......| an | a 1 A′| a 2 A′| a 3 A′ |......| an A′
So, we get the productions free from ILR.
Algorithm to convert the given grammar to GNF
Step 1. Simplify and convert the grammar to CNF
Step 2. Order the non terminals in the productions through substitution so that it
becomes ILR form
Step 3. + Convert ILR production into GNF production. (So we find that few produc-
tions derived from ILR non terminal† that are in GNF)
- use the GNF productions such that its derived string/s (right side) is sub-
stituted in other production/s where ILR non terminal occurs in left most
position on its right side. - By this substitution we modified non GNF productions to GNF productions.
Step 4. Repeat step 2 and 3 until we convert all productions into GNF productions.
We can remove left recursion both immediate left recursion (ILR) and non immediate
left recursion begin using following procedure,
begin for i = 1 to n do// where n is the number of ILR non terminals
{ for j = 1 to (i – 1) do
{ for every production of form Ai → Aj α do
{ for every production Aj → β do
begin
Add Ai → β α in the grammar
Remove Ai → Aj α from the grammar
end
// remove ILR from Ai
}
}
}
end
Fig. 11.24
Example 11.29. Convert the grammar into GNF
S → A A | a
A → S S | b
† ILR non terminal
If ‘A → A a’ is ILR production then symbol A is called ILR non terminal.