Compilerbau: Ableitung regulärer Ausdrücke

Idee	uralt Janusz A. Brzozowski, Princeton Univ. 1964

Ziel	Operationalisierung der Auswertung von regulären Ausdrücken (regulären Mengen)

	Reguläre Ausdrücke direkt verarbeiten ohne eine Transformation in DFAs.

	Weitere Mengenoperationen: Durchschnitt, Komplement, Differenz, exklusives Oder möglich: Alle Booleschen Funktionen

Vorgehen
1.Schritt	Definition einer Funktion δ zum Testen, ob das leere Wort ε in einer regulären Menge r enthalten ist und konstruktive Berechungsvorschrift für δ
2.Schritt	Definition einer Funktion Δ zur Ableitung einer regulären Menge nach einem Wort und konstruktive Berechungsvorschrift für Δ
3.Schritt	Entwicklung einer Funktion, die berechnet ob ein Wort w in einer regulären Menge r enthalten ist.

Definition von δ	Für alle r ∈ R (dem Bereich der regulären Mengen über einem Alphabet A) gilt
	δ(r) = {ε}, falls ε ∈ r
	δ(r) = {}, falls ε ∉ r
äquivalente Definition	δ(r) = r ∩ {ε}

Berechnung von δ
1.	δ({}) = {}
2.	δ({ε}) = {ε}
3.	δ({a}) = {} für alle a ∈ A
4.	δ(r^*) = {ε}
5.	δ(r₁ ⋅ r₂) = δ(r₁) ∩ δ(r₂)
6.	δ(r₁ ∪ r₂) = δ(r₁) ∪ δ(r₂)

Definition von Δ	Für alle r ∈ R und alle a ∈ A gilt:
	Δ_a(r) = {t \| a ⋅t ∈ r}

Erweiterung von Δ	auf Wörter
	Für alle r ∈ R und alle w ∈ A^* gilt:
	Δ_w(r) = {t \| w ⋅t ∈ r}


Berechnung von Δ
1.	Δ_a({}) = {}
2.	Δ_a({ε}) = {}
3.	Δ_a({a}) = {ε}
4.	Δ_a({b}) = {} für alle b ∈ A mit b ≠ a
5.	Δ_a(r^) = Δ_a(r) ⋅ r^
6.	Δ_a(r₁ ⋅ r₂) = Δ_a(r₁) ⋅ r₂ ∪ δ(r₁) ⋅ Δ_a(r₂)
7.	Δ_a(r₁ ∪ r₂) = Δ_a(r₁) ∪ Δ_a(r₂)

Folgerung	Die Ableitung einer regulären Menge ist wieder eine reguläre Menge
Folgerung	Der Algorithmus ist auf natürliche Weise erweiterbar von Zeichen a ∈ A auf Wörter w ∈ A^*
	Δ_ε(r) = r
	Δ_aw(r) = Δ_w(Δ_a(r)) für a ∈ A, w ∈ A^*

Repräsentation	der regulären Mengen durch Ausdrücke
	data RE a = Zero -- {} \| Unit -- {ε} \| Sym a -- {a} \| Star (RE a) -- r* \| Seq (RE a) (RE a) -- r1 . r2 \| Union (RE a) (RE a) -- r1 \| r2

Beispiele
A = {0,1}	type BinRE = RE Bool

A = Char	type RegEx = RE Char

Implementierung von δ	mit Hilfe eines Prädikates nullable
	nullable :: RE a -> Bool nullable Zero = False nullable Unit = True nullable (Sym x) = False nullable (Star r) = True nullable (Seq r1 r2) = nullable r1 && nullable r2 nullable (Union r1 r2) = nullable r1 \|\| nullable r2

Implementierung von Δ	delta :: Eq a => RE a -> a -> RE a delta Zero x = Zero delta Unit x = Zero delta (Sym y) x \| x == y = Unit \| otherwise = Zero delta (Star r) x = Seq (delta r x) (Star r) delta (Seq r1 r2) x \| nullable r1 = Union dr1 dr2 \| otherwise = dr1 where dr1 = Seq (delta r1 x) r2 dr2 = delta r2 x delta (Union r1 r2) x = Union (delta r1 x) (delta r2 x)

Erweiterung von Δ	auf Wörter
	delta' :: Eq a => RE a -> [a]-> RE a delta' re [] = re delta' re (x:w) = delta' (delta re x) w
Worttest	match :: Eq a => RE a -> [a]-> Bool match re w = nullable (delta' re w)

Offene Fragen
?	Praxisrelevanz, Anwendungen?
?	Laufzeit- und Speicherplatzeffizienz?
?	Erweiterbarkeit

Effizienz
	Sequenz und * vergrößern die Ausdrücke
	Im schlimmsten Fall exponentielles Wachstum in Abhängigkeit von der Wortlänge, der Anzahl der Ableitungen
	Unpraktikabel

Ausweg, Verbesserung	beim Konstruieren der Ausdrücke in Δ partiell auswerten und vereinfachen
Gesetzte	zur Vereinfachung
	r ∪ {} = r
	{} ∪ r = r
	r ∪ r = r
	r1 ∪ r2 = r2 ∪ r1
	(r1 ∪ r2) ∪ r3 = r1 ∪ (r2 ∪ r3)
	r ⋅ {} = {}
	{} ⋅ r = {}
	r ⋅ {ε} = r
	{ε} ⋅ r = r

Umsetzung	durch "intelligente" Konstruktoren
Beispiel: r₁ ∪ r₂	union :: Eq a => RE a -> RE a -> RE a union r1 Zero = r1 union Zero r2 = r2 union r1 r2 \| r1 == r2 = r1 \| otherwise = Union r1 r2
Beispiel: r₁ ⋅ r₂	analog
	Platzbedarf bleibt (fast immer) beschränkt, hängt nicht mehr von der Eingabe ab
	Laufzeit für δ und Δ bleibt (fast immer) beschränkt, hängt nicht mehr von der Eingabe ab
	Es gibt worst-case-Fälle, bei denen der abgeleitete reguläre Ausdruck extrem wächst.
Beispiel	r=a?{n}a{n}
Allgemein	Der Ausdruck besteht aus einer Sequenz von R.E.s, die alle das leere Wort enthalten.

Erweiterbarkeit	um Mengendurchschnitt, Differenz, Komplement, exklusives Oder
	Sehr einfach umzusetzen
Beispiel: r₁ ∩ r₂
Datenstruktur	data RE a = ... \| Intersect (RE a) (RE a) \| ...
δ	nullable (Intersec r1 r2) = nullable r1 && nullable r2
Δ	delta (Intersect r1 r2) a = Intersect (delta r1 a) (delta r2 a)
Vereinfachung	intersect :: Eq a => RE a -> RE a -> RE a intersect r1 Zero = Zero intersect Zero r2 = Zero intersect r1 Unit = Unit intersect Unit r2 = Unit intersect r1 r2 \| r1 == r2 = r1 \| otherwise = Intersect r1 r2
	analog für Differenz, Komplement, ...
Praxisrelevanz, Anwendungen
?	für grep, sed, perl, lex, ...
shortest match	reguläre Ausdrücke aus Perl, z.B. für Kommentare (/.../), können auf einfache Weise in reguläre Ausdrücke mit Differenz-Operatoren transformiert werden.
XML, DTD, XML Schema, RelaxNG	Validierung des Inhalts eines Elements gegen das Inhaltsmodell

Ableitung regulärer Ausdrücke

Ableitungen Regulärer Mengen

Implementierung

Erweiterungen