Hallo Welt für Fortgeschrittene - Lehrstuhl für Informatik 2

Hallo Welt für Fortgeschrittene
Parsen
Andreas Hammer
Informatik 2  Programmiersysteme  Martensstraße 3  91058 Erlangen
Inhalt
 Einführung
 Theoretische Grundlagen
□ Grammatiken im Allgemeinen
□ Die Chomsky-Hierarchie
□ Die Chomsky-Normalform für kontextfreie Grammatiken
 Vorgehensweisen beim Parsen
□ Bottom-Up-Parsing
 CYK-Algorithmus
□ Top-Down-Parsing
 Allgemeines Prinzip
 Rekursiver Abstiegsparser
 Ein- und Ausgabe in Java, C und C++
 Reguläre Ausdrücke
 Zusammenfassung
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 2/80
Einführung
 Definition des Begriffs „Parser“:
Ein Parser ist ein Computerprogramm, das in der Informatik für die
Zerlegung und Umwandlung einer beliebigen Eingabe in ein für
die Weiterverarbeitung brauchbares Format zuständig ist.
 Beispiele für Parser:
□ Compiler von Programmiersprachen
□ TeX/LaTeX
□ Intelligente Suche
 z.B. „Wie wird morgen das Wetter?“
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 3/80
Einführung - Compiler
 Vereinfachte Funktionsweise:
□ 1. Analysephase
 Lexikalische Analyse (Zerteilung des Textes in Token)
 Syntaktische Analyse
▫ Überprüfung, ob Syntax „stimmt“, dem Standard entspricht
▫ Umwandlung in Syntaxbaum, Analyse mit Parser
▫ Fehler, falls Syntaxprüfung oder Analyse nicht funktioniert (der Code
nicht korrekt ist)
 Semantische Analyse („Macht der Code Sinn?“), weitere Sprachbedingungen prüfen
□ 2. Synthesephase
 Zwischenprodukte (Header inkludieren, Makros einfügen, …)
 Optimierung (wenn gewünscht)
 Endprodukt (Maschinencode) erzeugen
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 4/80
Einführung - Syntaxbaum
 Beispiel für den Syntaxbaum einer natürlichen Sprache
□ „Grammatik“ ist hier, was man klassisch unter Grammatik versteht
Satz
Subjekt
Prädikat
Artikel
Substantiv
Verb
Die
Katze
schläft
□ Erforschung der Struktur von Sprachen u.a. durch Noam
Chomsky (Chomsky-Hierarchie)
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 5/80
Inhalt
 Einführung
 Theoretische Grundlagen
□ Grammatiken im Allgemeinen
□ Die Chomsky-Hierarchie
□ Die Chomsky-Normalform für kontextfreie Grammatiken
 Vorgehensweisen beim Parsen
□ Bottom-Up-Parsing
 CYK-Algorithmus
□ Top-Down-Parsing
 Allgemeines Prinzip
 Rekursiver Abstiegsparser
 Ein- und Ausgabe in Java, C und C++
 Reguläre Ausdrücke
 Zusammenfassung
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 6/80
Theoretische Grundlagen - Grammatiken
 Eine formale Grammatik G = (V, Σ, P, S) besteht aus
□
□
□
□
V: endliche, nichtleere Menge von Variablen
Σ: endliche, nichtleere Menge von Terminalen
S: Startsymbol, S ∈ V
P: endliche Menge von Produktionen der Form
((V ∪ Σ) + \ Σ*) x (V ∪ Σ)*
Anschaulich: Menge von Ableitungsregeln P → Q, wobei
 P aus mindestens einer Variable und optional Terminalen und
 Q aus beliebig vielen Variablen und Terminalen
besteht.
 Allgemeinster Typ: Chomsky-0-Grammatik
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 7/80
Theoretische Grundlagen – Chomsky-Hierarchie (1)
 Hierarchische Klassifikation von Grammatiken, erstmals
1956 durch Noam Chomsky beschrieben
 Unterschied der Hierarchiestufen:
zunehmend stärkere Einschränkungen für die Form
zulässiger Produktionen
 Grammatik G = (V, Σ, P, S)
□ Chomsky-0: wie auf vorheriger Folie
□ Chomsky-1, „kontextsensitiv“:
 Wie Chomsky-0, zusätzlich:
 ∀ (u → v) ∈ P: |u| ≤ |v|
 Erweiterung: S → ε erlaubt, wenn S nie rechts vorkommt
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 8/80
Theoretische Grundlagen – Chomsky-Hierarchie (2)
□ Chomsky-2, „kontextfrei“ (für uns interessant):
 Wie Chomsky-1, zusätzlich:
 Links darf nur eine Variable stehen
□ Chomsky-3, „regulär“:
 Wie Chomsky-2, zusätzlich:
 Alle Produktionen haben die Form
▫
▫
▫
▫
A → aB (rechtsregulär) oder A → Ba (linksregulär)
A→a
A→ε
für A, B ∈ V, a ∈ Σ
□ Im Folgenden: Details der kontextfreien Grammatik
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 9/80
Theoretische Grundlagen - Beispiel
 Beispiel für eine kontextfreie Grammatik:
□ G = (V, Σ, P, S) mit
 V = {A, T, F}
 Σ = {1, 2, 3, 4}
 P:
▫ A→T|A+T
▫ T→F|T*F
▫ F → 1 | 2 | 3 | 4 | (A)
 S=A
□ Erzeugt mathematische Ausdrücke mit Zahlen 1-4, Operatoren
Plus und Mal, wertet diese in der richtigen Reihenfolge aus,
und lässt Klammerung zu
→ Tafel
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 10/80
Theoretische Grundlagen – Chomsky-Normalform
 Für die Anwendung bestimmter Algorithmen muss die
Grammatik in einer dafür geeigneten Normalform vorliegen.
Für CYK: Chomsky-Normalform
 Definition: Eine kontextfreie Grammatik ist in ChomskyNormalform (CNF), wenn jede Regel in der Form
□ A → BC oder
□ A→a
□ S→ε
ist, mit A ∈ V, B, C ∈ V \ {S} und a ∈ Σ.
 Jede kontextfreie Grammatik kann in eine CNF umgewandelt
werden.
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 11/80
Theoretische Grundlagen – Chomsky-Normalform
 Algorithmus zur Umformung einer kontextfreien Grammatik
in CNF:
1. Eliminiere ε-Produktionen
2. Für jedes Terminalsymbol a: Führe eine neue Variable Aa und
eine neue Regel Aa → a ein; ersetze alle Vorkommen von a
durch Aa
3. Eliminiere Kettenregeln
4. Löse Regeln mit mehr als 2 Variablen auf der rechten Seite auf
5. Entferne unerreichbare und unproduktive Variablen
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 12/80
Theoretische Grundlagen – CNF-Umformung (1)
 Elimination von ε-Produktionen:
□ Entferne alle Regeln der Form A → ε
□ Für jede Regel, die auf A abbildet, füge weitere Regel hinzu, in
der A gestrichen wurde
□ Ausnahme: Falls Startsymbol auf ε abbildet (S → ε)
 In diesem Fall: Füge neues Startsymbol S' ein und neue Regeln:
 S' → ε und S' → S

□ Beispiel:
S → A, A → BC, B → b | ε, C → c
→ Tafel
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 13/80
Theoretische Grundlagen – CNF-Umformung (1)
 Elimination von ε-Produktionen:
□ Entferne alle Regeln der Form A → ε
□ Für jede Regel, die auf A abbildet, füge weitere Regel hinzu, in
der A gestrichen wurde
□ Ausnahme: Falls Startsymbol auf ε abbildet (S → ε)
 In diesem Fall: Füge neues Startsymbol S' ein und neue Regeln:
 S' → ε und S' → S

□ Beispiel:
S → A, A → BC, B → b | ε, C → c
wird umgeformt zu:
S → A, A → BC | C, B → b, C → c
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 14/80
Theoretische Grundlagen – CNF-Umformung (2)
 Für jedes Terminalsymbol a:
Einführung einer neuen Variable Aa und einer neuen Regel
Aa → a; ersetze alle Vorkommen von a durch Aa
□ Ziel: Entfernung „gemischter“ Produktionen, die rechts
Terminale und Nicht-Terminale enthalten
□ Beispiel: A → Ab wird zu A → AAb, Ab → b
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 15/80
Theoretische Grundlagen – CNF-Umformung (3)
 Elimination von Kettenregeln:
□ Ziel: Entfernung von Regeln, die später zur Endlosrekursion
führen würden („im Kreis laufen“)
□ Konstruiere Graph aus Regeln, suche darin nach Zyklen
□ Ersetze bei jedem Zyklus die zugehörigen Variablen durch genau
eine davon, ersetze alle Vorkommen der ersetzten Variable durch
die „genau eine“ (S darf nicht ersetzt werden).
□ Ersetze zum Schluss die übrigen Kettenregeln durch die Regeln
A → „alle rechten Seiten“
 Beispiel:
A → BC | E
E → XZ | F
F→A|Z
Z → aE
→
A → BC | A
A → XZ | A
A→A|Z
Z → aE
→
A → BC | XZ | aE
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 16/80
Theoretische Grundlagen – CNF-Umformung (4)
 Auflösung von Regeln mit mehr als 2 Variablen auf der
rechten Seite
□ Vorgehen: Ersetze so lange jeweils 2 benachbarte Symbole AB
auf der rechten Seite durch neue Var. X, füge neue Regel X →
AB hinzu, bis keine Regeln mit mehr als 2 Variablen mehr
existieren
 Beispiel:
A → BCDEF
→ Tafel
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 17/80
Theoretische Grundlagen – CNF-Umformung (4)
 Auflösung von Regeln mit mehr als 2 Variablen auf der
rechten Seite
□ Vorgehen: Ersetze so lange jeweils 2 benachbarte Symbole AB
auf der rechten Seite durch neue Var. X, füge neue Regel X →
AB hinzu, bis keine Regeln mit mehr als 2 Variablen mehr
existieren
 Beispiel:
A → BCDEF
→
A → XDEF, X → AB
→
A → YEF, Y → XD, X → AB
→
A → ZF, Z → YE, Y → XD, X → AB
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 18/80
Theoretische Grundlagen – CNF-Umformung (5)
 Entferne unerreichbare und unproduktive Variablen
(Reduzieren der CNF)
□ Unerreichbar:
 Variablen, die vom Startsymbol aus nie erreicht werden können
 Regeln, deren linke Seite eine unerreichbare Variable ist, kann
ohne Veränderung der Sprache entfernt werden
□ Unproduktiv:
 Variablen, deren Anwendung nie zu einem Wort der Sprache
führen kann
 Diese Regeln können (und sollen) ebenso entfernt werden
 Grammatik ist nun in CNF und reduziert → Bereit für die
Algorithmen
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 19/80
Inhalt
 Einführung
 Theoretische Grundlagen
□ Grammatiken im Allgemeinen
□ Die Chomsky-Hierarchie
□ Die Chomsky-Normalform für kontextfreie Grammatiken
 Vorgehensweisen beim Parsen
□ Bottom-Up-Parsing
 CYK-Algorithmus
□ Top-Down-Parsing
 Allgemeines Prinzip
 Rekursiver Abstiegsparser
 Ein- und Ausgabe in Java, C und C++
 Reguläre Ausdrücke
 Zusammenfassung
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 20/80
Vorgehensweisen beim Parsen
 Bottom-Up-Parsing
□ „von unten nach oben“, für gegebenes Wort wird geprüft, ob es
der Grammatik entspricht
□ Algorithmus: CYK
 Top-Down-Parsing
□ „von oben nach unten“, wende Regeln der Grammatik an,
versuche daraus das Wort zu bilden
□ Mögliche Umsetzung: Rekursiver Abstiegsparser (RDP)
 Beide Male Backtracking möglich, aber nicht performant
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 21/80
Bottom-Up-Parsing – Der CYK-Algorithmus
 Cocke-Younger-Kasami-Algorithmus
Da fehlt doch
Magenta!
□ Unabhängig voneinander in den 1960er Jahren entwickelt
□ Beantwortet die Frage w ∈ L(G)? für kontextfreie Sprachen mit
Wortlänge n und Anzahl Produktionen P in
 Laufzeit
 Platz
O(n3 * |P|)
O(n2 * |P|)
□ Idee:
 Aufteilen des Wortes in Fragmente, die von Produktionen erzeugt
werden → Tafel
 Einzelne Terminale können direkt hergeleitet werden
 Backtracking → Ausprobieren aller Möglichkeiten
 Kann durch Dynamische Programmierung beschleunigt werden
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 22/80
Bottom-Up-Parsing – Der CYK - Algorithmus
 Pseudocode des Algorithmus:
Für i = 1 … n
Für jede Produktion (l → r) ∈ P
Falls r = wi
Setze Vi,1 := Vi,1 ∪ {l}
vi,j: Variablen, aus denen
wi...wj hergeleitet werden
Für d = 2 … n
Für i = 1 … n – d
kann
Setze j := i + d
Für k = 1 … j – 1
Für jedes (B ∈ Vi,k und C ∈ Vk+1,j)
Wenn (l → BC ∈ P)
Vi,j := Vi,j ∪ {l}
Wenn S ∈ V1,n
→ Wort ist enthalten
Sonst
→ Wort ist nicht enthalten
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 23/80
Bottom-Up-Parsing – Der CYK - Algorithmus
 Beispiel:
□ Grammatik:
S → AB|BC
B → CC|b
A → BA|a
C → AB|a
□ Zu prüfendes Wort: ?
□ → Tafel
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 24/80
Bottom-Up-Parsing – Der CYK - Algorithmus
 Beispiel:
□ Grammatik:
S → AB|BC
B → CC|b
A → BA|a
C → AB|a
□ Zu prüfendes Wort: babab
b
a
b
a
b
{B}
{A,C}
{B}
{A,C}
{B}
{S,A}
{S,C}
{S,A}
{S,C}
{S,C}
{B}
{S,C}
{B}
{B}
{B}
□ S ∉ V1,5 → babab ∉ L(G)
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 25/80
Inhalt
 Einführung
 Theoretische Grundlagen
□ Grammatiken im Allgemeinen
□ Die Chomsky-Hierarchie
□ Die Chomsky-Normalform für kontextfreie Grammatiken
 Vorgehensweisen beim Parsen
□ Bottom-Up-Parsing
 CYK-Algorithmus
□ Top-Down-Parsing
 Allgemeines Prinzip
 Rekursiver Abstiegsparser
 Ein- und Ausgabe in Java, C und C++
 Reguläre Ausdrücke
 Zusammenfassung
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 26/80
Top-Down-Parsing
 Gleiches Problem, „umgekehrte“ Lösung
 Arbeitet „von oben nach unten“
□ Tiefensuche: oben → unten, links → rechts
□ Versuche, Regeln der Grammatik anzuwenden, um zu
prüfenden Satz zu bilden
 Grammatik darf keine Linksrekursion enthalten, sonst
Endlosrekursion
 Laufzeit: O(nn)
□ Normal für Backtracking-Algorithmen
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 27/80
Top-Down-Parsing
 Operationen eines Top-Down-Parsers:
□ Expand
Für gefundene Variable eine Regel der Grammatik anwenden
z.B. X → ab (Vorkommen von X mit ab ersetzen)
□ Scan
Vergleiche Ableitungssymbol mit Eingabesymbol
(„Wurde das gleiche Wort gebildet?“)
Wenn gleich: Weiter expanden, wenn nicht:
□ Backtrack
gehe Schritt zurück, versuche nächste Möglichkeit
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 28/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
 Operation:
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 29/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
VP
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 30/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
VP
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 31/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
VP
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 32/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
VP
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
 Operation:
Scan
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 33/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
VP
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 34/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
VP
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze
 Operation:
Scan
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 35/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 36/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze jagt
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 37/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze jagt
 Operation:
Backtrack
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 38/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 39/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst
 Operation:
Scan
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 40/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst
 Operation:
Scan
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 41/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze
 Operation:
Backtrack
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 42/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
NP
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 43/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
NP
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze jagt
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 44/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
NP
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze jagt
 Operation:
Backtrack
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 45/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
NP
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 46/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
V
NP
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst
 Operation:
Scan
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 47/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 48/80
N
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst Die
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 49/80
N
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst die
 Operation:
Backtrack & Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 50/80
N
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst die
 Operation:
Scan
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 51/80
N
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst die Katze
 Operation:
Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 52/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst die Maus
 Operation:
Backtrack & Expand
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 53/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)?
Die
Katze frisst die Maus
 Operation:
Scan
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 54/80
Top-Down-Parsen (Demo)
 Grammatik:
□
□
□
□
□
□
S → NP VP
NP → DET N
VP → V | V NP
DET → Die | die | den
N → Katze | Maus
V → jagt | frisst
S
NP
DET
N
VP
NP
V
DET
N
 Frage:
□ „Die Katze frisst die Maus“
∈ L(G)!
Die
Katze frisst die Maus
 Operation:
Fertig
Die Katze frisst die Maus
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 55/80
Top-Down-Parsen – Rekursiver Abstiegsparser
 Wie setzt man das um?
□ Recursive Descent Parser
 Erinnerung: Grammatik darf keine Linksrekursion besitzen!
□ Regeln der Form S → Sb können aber leicht umgewandelt
werden:
 A → AX|Y wird zu
A → YA'
A' → XA' | ε
 Grundprinzip der Implementierung:
□ Pro Produktion eine eigene Funktion, die nur diese Produktion
prüft
□ Besonders schön für Grammatiken, bei denen man nicht
backtracken muss
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 56/80
Top-Down-Parsen – Rekursiver Abstiegsparser
 Beispiel:
S → AB
A → a | aB
B → b | ba
„Eine Funktion pro Regel“
pos = Position im Wort
len = Länge des Wortes
accept = Globales Flag
 Code:
fun S() {
//S → A
A(); B();
if(pos != len) {
accept = false;
}
}
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 57/80
Top-Down-Parsen – Rekursiver Abstiegsparser
 Code (weiter):
fun A() {
//A → a | aB
if(matches('a')) {
pos++;
if(pos != len) {
B();
}
} else {
accept = false;
}
}
fun B() {
//B → b | ba
if(matches('b')) {
pos++;
if(pos != len) {
if(matches('a')) {
pos++;
} else {
accept = false;
}
}
} else {
accept = false;
}
}
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 58/80
Inhalt
 Einführung
 Theoretische Grundlagen
□ Grammatiken im Allgemeinen
□ Die Chomsky-Hierarchie
□ Die Chomsky-Normalform für kontextfreie Grammatiken
 Vorgehensweisen beim Parsen
□ Bottom-Up-Parsing
 CYK-Algorithmus
□ Top-Down-Parsing
 Allgemeines Prinzip
 Rekursiver Abstiegsparser
 Ein- und Ausgabe in Java, C und C++
 Reguläre Ausdrücke
 Zusammenfassung
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 59/80
Ein- und Ausgabe in Java, C und C++
 Gleiches Schema bei Aufgaben
□ Einlesen von stdin
□ Algorithmen anwenden
□ Ausgeben auf stdout
 Zu lesende und verändernde Daten können groß werden
□ Aufgabe „Class Exercise“ (SS1):
 6.666.666 Zahlen einlesen, 10.000 Anfragen auf die Daten
□ Problem: Effiziente Ein- und Ausgabemechanismen benötigt
Bei großen Datenmengen ist C/C++ besser geeignet als Java
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 60/80
Ein- und Ausgabe in Java
 Einlesen
□ BufferedReader (in java.io.*)
 Initialisierung:
BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));
 Wichtige Methoden:
▫ public int read();
Liest einzelnes Zeichen, gibt bei EOF -1 zurück.
„Wie getc in C.“
▫ public String readLine();
Liest ganze Zeile ein. Newline ist \r, \n oder \r\n
▫ public int read(char[] cbuf, int off, int len)
Schreibt bis zu len Chars nach cbuf+off.
„Wie fgets in C.“
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 61/80
Ein- und Ausgabe in Java
 Einlesen
□ StringTokenizer (in java.util.*)
 Zur Weiterverarbeitung eines eingelesenen Strings („einer Zeile“)
 Initialisierung:
StringTokenizer st = new StringTokenizer(String str,
String delim);
 Wichtige Methoden:
▫ int countTokens();
Gibt die Anzahl der verbleibenden Tokens zurück
▫ boolean hasMoreTokens();
Gibt es verbleibende Tokens? (z.B. Prüfung in while-Schleife)
▫ string nextToken();
Gibt den nächsten Token zurück
▫ ...und viele mehr
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 62/80
Ein- und Ausgabe in Java
 Einlesen
□ Scanner (in java.util.*)
 Noch komfortabler, aber langsamer (reicht trotzdem für fast alle
Aufgaben aus)
 Initialisierung:
Scanner in = new
Scanner(System.in).useLocale(Locale.ENGLISH);
 Wichtige Methoden:
▫ public boolean hasNext[Int, Float, Double, Long]();
Gibt es einen nächsten Int-, Float-, …-Wert?
▫ public int nextInt(), float nextFloat(), …
Gib den nächsten Int-, Float-, …-Wert zurück
▫ public String nextLine();
Gibt komplette Zeile zurück
▫ public String next();
Gibt nächstes Token als String zurück
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 63/80
Ein- und Ausgabe in Java
 Ausgabe
□ System.out.print($ausgabe)
 $ausgabe kann alles sein, was toString() implementiert, nicht nur
primitive Datentypen
 Konkatenieren mit +, Automatisches \n mit System.out.println();
 Beispiel: System.out.print(„Das ist “ + 1 + „ Test“);
□ System.out.printf(String format, $ausgabe);
 Ähnlich wie printf in C
 Formatstring enthält Anweisungen, wie Argumente in $ausgabe
ausgeben werden sollen
 Beispiele: %d = int, %f = float, %.2f = float mit 2 Nachkommastellen, %c = char, %x = int als Hex, ...
 z.B. System.out.printf(„%d, %f, %x“, 1337, 13.37, 51966); gibt
aus: „1337, 13.37, cafe“
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 64/80
Ein- und Ausgabe in C/C++
 Einlesen
□ int scanf(const char *format, … );
(#include <cstdio> / <stdio.h>)
 Ignoriert Whitespace (' ', '\t', '\n')
 Liest Zeichen an im Formatstring angegebenen Stellen
automatisch in Variablen ein, Rest der Zeichen muss genau so
vorkommen
 Falls anderer Stream als stdin:
int fscanf(FILE *stream, const char *format, …);
 Beispiel:
scanf(„%d - %f“, &a, &b);
Bei Eingabe „42 – 13.37“ steht danach in a 42, in b 13.37
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 65/80
Ein- und Ausgabe in C/C++
 Einlesen
□ char *fgets(char *s, int size, FILE *stream);
 Liest, bis size Zeichen oder '\n' erreicht sind/ist nach s
 Buffer s muss groß genug sein!
□ char *strtok(char *str, const char *delim);
 Zerlegung von str bei jedem Vorkommen von delim
 Erster Aufruf: strtok(zuSplittenderString, delim);
 Alle nachfolgenden: strtok(NULL, delim);
 Gibt NULL zurück, wenn kein weiterer Token gefunden wurde
 Weiterverarbeitung z.B. mit atoi (String → int) oder atof (String →
float
 Vorsicht! strtok macht den String „kaputt“!
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 66/80
Ein- und Ausgabe in C/C++
 Einlesen (C++)
□ cin
(#include <iostream>)
□ Benutzung:
cin >> var1 >> var2 >> …;
varX kann z.B. int, double, long, char u.s.w. sein
□ Komfortabler, aber etwas langsamer als scanf oder fgets + strtok
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 67/80
Ein- und Ausgabe in C/C++
 Ausgabe
□ int printf(const char *format, …)
Benutzung wie in Java mit Formatstring und Argumenten
□ putc, puts, fputc, fputs
 putc(int c): gibt einzelnen Char auf stdout aus
 puts(char *s): gibt Char-Array (String) auf stdout aus
 fputc(int c, FILE *stream),
fputs(char *s, FILE *stream): das gleiche mit beliebigen
Streams
 Schneller als printf
□ Nur in C++: cout
 Benutzung: cout << var1 << var2 << …;
 Wie cin, nur eben Ausgabe
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 68/80
Ein- und Ausgabe - Zeitmessung
 5000 x 5000 Integer-Matrix einlesen und ausgeben (in Sekunden)
40
35
30
25
worst
avg
best
20
15
10
5
0
fgets
scanf
cin/cout
Java BufferedReader
Java Scanner
Gcc 4.9.2 / javac 1.7.0_51 auf Quad i5 @ 3.3GHz, Debian x86_64, Kernel 3.18.9
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 69/80
Inhalt
 Einführung
 Theoretische Grundlagen
□ Grammatiken im Allgemeinen
□ Die Chomsky-Hierarchie
□ Die Chomsky-Normalform für kontextfreie Grammatiken
 Vorgehensweisen beim Parsen
□ Bottom-Up-Parsing
 CYK-Algorithmus
□ Top-Down-Parsing
 Allgemeines Prinzip
 Rekursiver Abstiegsparser
 Ein- und Ausgabe in Java, C und C++
 Reguläre Ausdrücke
 Zusammenfassung
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 70/80
Reguläre Ausdrücke
 Regulärer Ausdruck = Zeichenkette, die die Struktur einer
Zeichenkette beschreibt. Dagegen kann dann „gematched“
werden
 Beschreibt die regulären Sprachen (Chomsky-3)
 Zum Filtern oder „erkennen“ von Texten geeignet, weit
flexibler als nur z.B. strtok & atoi
 In Java in der String-Klasse enthalten:
String text = “2015“;
if(text.matches(“[0-9]+“)) {//text ist eine Zahl}
[0-9]+ bedeutet „Es komme mindestens einmal ein Zeichen
aus dem Bereich '0'-'9' vor“
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 71/80
Reguläre Ausdrücke in Java
 Beispiele:
□ [0-9][0-35-9]
 Ziffer von 0-9, gefolgt von einer Ziffer von 0-3 oder 5-9
□ [3-5][a-zA-Z]?
 Ziffer […], optional gefolgt von Groß- oder Kleinbuchstabe
□ [0-9]*[a-z]+
 Keine oder beliebig viele Ziffern, gefolgt von mindestens einem
Buchstaben
□ Das .*Test
 Beliebige, beliebig viele Zeichen zwischen Leerzeichen und T
▫ z.B. „Das ist ein Test“, „Das Test“, „Das Herpaderp Test“, …
□ [^a-e]
 Negation, beliebiges Zeichen außer a-e
□ Römer geht (nach Haus|in das Haus)
 Zusammenfassen von Zeichenfolgen
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 72/80
Reguläre Ausdrücke in Java
 Alternative in Java: Matcher-Klasse
□ Zuerst Reg. Ausdruck zu Pattern umwandeln:
Pattern p = Pattern.compile(String regexp);
□ Danach Matcher-Objekt erzeugen:
Matcher m = p.matcher(String input)
□ Damit sind folgende Methoden möglich:
 bool matches():
 bool find():
 int start():
Matcht kompletten input-String
Versucht, einen Teilstring von input auf das
Muster zu matchen
Gibt Index des ersten passenden chars
zurück
 etc.
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 73/80
Reguläre Ausdrücke in C++11 und Python
 C++11:
□ bool regex_match(string search, string regex):
 Sucht Matches von regex in search, gibt bei Erfolg true zurück
□ bool regex_search(string search, string regex):
 Wie match, aber sucht nach Substrings und matcht diese
□ string regex_replace(string search, string regex,
string replace):
 Ersetzt jedes Vorkommen von regex in search durch replace
 Python:
□ re-Modul, ähnlich wie Matcher in Java:
import re
matcher = re.compile(„RegExp“)
match = matcher.match(„Suchstring“)
 Match ist None, wenn nichts gefunden wurde, oder lässt durch
match.group() bzw. match.groups() auf gefundene(n) String(s) zugreifen
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 74/80
Inhalt
 Einführung
 Theoretische Grundlagen
□ Grammatiken im Allgemeinen
□ Die Chomsky-Hierarchie
□ Die Chomsky-Normalform für kontextfreie Grammatiken
 Vorgehensweisen beim Parsen
□ Bottom-Up-Parsing
 CYK-Algorithmus
□ Top-Down-Parsing
 Allgemeines Prinzip
 Rekursiver Abstiegsparser
 Ein- und Ausgabe in Java, C und C++
 Reguläre Ausdrücke
 Zusammenfassung
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 75/80
Zusammenfassung
 Wichtig für das Verständnis:
Theoretisches Hintergrundwissen
□ Formale Grammatiken (→ Chomsky-Hierarchie)
□ Umformung nach CNF, um div. Algorithmen anwenden zu
können





Entfernen von ε-Produktionen
Neue Terminalregeln
Entfernen von Kettenregeln
Auflösen „längerer“ Regeln
Ziel: Nur noch Regeln der Form
▫
▫
▫
▫
▫
S→ε
A→b
A → Bb
B→c
…
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 76/80
Zusammenfassung
 Bottom-Up-Parsing
□ Fange mit Wort an, finde heraus, wie es entstanden sein
könnte
□ CYK-Algorithmus
 Vorher: Grammatik nach CNF umwandeln
 Laufzeit: O(n3)
 Top-Down-Parsing
□ Fange mit Startsymbol an, versuche Wort zu bilden
→ Backtracking („Trial and Error“)
□ Rekursive Abstiegsparser
 Jede Regel in Funktion umwandeln
 Linksrekursion vermeiden
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 77/80
Zusammenfassung
 Ein-/Ausgabe in Java, C und C++
□
□
□
□
Java im Vergleich am Langsamsten
Bequemste Variante zum Einlesen: java.util.Scanner
Schnellste Variante: fgets + strtok
Schnellste Ausgabe: putc, printf reicht aber fast immer aus
 Reguläre Ausdrücke
□ Flexibler und komfortabler
□ In Java mit Matcher- oder String-Klasse
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 78/80
Ende
Vielen Dank für eure Aufmerksamkeit!
Fragen?
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 79/80
Literaturhinweise
 Mitschrift zur Vorlesung „Berechenbarkeit und Formale
Sprachen“, Prof. Rolf Wanka, WS14/15
 Vortrag „Parsen“, Andreas Ruprecht, 2011
 C/C++ Reference (http://www.cppreference.com/wiki/)
 Java 7 API (http://docs.oracle.com/javase/7/docs/api/)
 Folien zu „Theoretische Informatik“, Uni Mannheim
(http://th.informatik.uni-mannheim.de/teach/Ti-0809/9/ueb/add/CYK-2.pdf )
 Wikipedia (Regulärer Ausdruck, CYK-Algorithmus)
 TopCoder Forums
(http://apps.topcoder.com/forums/?module=Thread&threadID=697463&start=0&mc=14)
 Theoretische Informatik, Ingo Wegener, Teubner Verlag, 3.
Auflage, 2005
 Python Dokumentation (https://docs.python.org)
Hallo Welt für Fortgeschrittene  Parsen  Andreas Hammer  Folie 80/80

Download Report