View
32
Download
2
Category
Preview:
DESCRIPTION
Parsing regulärer Ausdrücke. Karin Haenelt 25.4.2009. Inhalt. kontextfreie Grammatik für reguläre Ausdrücke Grundlagen Parsebaum: konkrete Syntax Syntaxbaum: abstrakte Syntax Algorithmus: Parsing regulärer Ausdrücke Erkennung Konstruktion des Syntaxbaumes. - PowerPoint PPT Presentation
Citation preview
1
Parsing regulärer Ausdrücke
Karin Haenelt
25.4.2009
Inhalt
kontextfreie Grammatik für reguläre Ausdrücke Grundlagen
Parsebaum: konkrete Syntax Syntaxbaum: abstrakte Syntax
Algorithmus: Parsing regulärer Ausdrücke Erkennung Konstruktion des Syntaxbaumes
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
2
Grammatik für reguläre Ausdrücke
reguläre Ausdrücke beschreiben reguläre Sprachen Notationssprache für reguläre Ausdrücke
ist keine reguläre Sprache Sprache enthält Klammern
die beliebig ineinander geschachtelt werden können ausbalanciert sein müssen (Anzahl öffnender
Klammern = Anzahl schließender Klammern) ist eine kontextfreie Sprache
Erkennung mit Automaten mit Gedächtnis
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
3
Konkrete Syntax und abstrakte Syntax
konkrete Syntax Ableitungsbaum der Erkennung mit kontextfreier Grammatik Parsebaum Ziel: effiziente Erkennung
abstrakte Syntax Abstraktion von Details, die zur Weiterverarbeitung nicht
gebraucht werden Syntaxbaum
Ziel: effiziente Weiterverarbeitung Ziel: kontextfreie Grammatik – nach der konkrete Syntax und
abstrakte Syntax möglichst ähnlich sind
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
4
Grammatik für arithmetische Ausdrücke, 1. Entwurf
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
5
EEEEE |
1
E +
E
2 3
E E
E E
E
3
E
1 2
E + E
2 Ableitungen mit 2 Strukturen für 1+2x3
x
x
unbrauchbar zur weiterenAuswertung des Ausdrucks,falsche Priorität der Rechenregeln
Grammatik für reguläre Ausdrücke, 2. Entwurf
Berücksichtigung der Priorität der Operatoren
+ vereinigt Produkte (Operator • hat seine Argumente zuvor gebunden)
• konkateniert Terme (Operator * hat sein Argument zuvor gebunden)
* bindet sein Argument zuerst
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
6
)(|*||
|
ETidTTPTPPEPE
Expression
ProductTerminal
Kontextfreie Grammatik für reguläre Ausdrücke
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
7
)(|*|||...||
|
ETaTTPTPPEPE
(a|b)*abbGrammatik BeispielAbleitungsbaum
Die Grammatikregel enthält eineRechtsrekursion.Rechtsrekursion lässt sich durchIteration darstellen. In einer iterativen Darstellung treten die markierten Ableitungen nicht auf a b
T TP
P | EE( ) aT * T •
T • PP
bb TT • P
P
E
Erkennen regulärer Ausdrücke
Grundlage: Grammatik für reguläre Ausdrücke E → P + E | P Ausdruck P → T •P | T Produkt T → 0 | 1 |ε | Ø | T* | (E) Terminal
(Terminalsymbole können erweitert werden) weder Lexikon noch Grammatik sind komplex oder veränderlich Erkenner kann direkt aus der Grammatik abgeleitet werden,
indem man für jede Variable eine Prozedur schreibt(Hopcroft/Ullman, 1988: 128/129)
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
8
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
9
)(|*| ETidT
PEPE |
procedure FINDE_AUSDRUCK; begin FINDE_PRODUKT; while erste Symbol von STRING ist ’+’ do // Disjunktion { stringIndex++; FINDE_PRODUKT; } end FINDE_AUSDRUCK; procedure FINDE_PRODUKT; begin FINDE_TERM; while erstes Symbol von String ist ’•’ do // Konkatenation { stringIndex++; FINDE_TERM; } end FINDE_PRODUKT; procedure FINDE_TERM; begin if erstes Symbol von STRING ist TERMINAL then { stringIndex++;} else if erstes Symbol von STRING ist ’(’ then { stringIndex++; FINDE_AUSDRUCK; if erstes Symbol von STRING ist ’)’ then stringIndex++; else Fehler } while erstes Symbol von STRING ist ’*’ do // Kleenesche Hülle {stringIndex++;} end FINDE_TERM;
Algorithmus zur Erkennungregulärer Ausdrückenach Hopcroft/Ullmann 1988:128
1
347
12
16
21232627
31
PEPE |
TPTP |
*|)(| TEidT
Ableitungsstruktur nach Algorithmus
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
10
Beispiel: (a|b)*abb
21a 21b
12T 12T
3P 7P4|
23( 27)26E 31*
12T 13•
21a
16T 13•
21b
16T 13•
21b
16T
3P
1E
Die Zahlen geben die Zeile desAlgorithmus an
Konstruktion des Syntaxbaumes
Erkennungsalgorithmus durchläuft nur den Ausdruck und erkennt ihn gibt accept oder reject aus erzeugt keine weitere Ausgabe
Konstruktionsanweisungen für den Syntaxbaum müssen an den entsprechenden Stellen im Algorithmus hinzugefügt werden
Veränderungen gegenüber der konkreten Syntax: Operatoren als innere Knoten Operanden als Kinder des Knotens Symbole des Eingabealphabetes und leere Kette als
terminale Knoten Grundstruktur
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
11
class TreeNode{ String info;
TreeNode left; TreeNode right;
}
Ein Parsebaum und Syntaxbaum
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
12
(a|b)*abb
a b
ab
b#
|*
●●
●●
Parsebaum Syntaxbaum
a*T •T •
P
bbTT •
a bT
P | PE( )
E
T
Vielen Dank
Für das Aufspüren von Fehlern in früheren Versionen und für Verbesserungsvorschläge danke ich
Victor Gabriel Saiz Castillo, Robert Schumann
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
13
Literatur
Aho, Alfred V.; Sethi, Ravi und Jeffrey D. Ullman (1986). Compilers. Principles, Techniques and Tools. Addison-Wesley Publishing Company.
Hopcroft, John E. und Jeffrey D. Ullman (1988). Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn u. a.: Addison-Wesley, 1988 (engl. Original Introduction to automata theory, languages and computation).
Hopcroft, John E., Rajeev Motwani und Jeffrey D. Ullman (2002). Einführung in die Automatentheorie, Formale Sprachen und Komplexität. Pearson Studium engl. Original: Introduction to Automata Theory, Languages and Computation. Addison-Wesley. www-db.stanford.edu/~ullman/ialc.html
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
14
Versionen
25.04.2009 06.05.2008, 05.05.2007 27.05.,20.05.2005
© Karin Haenelt,Parsing regulärer Ausdrücke 25.4.2009, 1 22.5.2005
15
Recommended