Pok-10-wyk-Slajd23
Zmienne globalne(18)
Na stos przesuwana jest kolejna liczba (3) z wejścia. Zmienna x przyjmuje wartość 3.
Ta wersja analizatora składniowego (z prawostronną rekurencją) osiągnęła teraz maksymalną zajętość stosu dla przykładowego wejścia – 5 komórek.
Warto zauważyć, że zajętość stosu przy prawostronnej rekurencji jest większa i liniowo zależna od liczby liczb na wejściu (w analizatorze opartym o lewostronną rekurencję maksymalna zajętość stosu była stała i nie zależała od rozmiaru wejścia).
Na przykład dla 100 liczb na wejściu zajętość stosu wzrosłaby do 199 symboli – (100 liczb + 99 znaków).
Jeżeli koniecznie chcemy użyć prawostronnej rekurencji i zredukować zajętość stosu można modyfikować gramatykę, na przykład w następujący sposób:
Zastąpić w produkcji E ? n ‘+’ E dwie jednostki leksykalne pomocniczym nieterminalem o nazwie np. Nplus co pozwoli LR-parserowi wykonać redukcję po każdym przesunięciu znaku dodawania i zaoszczędzić prawie połowę stosu.
Zmodyfikowany fragment gramatyki będzie miał wówczas następującą postać:
Nplus –> n ‘+’
E : Nplus E
| n
