1 Parsing regulärer Ausdrücke Karin Haenelt 25.4.2009

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


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


4

Grammatik für arithmetische Ausdrücke, 1. Entwurf


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


6

)(|*|

|

|

ETidT

TPTP

PEPE

Expression

ProductTerminal

Kontextfreie Grammatik für reguläre Ausdrücke


7

)(|*|||...|

|

|

ETaT

TPTP

PEPE

(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 T

P

P | E

E( ) a

T * T •

T • P

P

b

b T

T • 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)


8


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


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


11

class TreeNode{ String info;

TreeNode left; TreeNode right;

}

Ein Parsebaum und Syntaxbaum


12

(a|b)*abb

a b

ab

b#

|*

●●

●

●

Parsebaum Syntaxbaum

a*

T •T •

P

bb

TT •

a b

T

P | P

E( )

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


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


14

http://www.pearson-studium.de/

http://www-db.stanford.edu/~ullman/ialc.html

Versionen

25.04.2009 06.05.2008, 05.05.2007 27.05.,20.05.2005


15

Documents

1 Parsing regulärer Ausdrücke Karin Haenelt 25.4.2009