View
104
Download
0
Category
Preview:
Citation preview
Entwurf und Implementierung
eines Scanner-Generatorsystems
nach der Methode von Gluschkow
Sabine Ludvik
27.10.2007
Was ist ein Scanner-Generatorsystem
und wozu braucht man es?ein Programm, welches:
testet, ob ein eingelesenes Wort dem vorgegebenen Muster entspricht
Beispiel Variablenbezeichner: korrekter Bezeichner: myVar oder Var2 nicht korrekter Bezeichner: -myVar oder 2Var
Input des Programm: reguläre Ausdrücke als konkrete syntaktische Spezifikationen
Aufgabenstellung I
2
Chomsky-Hierarchie: Formalisierung von Sprachen
Formale Sprachen
Grammatik
Sprache Automat
Typ 0rekursiv
aufzählbarTuringmaschine
Typ 1 kontextsensitivlinear beschränkter
Automat
Typ 2 kontextfrei Kellerautomat
Typ 3 regulärendlicher Automat
3
Automat = Akzeptor der definierenden Sprache
• virtuelle Zustandsmaschine
• Elemente: Zustände und Zustandsübergänge
• Input: Wort
Endlicher Automat:
Typ 3: reguläre Grammatik / regulärer Ausdruck
• endliche Zustandsmenge
• A = (S, T, δ, So, E)
Automaten
4
Was ist ein Scanner-Generatorsystem?
eine Software, die folgendes implementiert:
die Erzeugung von endlichen Automaten = Generator Input: regulärer Ausdruck
deren Anwendung zum Testen von Token= Simulator Input: Wort
Aufgabenstellung II
5
• Alternative zu regulärer Grammatik
• beschreiben Mengen von Zeichenketten
• Syntax ist definiert durch Eingabealphabet und spezielle syntaktische Zeichen: « » [ ] | ε
• Mengenoperationen definieren die beschriebene Sprache (Semantik): - Alternative („Mengenvereinigung“: |)- Konkatenation („Aneinanderreihung“: •)- Kleene‘sche Sternoperation („Wiederholung“: « » )
• Beispiel: R = [ a | a « b » c | | w x y z ]
Reguläre Ausdrücke
6
Viktor Michailowitsch Gluschkow (1923 - 1982)
• Theorie der abstrakten Automaten. Mathematische Forschungsberichte (deutsch:1963)
• Methode zur direkten Erzeugung eines DEA aus einem regulären Ausdruck in zwei Schritten:
Schritt 1: Indizierung des regulären Ausdrucks (Regel a-e)
Schritt 2:Berechnung der Zustandsüberführungsfunktion
Gluschkow I
7
jedes einzelne Zeichen des regulären Ausdrucks hat zwei „Stellen“:
Gluschkow II
8
R = [ a | a « b » c | | w x y z ]
0 1 2 3 4 5 6 7 8 9
Vorgrundstelle
Grundstelle
jedes Eingabezeichen erhält einen Grundindex:
R = [ a | a « b » c | | w x y z ]
Weitergabe nach Regel a-e erzeugt abgeleitete Indizes
GUI-Anforderungen:
• GUI im Microsoft-Windows-Stil• Projektverwaltung• Persistenz• optional: Sprachen
Gluschkow-Algorithmen:
• Ableitungsbaum des regulären Ausdrucks• Indizierung des regulären Ausdrucks: Regeln a-e• Berechnung der Zustandsüberführungsfunktion• Simulator• optional: Zustandsdiagramm
Anforderungen
9
Entwurf - Struktur
10
Entwurf nach MVC-Modell:
M odel: Algorithmen
V iew: Präsentation
C ontroller: Programmsteuerung
DOM: Elemente
• Expression []
• Loop « »
• Option |
• Terminal
• Epsilon
• Root
11
Beispiel: [ a | a « b » c | ]
Elemente sind XML-NodesElemente haben Attribute
DOM: Attribute
• INDEX_BASE:Grundindex eines Terminals oder Epsilons
• INDEX_OPEN:abgeleitete Indizes am Anfang von Loops oder Expressions und von Epsilon
• INDEX_CLOSE:abgeleitete Indizes am Ende von Loops oder Expressions
12
Indizierung: Lexer
Schritt 1: Lexer
Beispiel von: [ a | a « b » c | ]
regulärer Ausdruck Token-Strom
13
Indizierung: Parser
Schritt 2: Parser
Token-Strom DOM
14
Indexübertragung
Quelle Akzeptor
• von „oben nach unten“ • von „links nach rechts“
15
Regel aIndizes über öffnende Klammern
ziehen:
16
Regel bIndizes über schließende Klammern
ziehen:
17
Regel cWeglassen eines regulären Teilausdrucks:
18
Regel dWiederholen eines regulären
Teilausdrucks:
19
Regel eBearbeitung des leeren Wortes ε:
20
Indizierung II
21Schritt 1 der DEA-Konstruktion ist beendet!
Indizierung III
vor der Indizierung:„Liste“ Baum
nach der Indizierung:Baum Liste
22
{ 0 } { 1, 2 } {IA1, IA2,...} {IF1, IF2,...}
Zustandsüber-führungsfunktion I
23
a
R = [ a | a « b » c | | w x y z ]
0 1 2 3 4 5 6 7 8 9 0a 0a 0a 0a
( S0, a ) = { 1,2 } = S1
( S0, b ) = { Ø } = S⒠ ( S0, c ) = { Ø } = S⒠ ( S0, w ) = { 6 } = S2
...
Zustandsübergang: x
Berechnung:• Ausgangspunkt: S0 mit Grundindex 0• berechnete Zustände werden sukzessive bearbeitet• Endpunkt: keine unberechneten Zustände mehr
Zustandsüber-führungsfunktion II
24
Zustandsdiagramm
optionale Anforderung, daher einfache Implementierung:
1. Schritt: Einteilung in vier Gruppen und Positionierung
2. Schritt: Ergänzung von - Pfeilen- Schlingen- Buchstaben
25
Simulator
Testen beliebiger Zeichenfolgen
Darstellung aller Einzelschritte
Anzeige, ob das Wort
akzeptiert wurde: Endzustand
nicht akzeptiert wurde: kein Endzustand oder Fehlerzustand
26
Zusammenfassung
SL»DEA erfüllt alle geforderten Anforderungen:
• MS-Windows-GUI• Generierung eines DEA aus einem regulären
Ausdruck• Simulationen von Eingabezeichenfolgen• Dokumentation und Benutzeranleitung
zusätzlich wurde implementiert:
• Sprachunterstützung zur Laufzeit• einfache Zustandsdiagramme
Weiterentwicklungen:
• geplant: Drucken / Projektverwaltung• denkbar: schrittweise mitverfolgbare Indizierung 27
Dank
für das Thema, die Betreuung und Begutachtung:
• Prof. Dr. Bernhard Zimmermann• Dipl.-Ing. Ute Kretschmer
für moralische Unterstützung:
• Jan-Peter Flato• Ulrich Szagun• Holger Sanio
28
Recommended