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

\begin{slide}{Endliche Automaten als Scanner}

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

Während ein Automat nur akzeptiert (oder ablehnt),
soll ein Scanner die Eingabe in Tokens zerteilen.

Gegeben ist zu jedem Tokentyp $T_k$ ein Ausdruck $X_k$,
der genau die Token-Werte zu $T_k$ beschreibt.

Der Eingabestring $w$ soll so in Wörter $w_{k_i}$ zerlegt werden, daß
\begin{itemize}
\item $w = w_{k_1} w_{k_1} \ldots w_{k_n}$
\item für alle $1 \le i \le n$: $w_{k_i}$ ist \emph{longest match}:
  \begin{itemize}
  \item $w_{k_i} \in L(X_{k_i})$
  \item
    jedes Anfangsstück von $w_{k_i} \ldots w_{k_n}$,
    das echt länger als $w_{k_i}$ ist,
    gehört zu keinem der $X_k$.
  \end{itemize}
\end{itemize}

\end{slide}

\begin{slide}{Automaten als Scanner (II)}

Man konstruiert aus den $X_i$ Automaten $A_i$
und vereinigt diese, markierte jedoch vorher ihre Endzustände
(jeweils mit $i$). Dann deterministisch und minimal machen.

Beim Lesen der Eingabe zwei Zeiger mitführen:
auf Beginn des aktuellen matches,
und letzten durchlaufenen akzeptierenden Zustand.

Falls Rechnung nicht fortsetzbar, dann bisher besten match
ausgeben, Zeiger entsprechend anpassen, und wiederholen.

Beachte: evtl. muß man ziemlich weit vorausschauen:

Tokens $X_1 = ab, X_2 = ab^*c, X_3=b$, Eingabe $abcabbbbbbac$.

\end{slide}
