Rechtsreduktion

Rechtsreduktion i​st ein Begriff a​us der Theoretischen Informatik u​nd bezeichnet e​ine 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

${\displaystyle \alpha \beta w\Leftarrow _{r}\alpha Aw}$

auch von einer Rechtsreduktion, bei der nach der Regel ${\displaystyle A\rightarrow \beta }$ reduziert wurde.

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