%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Shift und Reduce}

\kopf{$ $Id: shiftreduce.tex,v 1.1 2011-10-16 14:06:17 waldmann Exp $ $}

\emph{LR-Parser}: deterministischer endlicher Automat mit Keller.

\emph{Kellerinhalt}: $s_0 X_1 s_1 X_2 \ldots X_m s_m$

(abwechselnd Zustand und Zeichen)

\emph{Konfiguration}: (Kellerinhalt, Rest der Eingabe $a_i a_{i+1} \ldots a_n$)

repräsentiert (rechts-)abgeleitete Satzform 
\[ X_1 X_2 \ldots X_m a_i a_{i+1} \ldots a_n \] 

 $\text{action}(s_m, a_i)$ kann sein:
\begin{itemize}
\item shift $s$: 
  zu $(\ldots  X_m s_m a_i s,  a_{i+1} \ldots)$
\item reduce $A \to b$:
  zu $(\ldots X_{m-r} s_{m-r} A s, a_i a_{i+1} \ldots)$,

  wobei $|b|=r$ und $s=\text{jump}(s_m, a_i)$.
\end{itemize}

\end{slide}
