Rechtsreduktion

Vorlage:Belege fehlen Rechtsreduktion ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine umgedrehte Rechtsableitung.

Beim Bottom-Up-Parsing werden keine Ableitungen vom Startsymbol der Grammatik aus zur Eingabe berechnet, sondern Reduktionen von der Eingabe zum Startsymbol. Im Zusammenhang mit LR(k)-Parsing spricht man deshalb bei einer umgedrehten Rechtsableitung

$\alpha \beta w{\Leftarrow }_r\alpha Aw$

auch von einer Rechtsreduktion, bei der nach der Regel

$A\to \beta$

reduziert wurde.

• $\alpha$ repräsentiert den Parse-Stack unterhalb des Handles.
• $\beta$ ist das Handle.
• $w$ ist der noch nicht abgearbeitete Teil der Eingabe.