\begin{slide}{Robuste Parser-Bibliotheken}

Designfragen:
  \begin{itemize}
  \item asymmetrisches \verb+<|>+
  \item Nichtdeterminismus einschränken
  \item Fehlermeldungen (Quelltextposition)
  \end{itemize}

Beispiel: Parsec (Autor: Daan Leijen) 
\url{http://www.haskell.org/haskellwiki/Parsec}

\end{slide}

\begin{slide}{Asymmetrische Komposition}

gemeinsam:
\begin{verbatim}
(<|>) :: Parser c a -> Parser c a 
      -> Parser c a
Parser p <|> Parser q = Parser $ \ s -> ...
\end{verbatim}
\begin{itemize}
\item symmetrisch: \verb|p s ++ q s|
\item asymmetrisch: \verb|if null p s then q s else p s|
\end{itemize}

Anwendung: \verb|many| liefert nur maximal mögliche
Wiederholung (nicht auch alle kürzeren)

\end{slide}

\begin{slide}{Nichtdeterminismus einschränken}

  \begin{itemize}
  \item 
Nichtdeterminismus $=$ Berechnungsbaum $=$ Backtracking
\item
asymmetrisches \verb+p <|> q+ : 
probiere erst \verb|p|, dann \verb|q|
\item
häufiger Fall: \verb|p| lehnt \glqq sofort\grqq\ ab
  \end{itemize}

Festlegung (in Parsec): 
wenn \verb|p| wenigstens ein Zeichen verbraucht,
dann wird \verb|q| nicht benutzt 
(d. h. \verb|p| muß erfolgreich sein)

Backtracking dann nur durch \verb+try p <|> q+

\end{slide}

\begin{slide}{Fehlermeldungen}

  \begin{itemize}
  \item Fehler $=$ Position im Eingabestrom,
    bei der es \glqq nicht weitergeht\grqq
  \item und auch durch Backtracking keine 
    Fortsetzung gefunden wird
  \item Fehlermeldung enthält:
    \begin{itemize}
    \item Position
    \item Inhalt (Zeichen) der Position
    \item Menge der Zeichen mit Fortsetzung
    \end{itemize}
  \end{itemize}

\end{slide}
