\begin{slide}{LR-Parsing}

Invariante: 

verbrauchte Eingabe ist aus  Spiegelbild des Kellers ableitbar

Aktionen im Keller:
\begin{itemize}
\item
  \emph{shift}: Eingabezeichen $\to$ push
\item
  (eventuell vorher)

  \emph{reduce} (mit Regel $T\to w$):

  Anfangsstück $w$ des Kellers durch $T$ ersetzen
\end{itemize}

\end{slide}


\begin{slide}{LR-Items}

\begin{itemize}
\item
  benutze größeres Kelleralphabet,
  damit man bereits am top-of-stack erkennt,
  welche Regeln anwendbar sind.
\item 
  ein solches Kellerzeichen ist eine Menge von Items,
\item 
  ein Item hat die Form $(T \to u\cdot v)$

  mit der Bedeutung: $u$ haben wir schon gesehen;
  wenn noch $v$ kommt, dann können wir alles durch $T$ ersetzen.
\item
  Items mit möglichen Übergängen bilden endlichen Automaten.

  (groß $\Rightarrow$ Werkzeuge)
\end{itemize}

\end{slide}

\begin{slide}{$LR(k)$-Grammatiken}

Für $k\in \NN$:

$LR(k)$ ist die Menge aller CFG $G$,
bei denen im angegebenen Automaten 
durch Vorausschau um $k$ Zeichen
die auszuführende Regel (reduce) eindeutig bestimmt ist.

\bigskip

Definition:

Für alle Paare von Rechtsableitungen
\begin{eqnarray*}
S \to_R^* u T v \to_R  u w v  \\
S \to_R^* u' T' v' \to_R  u w v' ,
\end{eqnarray*}
bei denen $v$ und $v'$ bis zur Länge $k$ übereinstimmen, \\
gilt $u = u', T=T',v=v'$

\end{slide}

