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

\begin{slide}{Keller-Automaten}

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

im Prinzip wie endlicher Automat,
aber als Arbeitsspeicher nicht nur Zustand,
sondern auch Keller (Band).

\begin{verbatim}
data Konfiguration x y z =
     Konfiguration { eingabe :: [ x ]
                   , zustand :: z
                   , keller  :: [ y ]
                   }
\end{verbatim}

Ein Arbeitsschritt ist abhängig 
vom obersten Kellersymbol $y$   und Zustand $z$
und besteht aus:
\begin{itemize}\itemsep 0pt \parskip 2pt
\item Zeichen $x$ lesen oder $\epsilon$ lesen
\item neuen Zustand annehmen und
\item oberstes Kellersymbol ersetzen
\end{itemize}

\end{slide}

\begin{slide}{Keller-Automaten (II)}

\begin{verbatim}
data NPDA x y z =
  NPDA { eingabealphabet  :: Set x
       , kelleralphabet   :: Set y
       , zustandsmenge    :: Set z
       , startzustand     :: z
       , startsymbol      :: y
       , akzeptiert       :: Modus z
       , transitionen     :: 
     FiniteMap (Maybe x, z, y) (Set (z, [y]))
       }

data Modus z =
  Leerer_Keller | Zustand ( Set z )
\end{verbatim}


\end{slide}

