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

• reservierte Wörter (if, while, class, ...)
• Bezeichner (foo, bar, ...)
• Literale für ganze Zahlen, Gleitkommazahlen, Strings, Zeichen
• Trennzeichen (Komma, Semikolon)
• Klammern (runde: paren(these)s, eckige: brackets, geschweifte: braces) (jeweils auf und zu)
• Operatoren (=, +, &&, ...)

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:

• für jeden Buchstaben $x \in \Sigma: x\in E$ (autotool: Ziffern oder Kleinbuchstaben)
• das leere Wort $\epsilon \in E$ (autotool: Eps)
• die leere Menge $\emptyset \in E$ (autotool: Empty)
• wenn $A, B\in E$, dann
  • (Verkettung) $A \cdot B \in E$ (autotool: * oder weglassen)
  • (Vereinigung) $A + B \in E$ (autotool: +)
  • (Stern, Hülle) $A^* \in E$ (autotool: ^*)

Jeder Ausdruck beschreibt eine reguläre Sprache.

Beispiele/Aufgaben zu regulären Ausdrücken

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

• alle Wörter, die mit $a$ beginnen und mit $b$ enden: $a \Sigma^* b$.
• alle Wörter, die wenigstens drei $a$ enthalten $\Sigma^* a \Sigma^* a \Sigma^* a \Sigma^*$
• alle Wörter mit gerade vielen $a$ und beliebig vielen $b$?
• Alle Wörter, die ein $aa$ oder ein $bb$ enthalten: $\Sigma^* (aa \cup bb) \Sigma^*$
• (Wie lautet das Komplement dieser Sprache?)

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

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

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

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

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

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

• $\vert S(A)\vert = \vert F(A)\vert = 1$
• keine Pfeile führen nach $S(A)$
• von $S(A)$ führen genau ein Buchstaben- oder zwei $\epsilon$-Pfeile weg
• keine Pfeile führen von $F(A)$ weg

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

Automaten-Synthese (II)

Konstruktion induktiv über den Aufbau von $X$:

• für $c \in \Sigma\cup\{\epsilon\}$: $p_0 \stackrel{c}{\to} p_1$
• für $s_X \stackrel{X}{\to} f_X$, $s_Y \stackrel{Y}{\to} f_Ye:$
  • $s \stackrel {X \cdot Y}{\to} f$ durch $s=s_X, f_X=s_Y, f_Y = f$.
  • $s \stackrel {X \cup Y}{\to} f$ durch $s \stackrel{\epsilon}{\to} s_X, s \stackrel{\epsilon}{\to} s_Y, f_X \stackrel{\epsilon}{\to} f, f_Y \stackrel{\epsilon}{\to} f$
  • $s \stackrel {X^*}{\to} f$ durch $s \stackrel{\epsilon}{\to} s_X, s \stackrel{\epsilon}{\to} f, f_X \stackrel{\epsilon}{\to} s_X, f_X \stackrel{\epsilon}{\to} f$.

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:

• Sub. Alle Strings über Alphabet $\{a,b\}$, die keinen Teilstring $aba$ enthalten.
• Kommentare (Com): beginnen mit $ab$, enden mit $ba$, dazwischen beliebige Zeichenfolge ohne $ba$. Alphabet ist $\{a,b,c,d\}$.
• String-Literale (String): beginnen mit $q$, enden mit $q$, dazwischen kein $q$, es sei denn, es ist escaped ($bq$) Alphabet ist $\{a,b,c,q\}$.
• (Drei): Die Anzahl der $a$ in $w$ ist durch 3 teilbar und alle $b$ stehen links von allen $c$. Alphabet ist $\{a,b,c\}$.

Autotool-Aufgaben (II)

und dazu diese Aufgaben:

• Automaten-Synthese (Synthese-S-{Sub,Com,String,Drei}): Finden Sie jeweils einen endlichen Automaten, der die Sprache erzeugt.
• Analyse-A-{Sub,Com,String,Drei}: Finden Sie jeweils einen regulären Ausdruck, der die Sprache beschreibt.

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