Inhaltsverzeichnis
10. Kapitel: Syntaxanalyse (Parsing)
Zwei grundsätzliche Vorgehensweisen werden für die
Kontextfreie Grammatiken
Diese Grammatik beschreibt reguläre Ausdrücke wie etwa
Die verschiedenen Produktionen entsprechen trotz dieser
Ein natürlicher Weg zur Beschreibung des Ergebnisses
Syntaxbaum für (A*B +AC)D
Die Hauptaufgabe eines Parsers besteht darin, Zeichenfolgen,
Ein weiteres Beispiel für eine kontextfreie Grammatik
Diese Regeln legen fest, woraus „zulässige“ arithmetische
Jeder reguläre Ausdruck ist selbst ein Beispiel für eine
Der rekursive Abstieg (Top-Down-Syntaxanalyse)
Prozedur als Teil eines Top-Down-Parsers
Das erste, was Ausdruck bewirkt, ist ein Aufruf der Prozedur
Die Prozedur Term hingegen muss einen Teil der Aufgabe
Prozedur Faktor
Syntaxanalyse von ( A * B + AC ) D
Die Funktionen Ausdruck, Term und Faktor sind
Der Top-Down-Ansatz führt nicht für alle möglichen
Wenn diese Prozedur mit einem p[j] aufgerufen würde,
Bottom-up Analyse
Verbindungen zum Pattern Matching
Zunächst muss man eine Methode entwickeln, um die Muster
Beschreibung von Mustern
3) Hüllenbildung (Closure): Diese Operation gestattet es,
Eine Folge von Symbolen, die unter Verwendung dieser
Der Pattern Matching-Algorithmus kann als eine
Automaten für das Pattern Matching
Um reguläre Ausdrücke zu behandeln, ist es erforderlich,
Ein nichtdeterministischer Mustererkennungs-Automat
Der Automat hat einen eindeutigen Anfangszustand
Konstruktion eines Zustandsautomaten:
2.) Konstruktion eines Zustandsautomaten: Verkettung
3.) Konstruktion eines Zustandsautomaten: oder
4.) Konstruktion eines Automaten: Hüllenbildung
Darstellung des Automaten
|