next up previous
Nächste Seite: Lexikalische Analyse (10. 11.) Aufwärts: Compilerbau Vorlesung, Wintersemester 2003 Vorherige Seite: Lokale Klassen in Java

Lexikalische Analyse (5. 11.)

Daten-Repräsentation im Compiler

$ $Id: daten.tex,v 1.2 2003/11/03 12:11:31 joe Exp $ $

Jede Compiler-Phase arbeitet auf geeigneter Repräsentation ihre Eingabedaten.

Die semantischen Operationen benötigen das Programm als Baum

(das ist auch die Form, die der Programmierer im Kopf hat).

In den Knoten des Baums stehen Token,

jedes Token hat einen Typ und einen Inhalt (eine Zeichenkette).

Token-Typen

Token-Typen sind üblicherweise

Reguläre Ausdrücke/Sprachen

Die Menge aller möglichen Werte einer Tokenklasse ist üblicherweise eine reguläre Sprache, und wird (extern) durch eine regulären Ausdruck beschrieben.

Die Menge $E(\Sigma)$ der regulären Ausdrücke über einem Alphabet (Buchstabenmenge) $\Sigma$ ist die kleinste Menge $E$, für die gilt:

Jeder Ausdruck beschreibt eine reguläre Sprache.

Beispiele/Aufgaben zu regulären Ausdrücken

Wir fixieren das Alphabet $\Sigma=\{a,b\}$.

Endliche Automaten

$ $Id: auto.tex,v 1.2 2003/11/03 12:11:31 joe Exp $ $

Intern stellt man reguläre Sprachen lieber effizienter dar:

Ein (nichtdeterministischer) endlicher Automat $A$ ist ein Tupel $(Q, S, F, T)$ mit

  • endlicher Menge $Q$ (Zustände)
  • Menge $S \subseteq Q$ (Start-Zustände)
  • Menge $F \subseteq Q$ (akzeptierende Zustände)
  • Relation $T \subseteq (Q \times \Sigma) \times Q$

    bzw. Funktion $T: (Q \times \Sigma) \to 2^Q$

autotool:
NFA { states = mkSet [ 1, 2, 3]
    , starts = mkSet [ 2]
    , finals = mkSet [ 2]
    , trans = listToFM 
         [ ((1, 'a'), mkSet [ 2])
         , ((2, 'a'), mkSet [ 1])
         , ((2, 'b'), mkSet [ 3])
         , ((3, 'b'), mkSet [ 2])
         ]
    }

Rechnungen und Sprachen von Automaten

Für $((p,c),q)\in T(A)$ schreiben wir auch $p \stackrel{c}{\to}_A q$.

Für ein Wort $w = c_1 c_2 \ldots c_n$ und Zustände $p_0, p_1, \ldots, p_n$ mit

$\displaystyle p_0 \stackrel{c_1}{\to}_A p_1 \stackrel{c_2}{\to}_A \ldots
\stackrel{c_n}{\to}_A p_n $

schreiben wir $p_0 \stackrel{w}{\to}_A p_n$.

(es gibt in $A$ einen mit $w$ beschrifteten Pfad von $p_0$ nach $p_n$).

Die Sprache von $A$ ist

$\displaystyle L(A) = \{ w \mid \exists p_0\in S, p_n\in F: p_0 \stackrel{w}{\to}_A p_n \}
$

Automaten mit Epsilon-Übergängen

$ $Id: eps.tex,v 1.1 2003/11/03 12:11:31 joe Exp $ $

Definition. Ein $\epsilon$-Automat ist ... mit $T \subseteq (Q \times (\Sigma \cup \{\epsilon\})) \times Q$.

Definition. $p \stackrel{c}{\to}_A q$ wie früher, und $p \stackrel{\epsilon}{\to}_A q$ für $((p, \epsilon),q) \in T$.

Satz. Zu jedem $\epsilon$-Automaten $A$ gibt es einen Automaten $B$ mit $L(A)=L(B)$.

Beweis: benutzt $\epsilon$-Hüllen: $H(q) = $ alle $r \in Q$, die von $q$ durch Folgen von $\epsilon$-Übergängen erreichbar sind:

$\displaystyle H(q) = \{ r \in Q \mid q \stackrel{\epsilon}{\to}_A^* r \} $

Konstruktion: $B = (Q, H(S), A, T')$ mit

$\displaystyle p \stackrel{c}{\to}_B r
\iff \exists q \in Q:
p \stackrel{c}{\to}_A q \stackrel{\epsilon}{\to}_A^* r
$

Optimierung: in $B$ alle Zustände streichen, von denen in $A$ nur $\epsilon$-Pfeile ausgehen.

Automaten-Synthese

$ $Id: synth.tex,v 1.1 2003/11/03 12:11:31 joe Exp $ $

Satz: Zu jedem regulären Ausdruck $X$ gibt es einen $\epsilon$-Automaten $A$, so daß $L(X) = L(A)$.

Beweis (Automaten-Synthese) Wir konstruieren zu jedem $X$ ein $A$ mit:

Wir bezeichnen solche $A$ mit $s \stackrel{X}{\to} f$.

Automaten-Synthese (II)

Konstruktion induktiv über den Aufbau von $X$:

Satz. Der so erzeugt Automat $A$ ist korrekt und $\vert Q(A)\vert \le 2 \vert X\vert$.

Aufgabe: Warum braucht man bei $X^*$ die zwei neuen Zustände $s,f$ und kann nicht $s=s_X$ oder $f=f_X$ setzen?

Hinweise: (wenigstens) eine der Invarianten wird verletzt, und damit (wenigstens) eine der anderen Konstuktionen inkorrekt.

Autotool-Aufgaben

$ $Id: aufgaben.tex,v 1.4 2003/11/12 09:56:19 joe Exp $ $

Wir betrachten diese Sprachen:

Autotool-Aufgaben (II)

und dazu diese Aufgaben:

Synthese-S-Quiz: finden Sie einen endlichen Automaten zu gegebenem regulären Ausdruck.


next up previous
Nächste Seite: Lexikalische Analyse (10. 11.) Aufwärts: Compilerbau Vorlesung, Wintersemester 2003 Vorherige Seite: Lokale Klassen in Java
Johannes Waldmann 2004-01-28