Metoda przesunięcie-redukcja
Z Wikipedii
Metoda przesunięcie-redukcja - ogólna metoda wstępującej analizy składniowej. Drzewo wyprowadzenia budowane jest od dołu, zaczynając od liści, a na korzeniu kończąc. Parser posiada stos, na którym przechowuje symbole gramatyki (terminalne i nieterminalne) oraz bufor wejściowy zawierający nieprzeczytaną część ciągu wejściowego. Podczas działania parser czyta kolejne symbole z wejścia i wkłada je na stos, aż do momentu, gdy uzna, że może wykonać redukcje ciągu symboli z wierzchołka stosu α zgodnie z pewną produkcją 
należącą do gramatyki. Wtedy ciąg α na stosie zastępowany jest pojedynczym symbolem A. Praca ta jest kontynuowa do momentu gdy wejście będzie puste, a na stosie będzie tylko symbol startowy, lub do wykrycia błędu. Problem polega na tym, żeby redukcja nastąpiła w odpowiednim momencie i była przeprowadzona zgodnie z dobrą produkcją. Jeśli uchwyt (prawa strona produkcji, znajdująca się na stosie, którą można zredukować do lewej strony produkcji), nie zostanie w porę wykryty i nastąpi przesunięcie, zostanie on pogrzebany na stosie i nie będzie mógł być poprawnie zredukowany (redukcje przeprowadzane są tylko na wierzchołku stosu). Jeśli nastąpi przedwczesna redukcja, to symbole które dopiero trafią na stos mogą nie pasować do żadnej produkcji.
[edytuj] Przykład
Weźmy gramatykę 
i słowo dd:
| Stos | Wejście | Akcja | Błędna akcja |
|---|---|---|---|
| $ | dd# | przesunięcie | |
| $d | d# | redukcja  |
przesunięcie |
| $A | d# | przesunięcie | |
| $Ad | # | redukcja  |
redukcja |
| $S | # | Akceptacja |
Przesunięcie w drugim wierszu, prowadziłoby do powstania na stosie ciągu $dd, który mógłby być zredukowany do $dA i na tym koniec - pierwszego d nie dałoby się już zredukować. Podobnie redukcja d na A z czwartego wiersza prowadziłaby do stosu $AA, z którym również nie można nic więcej zrobić.
[edytuj] Dalszy podział
Istnieją różne sposoby podejmowania decyzji o kolejnej akcji. W zależności od użytych metod, powstają np.:
- parsery LR, a w tym:
- parsery BC
- parsery działające metodą pierwszeństwa operatorów
Parsery te zazwyczaj czytają wejście od lewej do prawej, choć mogą istnieć też czytające od prawej do lewej.
[edytuj] Bibliografia
- Alfred V. Aho, Ravi Sethi, Ullman imię3=Jeffrey D.: Kompilatory : reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1.
- Dick Grune, Ceriel Jacobs: Parsing Techiniques - A Practical Guide. Chichester, England: Ellis Horwood, 1990. ISBN 0136514316.
