Rechtsreduktion

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

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

${\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.