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

\begin{slide}{Top-Down/Bottom-Up}

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

\begin{itemize}
\item
Parsen durch rekursiver Abstieg ist top-down-Methode,

erzeugt Links-Ableitung.
\item
Operator-Präzedenz-Parsen ist bottom-up-Methode,

erzeugt Rechts-Ableitung. 
\item
Beide Methoden lesen die Eingabe \emph{von links}!
\item
Beide Methoden benutzen \emph{Vorschau-Zeichen}
(üblich: eines)

\end{itemize}


\end{slide}

\begin{slide}{Top-Down/Bottom-Up und Eindeutigkeit}

\begin{itemize} \itemsep 1pt
\item
Für effizientes Parsen möchte man kein Backtracking,
also \emph{Eindeutigkeit} (der Auswahl der anzuwendenden Regel,
abhängig von den Vorschau-Zeichen)
\item
Das ist bei Top-Down(LL)-Parsern eine starke Einschränkung,
aber bei Bottom-Up(LR)-Parsern nicht so gravierend:
\item
diese können Entscheidungen \glqq in die Zukunft\grqq verschieben,
indem Zwischenergebnisse auf dem Stack gespeichert werden.
\item
für Konstruktion von LR-Parsern benötigt man Werkzeuge,
das das benutzte Kelleralphabet sehr groß ist.
\end{itemize}

\end{slide}
