Shift und Reduce

Id: shiftreduce.tex,v 1.3 2005/11/17 08:14:31 waldmann Exp

LR-Parser: deterministischer endlicher Automat mit Keller, konstruiert von links eine Rechts-Ableitung.

Kellerinhalt: X₁X₂...X_m (jedes X_i ist Terminal oder Variable)

Konfiguration: (Kellerinhalt, Rest der Eingabe a_ia_i+1...a_n)

repräsentiert (rechts-)abgeleitete Satzform

X₁X₂...X_m a_ia_i+1...a_n

Parser-Aktionen sind:

• shift: zu (...X_ma_i, a_i+1...)
• reduce: falls Regel (A$\to$X_m-r+1...X_m) $\in$ G:

  zu (...X_m-rA, a_ia_i+1...), wobei r = | w|