Metoda przesunięcie-redukcja
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. Analizator składniowy (parser) posiada stos, na którym przechowuje terminalne i nieterminalne symbole gramatyki formalnej 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 kontynuowana 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.
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ć.
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:
- SLR
- LALR
- kanoniczny LR
- parsery działające metodą ograniczonego kontekstu (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.
Bibliografia
- Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: 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 0-13-651431-6.