next up previous
Nächste Seite: Übungen Reguläre Ausdrücke (12. Aufwärts: Compilerbau Vorlesung, Wintersemester 2003 Vorherige Seite: Lexikalische Analyse (5. 11.)

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

$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

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

Idee: betrachten Mengen von erreichbaren Zuständen

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

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:

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

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ß

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:


next up previous
Nächste Seite: Übungen Reguläre Ausdrücke (12. Aufwärts: Compilerbau Vorlesung, Wintersemester 2003 Vorherige Seite: Lexikalische Analyse (5. 11.)
Johannes Waldmann 2004-01-28