Rechtsreduktion
Zur Navigation springen
Zur Suche springen
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
auch von einer Rechtsreduktion, bei der nach der Regel reduziert wurde.
- repräsentiert den Parse-Stack unterhalb des Handles.
- ist das Handle.
- ist der noch nicht abgearbeitete Teil der Eingabe.