Lexikalische Analyse (10. 11.)

Reduzierte Automaten

$$Id: reduz.tex,v 1.1 2003/11/10 13:52:47 joe Exp $$

Ein Zustand $q$ eines Automaten $A$ heißt

• erreichbar, falls von $q$ von einem Startzustand aus erreichbar ist: $\exists w \in \Sigma^*, s \in S(A): s \stackrel{w}{\to} q$.
• produktiv, falls von $q$ aus ein aktzeptierender Zustand erreichbar ist: $\exists w \in \Sigma^*, f \in F(A): q \stackrel{w}{\to} f$.
• nützlich, wenn er erreichbar und produktiv ist.

$A$ heißt reduziert, wenn alle Zustände nützlich sind.

Satz: Zu jedem Automaten $A$ gibt es einen reduzierten Automaten $B$ mit $L(A)=L(B)$.

Beweis: erst $A$ auf erreichbare Zustände einschränken, ergibt $A'$, dann $A'$ auf produktive Zustände einschränken, ergibt $B$.

Deteministische Automaten

$$Id: det.tex,v 1.3 2003/11/10 13:52:47 joe Exp $$

$A$ heißt vollständig, wenn es zu jedem $(p,c)$ wenigstens ein $q$ mit $p \stackrel{c}{\to}_A q$ gibt.

$A$ heißt deterministisch, falls

• die Start-Menge $S(A)$ genau ein Element enthält und
• die Relation $T(A)$ sogar eine partielle Funktion ist (d. h. zu jedem $(p,c)$ gibt es höchstens ein $q$ mit $p \stackrel{c}{\to}_A q$.

Dann gibt es in $A$ für jedes Wort $w$ höchstens einen mit $w$ beschrifteten Pfad vom Startzustand aus.

Satz: Zu jedem Automaten $A$ gibt es einen deterministischen und vollständigen Automaten $D$ mit $L(A)=L(D)$.

Potenzmengen-Konstruktion

$$Id: potenz.tex,v 1.1 2003/11/10 13:52:47 joe Exp $$

• Eingabe: ein (nicht-det.) Automat $A = (Q,S,F,T)$
• Ausgabe: ein vollst. det. Automat $A'$ mit $L(A')=L(A)$.

Idee: betrachten Mengen von erreichbaren Zuständen

$A' = (Q',S',F',T')$ mit

• $Q' = 2^Q$ (Potenzmenge - daher der Name)
• $((p', c),q') \in T' \iff q' = \{ q \mid \exists p \in p': p \stackrel{c}{\to}_A q \}$
• $S' = \{ S \}$
• $F' = \{ q' \mid q' \in Q' \wedge q' \cap F \neq \emptyset \}$

Minimierung von det. Aut. (I)

$$Id: min.tex,v 1.1 2003/11/10 13:52:47 joe Exp $$

Idee: Zustände zusammenlegen, die ,,das gleiche`` tun. Das ,,gleich`` muß man aber passend definieren: benutzen Folgen von Äquivalenz-Relationen $\sim_0, \sim_1, \ldots$ auf $Q$.

$p \sim_k q \iff$ Zustände $p$ und $q$ verhalten sich für alle Eingaben der Länge $\le k$ beobachtbar gleich: $\forall w \in \Sigma^{\le k}: w \in L(A,p) \leftrightarrow w \in L(A,q)$.

äquivalent ist induktive Definition:

• $(p \sim_0 q) :\iff (p \in F \leftrightarrow q \in F)$
• $(p \sim_{k+1} q) :\iff (p \sim_k q) \wedge \forall c\in\Sigma: T(p,c) \sim_k T(q,c)$.

Minimierung von det. Aut. (II)

Nach Definition ist jeder Relation eine Verfeinerung der Vorgänger: $\sim_0 \supseteq \sim_1 \supseteq \ldots$. Da die Trägermenge $Q$ endlich ist, kann man nur endlich oft verfeinern, und es gibt ein $k$ mit $\sim_k = \sim_{k+1} = \ldots$. Wir setzen $\sim := \sim_k$.

Konstruiere $A' = (Q',S',F',T')$ mit

• $Q' = Q/\sim$ (Äquivalenzklassen)
• $S' = [s]_{\sim}$ (die Äq.-Klasse des Startzustands)
• $F' = \{ [f]_{\sim} \mid f \in F \}$ (Äq.-Kl. v. akzt. Zust.)
• für alle $((p,c),q)\in T: (([p]_{\sim},c),[q]_{\sim})\in T'$.

Satz: Wenn $A$ vollständig und deterministisch,
dann ist $A'$ ein kleinster vollst. det. Aut mit $L(A')=L(A)$.

Endliche Automaten als Scanner

$$Id: scan.tex,v 1.2 2003/11/10 13:52:47 joe 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ß

• $w = w_{k_1} w_{k_1} \ldots w_{k_n}$
• für alle $1 \le i \le n$: $w_{k_i}$ ist longest match:
  • $w_{k_i} \in L(X_{k_i})$
  • 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$.

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$.

Komprimierte Automatentabellen

$$Id: tables.tex,v 1.2 2003/11/10 13:52:47 joe Exp $$

Für det. Aut. braucht man Tabelle (partielle Funktion) $T:(Q \times \Sigma) \hookrightarrow Q$. Die ist aber riesengroß, und die meisten Einträge sind leer. Sie wird deswegen komprimiert gespeichert. Benutze Felder next, default, base, check.

Idee: es gibt viele ähnlichen Zustände:

Zustand $p$ verhält sich wie $q$, außer bei Zeichen $c$:
default[base[p]] = q; check[base[p]+c] = p;

Übergang $T(p,c)=$ lookup(p,c) mit

lookup (p, c) {     int a = base[p] + c;
    if  ( p == check[a] ) { return next[a]; }
    else { return lookup (default [p],c); }   }

Scanner mit Flex (I)

$$Id: flex.tex,v 1.2 2003/11/10 13:52:47 joe Exp $$

Das Programm flex erzeugt aus einer Scanner-Beschreibung einen Scanner (ein C-Programm).

Wie beschrieben wird aus regulären Ausdrücken $X_i$ ein (markierter) deterministischer Automaten $A$ bestimmt.

Beim Feststellen eines matches kann eine Aktion ausgeführt werden (default: String ausgeben).

Bei mehreren gleichlangen matches wird der (im Quelltext) erste genommen.

Damit der Scanner niemals hängt, gibt es einen Default-Tokentyp, der (zuletzt) jedes einzelne Zeichen matcht (und ausgibt).

Scanner mit Flex (II)

DIGIT   [0-9]
%%
DIGIT+  { fprintf (stdout, "%s", yytext); }
" "+    { fprintf (stdout, " "); }
"\n"    { fprintf (stdout, "\n"); }
%%
int yywrap () { return 1; }
int main ( int argc, char ** argv ) { yylex (); }

Aufruf mit flex -t simple.l > simple.c. Optionen:

• -T (Table) zeigt Automatentabellen
• -d (debug),
• -f (fast) ohne Tabellen-Kompression