I i II Reguła gramatyczna nie pozwalają na stosowanie definicji lewostronnie rekurencyjnych. Problem ten można rozwiązać poprzez:
1. zamianę rekurencji lewostronnej na prawostronną
A :: = ε| BA
2. zastąpienie rekursji iteracją.
Zapis {B} w notacji EBNF oznacza iterację czyli powtórzenie symbolu B 0,1,2, ... lub nieskończenie wiele razy. Produkcja:
A :: = {B}
opisuje zbiór ciągów: ε, B, BB, BBB, ...
W celu eliminacji lewostronnej rekurencji stosowane są wzory (1,2).
Z produkcji (3)
A :: = Aα1 | Aα2 | … | Aαn | β1 | β2 | … | βm
Można zastąpić dwoma równoważnymi jej produkcjami
A:: = β1A’ | β2A’ | … | βmA’
A’:: = α1A’ | α2A’ | … | αnA’ | ε
Przykład :
Przykład analizy gramatyki z eliminacją lewostronnej rekurencji i lewostroną faktoryzacją.
Dana jest gramatyka:
S::= -A | -a
A::= B | A * B
B::= C |B +C | b
C::= c | d
1. Wyznaczamy symbole pomocnicze N={A,B,C,D} i końcowe T={a,*,+,b,c,d}.
2.Zbiory symboli pierwszych i następnych dla każdego symbol pomocniczego.
pierw(S)={-}
pierw(A)=pierw(B)=pierw(C) ∪ {b}={c,d,b}
pierw(B)=pierw(C) ∪ {b}={c,d,b}
pierw(C)={c,d}
nast(S)= ∅
nast(A)=nast(S) ∪ {*}={*}
nast(B)=nast(A) ∪ {+}={*,+}
nast(C)=nast(B)={*,+}
Sprawdzamy czy dane produkcje z tej gramatyki spełniają I I II regułę gramatyczną. II reguła jest spełniona ponieważ żadna produkcja nie generuje pustego ciągu symboli.
Sprawdzamy I Regułę:
Dla produkcji S:
{-} ∩{-}≠ ∅ I Reguła nie jest spełniona!
Dla produkcji A:
pierw(B) ∩ pierw(A)≠∅ I Reguła nie jest spełniona!
Dla produkcji B
pierw(C) ∩ pierw(B)≠∅
pierw(C) ∩ {b}≠∅ I Reguła nie jest spełniona!
pierw(B) ∩ {b}≠∅
Dla produkcji C:
{c} ∩ {d}=∅ I Reguła jest spełniona!
W przypadku produkcji S należy zastosować lewostronną faktoryzację.
Natomiast dla produkcji B i C należy wyeliminować lewostronną rekurencję.
Poprawiona Gramatyka:
S::= -S`
S`::=A |a
A::=BA`
A`::=*BA` | ε
B::=CB` | bB`
B`::=+CB` | ε
C:: c | d
4.Wyznaczamy zbiory symboli pierwszych i następnych dla każdego symbolu pomocniczego dla gramatyki poprawionej:
pierw(S)={-}
pierw(S`)=pierw(A) ∪ { a}={c,d,b,a}
pierw(A)=pierw(B)={c,d,b}
pierw(A`)={*,ε}
pierw(B)=pierw(C) ∪ {b}={c,d,b}
pierw(B`)={+,ε}
pierw(C)={c,d}
nast(S)= ∅
nast(S`)=nast(S)= ∅
nast(A)=nast(S`)=∅
nast(A`)=nast(A)= ∅
nast(B)=pierw(A`)-ε={*}
nast(B`)=nast(B)={*}
nast(C)=pierw(B`)-ε={+}
Teraz należy sprawdzać czy poprawiona gramatyka spełnia I i II regułę gramatyczną:
Dla produkcji S i S`:
pierw (A) ∩ a= ∅ I Regułą jest spełniona!
Dla produkcji A:
pierw(B) ∩ ε=∅ I Regułą jest spełniona!
Dla produkcji A`:
{*} ∩ ε=∅ I Regułą jest spełniona!
Dla produkcji B:
pierw(C) ∩ {b}=∅ I Regułą jest spełniona!
Dla produkcji C reguła I była już spełniona, produkcja ta nie była zmieniana.
Dla wszystkich produkcji oprócz A` i B` II reguła jest spełniona ponieważ nie generują one pustego ciągu symboli. W takim przypadku należy jeszcze sprawdzić II regułę dla produkcji A` i B`.
Dla produkcji A`:
pierw (A`)∩ nast(A`)={*,ε} ∩ {∅}=∅ II Reguła jest spełniona!
Dla produkcji B`:
pierw(B`)∩ nast(B`)={+,ε} ∩ {*}=∅ II Reguła jest spełniona!
Zastosowanie lewostronnej faktoryzacji i eliminacja lewostronnej rekurencji umożliwiło poprawienie gramatyki, która spełnia teraz I i II regułę gramatyczną.