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

\begin{slide}{Operator-Präzedenz-Parser}

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

\begin{verbatim}
Ausdruck -> Literal | ( Ausdruck ) 
   | Ausdruck + Ausdruck
   | Ausdruck * Ausdruck | ...
\end{verbatim}

Eingabe: $A_1 o_1 A_2 o_2 A_3 o_3 A_4$

können nicht sofort ausrechnen,
Benutzen Keller für Zwischenresultate.

Entscheide zw. Push (warten) und Pop (rechnen) 
anhand der Präzedenz der Operatoren
(müssen mit gekellert werden).
\end{slide}

\begin{slide}{Operator-Grammatiken}

Def: eine CFG heißt \emph{Operator-Grammatik},
falls für jede Regel $(l \to r) \in R$ gilt:
\begin{itemize}
\item $r \neq \epsilon$
\item $r$ enthält keine direkt benachbarten Variablen
\end{itemize}

Wir benutzen \emph{Prioritäts-Relationen} $<$
auf Terminalen.

Für Wort $ c w \$  $
(mit Links- und Rechtsmarkierung):

Füge Relationen zwischen Terminalen ein
(üebrspringe dabei Variablen):
z. B. $ c < a_1 < a_2 > \ldots a_n > \$ $

Suche am weitesten links stehendes $>$,
dann das nächste davon links stehende $<$,
wende Regel auf Teilwort $< \ldots >$ an.

\end{slide}

\begin{slide}{Implementierung mit Stack}

Konstruiere Ableitungsbaum zu geg. Operator-Grammatik
mit Präzedenz

Interface Stack: \verb|push(), pop(), top|,
Interface Eingabe (Scanner): \verb|next()|
\begin{verbatim}
push ('c'); -- linke Rand-Markierung
Token n = next ();
while (('c' != top) || ('$' != n)) {
  if ( top < n ) {
    push (n); n = next ();
  } else {
    while ( top > n ) { pop (); }
  }
}
\end{verbatim}
\end{slide}


\begin{slide}{Bemerkungen}

stark vereinfacht. Es fehlen:
\begin{itemize}
\item Syntaxbaum bauen/semantisch Aktion ausführen
\item Assoziativität (Links, Rechts, keine)
\item Fehlerbehandlung
\end{itemize}  

Aufgaben (Praktikum):
\begin{itemize}
\item
  Welche Präzedenz entspricht der üblichen Arithmetik
  (Operatoren $+, -, *, /, \uparrow$)?
\item Welche Präzedenz bekommen Klammern?
\item (Kombination mit Parser mit rekursivem Abstieg,
  für Funktions-Aufrufe in Ausdrücken?)
\end{itemize}

\end{slide}
