Grammatical rules 1 & 2 forbid the usage of left recursion. To solve
this problem, left recursion has to be exchanged for right recursion.
Rule 1:
For the given grammar:
A:: = ζ1 | ζ2 | … | ζn
first(ζi) ∩ first(ζj) = ∅ for each i ≠ j
First (ζ) is a set of all the terminal symbols, which can occur at the
first position in the sentences derived from ζ. This set can be determined
from the following rules:
1. If the first symbol of the argument is a terminal symbol then
first(αζ) = {a}
2. If the first symbol is a non-terminal and the production exists
A::= α1| α2 | … | αn
then
first(Aζ)=first(α1) ∪ first(α2) ∪… ∪ first(αn)
In example 3 x ∈ first(A) i x ∈ first(B), therefore the first production
does not fulfill rule 1. To fulfill rule 1, syntax revision for the language
from example 3 has to be performed it is done by extracting the common
part “from brackets.” The below grammar is equal to the grammar from example
3 because it generates the same set of sentences:
S :: = C | xS
C :: = y | z
Generally, for a production of a form
A:: = αζ1 | αζ2 | ... | αζn
Left-factoring is applied (extracting the factor from brackets). Production (1) is rewritten as productions (2):
A :: = αA’
A’ :: = ζ1 | ζ2 | ... | ζn
Example :
Given a grammar:
S :: = Ax
A :: = x | ε
where: ε - empty sequence of symbols
S | x
Ax | x
xx | x
x | -
Using the production A :: = x instead of A :: = ε. The problem of empty
symbol arises, that occurs when there is a possibility to derive an empty
sequence of symbols from a non-terminal symbol. To avoid such a situation,
the grammatical rule 2 is applied.
Rule 2:
For the each symbol A ∈ N, from which an empty symbol can be derived (A
→* ε), a set of its FIRST symbols must be separated from the set of
symbols, which can follow any sequence derived from A, i.e.
first(A) ∩ follow(A) = ∅
A set follow(A)is determined as follows for each production Pi of a form:
X::=ζΑη
Si means first(ηi); and a set follow(A) is a sum of all sets . If only an empty symbol can be derived from one hi then a set follow(X) must be included into follow(A) also:
first(A) = follow(A) = {x}
If the same pattern of symbols is repeated several times, it is expressed
by means of recursive definition of sentence construction.
Production
A :: = B | AB
generates sentences: B, BB, BBB, …
first(B) ∩ first(AB) = first (B) ≠ ∅
While production:
A:: = ε | AB
generates sentences ε, B, BB, BBB, .... According to rule 1, their usage is forbidden, because:
first(A) = first(B)
and therefore:
first(A) ∩ follow(A) = first (B) ≠ ∅
In both considered productions, left recursion occurs.