According to 1 & 2 grammatical rules, the usage of left recursion
is forbidden in LL grammars. Problem solutions:
1. exchange of left recursion into right recursion
A :: = ε| BA
In EBNF notation, description {B} means iteration i.e. repetition of B
symbol zero, one, two, ... or infinite number of times. Production:
A :: = {B}
generates sentences: ε, B, BB, BBB, ...
To remove left-recursion, the formulae (1,2) are used.
Production (3)
A :: = Aα1 | Aα2 | … | Aαn | β1 | β2 | … | βm
It can be exchanged for two productions equal to it.
A:: = β1A’ | β2A’ | … | βmA’
A’:: = α1A’ | α2A’ | … | αnA’ | ε
Example :
An example of analysis of grammar with left recursion removal and left-factoring.
Given a grammar:
S::= -A | -a
A::= B | A * B
B::= C |B +C | b
C::= c | d
1. Finding non-terminal symbols N={A,B,C,D} and end T={a,*,+,b,c,d}.
2.Sets of first and follow symbols for each non-terminal symbol.
first(S)={-}
first(A)=first(B)=first(C) ∪ {b}={c,d,b}
first(B)=first(C) ∪ {b}={c,d,b}
first(C)={c,d}
follow(S)= ∅
follow(A)=follow(S) ∪ {*}={*}
follow(B)=follow(A) ∪ {+}={*,+}
follow(C)=follow(B)={*,+}
Checking if given productions from this grammar fulfill grammatical rules
1 and 2. Rule 2 is fulfilled because no production generates an empty sequence
of symbols.
Checking Rule 1:
For production S:
{-} ∩{-}≠ ∅ Rule 1 is not fulfilled!
For production A:
first(B) ∩(A)≠ ∅ Rule 1 is not fulfilled!
For production B:
first(C) ∩ first(B)≠ ∅
first(C) ∩{b}≠ ∅ Rule 1 is not fulfilled!
first(B) ∩{b}≠ ∅
For production C:
{c}∩ {d}=∅Rule 1 is fulfilled!
In the case of production S, left-factoring should be applied. For productions
B and C, left recursion should be removed.
Revised Grammar:
S::= -S`
S`::=A |a
A::=BA`
A`::=*BA` | ε
B::=CB` | bB`
B`::=+CB` | ε
C:: c | d
4. Finding sets of first and follow symbols for each non-terminal symbol of the revised grammar:
first(S)={-}
first(S`)=first(A) ∪ { a}={c,d,b,a}
first(A)=first(B)={c,d,b}
first(A`)={*,ε}
first(B)=first(C) ∪ {b}={c,d,b}
first(B`)={+,ε}
first(C)={c,d}
follow(S)= ∅
follow(S`)=follow(S)= ∅
follow(A)=follow(S`)=∅
follow(A`)=follow(A)= ∅
follow(B)=first(A`)-ε={*}
follow(B`)=follow(B)={*}
follow(C)=first(B`)-ε={+}
Then, checking if the revised grammar fulfills the grammatical rules 1
and 2:
For production S i S`:
first (A) ∩ a= ∅ Rule 1 is fulfilled!
For production A:
first(B) ∩ ε = ∅ Rule 1 is fulfilled!
For production A`:
{*}∩ ε = ∅ Rule 1 is fulfilled!
For production B:
first(C) ∩ {b} = ∅ Rule 1 is fulfilled!
For production C, rule 1 was already fulfilled, this production was not
changed.
For all productions except for A` and B`, rule 2 is fulfilled because
they do not generate an empty sequence of symbols. In such a case, rule
2 has to be checked for productions A` i B`.
For production A`:
first (A`)∩ follow(A`)={*,ε}∩{∅}=∅ Rule II is fulfilled!
For production B`:
first(B`) ∩ follow(B`) = {+,ε} ∩ (*) = ∅ Rule II is fulfilled!
The application of left-factoring and left recursion removal allowed to revise the grammar that now fulfills grammatical rules 1 and 2.