I i II Reguła gramatyczna nie pozwalają na stosowanie definicji lewostronnie rekurencyjnych. Aby rozwiązać ten problem należy zamienić rekurencję lewostronną na prawostronną.
Reguła 1:
Dla zadanej gramatyki:
A:: = ζ1 | ζ2 | … | ζn
zbiory pierwszych symboli w zdaniach, które mogą być wyprowadzone z ζi muszą być rozłączne, tzn.
pierw(ζi) ∩ pierw(ζj) = ∅ dla wszystkich i ≠ j
Zbiór pierw (ζ) jest zbiorem wszystkich symboli końcowych, które mogą wystąpić na pierwszej pozycji w zdaniach wyprowadzonych z ζ. Zbiór ten może być wyznaczony według następujących reguł:
1. Jeśli pierwszy symbol argumentu jest symbolem końcowym, to
pierw(αζ) = {a}
2. Jeśli pierwszy symbol jest symbolem pomocniczym i istnieje produkcja
A::= α1| α2 | … | αn
to
pierw(Aζ)=pierw(α1) ∪ pierw(α2) ∪… ∪ pierw(αn)
W przykładzie 3 x ∈ pierw(A) i x ∈ pierw(B), w związku z tym pierwsza produkcja nie spełnia reguły I. Należy dokonać korekty składni dla języka z przykładu 3 aby była spełniona reguła I, polega to na wyłączeniu części wspólnej “przed nawias”.
Poniższa gramatyka jest równoważna gramatyce z przykładu 3, ponieważ generuje ten sam zbiór zadań:
S :: = C | xS
C :: = y | z
W ogólnym przypadku dla produkcji postaci:
A:: = αζ1 | αζ2 | ... | αζn
stosuje się lewostronną faktoryzację (wyciągnięcie czynnika przed nawias). Produkcję (1) zastępuje się produkcjami (2):
A :: = αA’
A’ :: = ζ1 | ζ2 | ... | ζn
Example :
Dana jest gramatyka:
S :: = Ax
A :: = x | ε
gdzie: ε - pusty ciąg symboli.
S | x
Ax | x
xx | x
x | -
Stosując produkcję A :: = x zamiast A :: = e. Pojawia się problem pustego symbolu, który występuje wtedy gdy z symbolu pomocniczego istnieje możliwość wyprowadzenia pustego ciągu symboli. W celu eliminacji takiej sytuacji stosuje się II regułę gramatyczną.
Reguła 2:
Dla każdego symbolu A ∈ N, z którego można wyprowadzić pusty ciąg symboli (A →* e), zbiór jego pierwszych symboli musi być rozłączny ze zbiorem symboli, które mogą następować po dowolnym ciągu wyprowadzonym z A, tzn.
pierw(A) ∩ nast(A) = ∅
Zbiór nast(A) wyznacza się następująco: dla każdej produkcji Pi postaci:
X::=ζΑη
przez Si oznaczamy pierw(ηi); suma wszystkich zbiorów Si tworzy zbiór nast(A). Jeśli z co najmniej jednego ηi możemy wyprowadzić pusty ciąg symboli, to zbiór nast(X) musi być również włączony do nast(A). W przykładzie 4 reguła 2 nie jest spełniona dla symbolu A, ponieważ:
pierw(A) = nast(A) = {x}
Jeżeli wielokrotnie się powtarza pewien wzorzec symboli to wyrażamy go za pomocą rekurencyjnej definicji konstrukcji zdaniowej.
Na przykład produkcja:
A :: = B | AB
Opisuje ciąg zbiorów B, BB, BBB, .... Jej użyciezgodnie z regułą 1 jest niedozwolone ponieważ:
pierw(B) ∩ pierw(AB) = pierw (B) ≠ ∅
Natomiast produkcja postaci:
A:: = ε | AB
Która generuje zdania ε, B, BB, BBB, .... nie spełnia reguły 2, ponieważ
pierw(A) = pierw(B)
a zatem:
pierw(A) ∩ nast(A) = pierw (B) ≠ ∅
W obu omawianych produkcjach występuje lewostronna rekurencja.