Rechtsreduktion

Vorlage:Hinweisbaustein 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

<math>\alpha \beta w \Leftarrow_r \alpha A w</math>

auch von einer Rechtsreduktion, bei der nach der Regel <math>A \rightarrow \beta</math> reduziert wurde.

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