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ą $A\rightarrow \alpha$ 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ę $S\rightarrow d,\ S\rightarrow Ad,\ A\rightarrow d$ i słowo dd:

Stos	Wejście	Akcja	Błędna akcja
$	dd#	przesunięcie
$d	d#	redukcja $A\rightarrow d$	przesunięcie
$A	d#	przesunięcie
$Ad	#	redukcja $S\rightarrow Ad$	redukcja $A\rightarrow d$
$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.brak strony w książce
• Dick Grune, Ceriel Jacobs: Parsing Techiniques – A Practical Guide. Chichester, England: Ellis Horwood, 1990. ISBN 0-13-651431-6.brak strony w książce