Compilerbau (3. Teil): Grammatiken und Parser back to frontpage

Die nächsten beiden Teile meiner Compilerbauserie (siehe auch Teil 1: Grundlagen und Teil 2: Sprache und Lexer werden eine der spannendsten. Sie beschäftigen sich damit, wie die Token, die der Lexer produziert hat, gemäß der eigenen “Spielregeln”, der Grammatik, zu einer internen Repräsentation, einem Baum, angeordnet werden. Die erfolgreiche Anwendung der Regeln lassen also eine Aussage darüber zu, ob der gegebene Input, der mittlerweile in einer Liste von Token vorliegt, syntaktisch korrekt ist. Kann der Baum an einer Stelle nicht gebaut werden (zum Beispiel, weil ein anderes Token als das aktuell gelieferte erwartet wurde), wird das Parsing abgebrochen und eine entsprechende Fehlermeldung angezeigt.

Ziel ist es zunächst, eine (überwiegend theoretische, jedoch noch möglichst leicht verständliche) Einführung in Grammatiken und Parserstrukturen zu geben (dieser Teil 3), um danach im Teil 4 eine geeignete Grammatik für Blogmath zu entwerfen. Die Grammatik dient dann der Vorlage für die Entwicklung eines eigenen Parsers, genauer: einem recursive descent parser (ebenfalls Teil 4).

Einführung in kontextfreie Grammatiken

Das Ziel des Parsing ist es, Strukturen im Input zu erkennen und in eine geeignete Datenstruktur, einen Baum, zu überführen. Wie bereits im Post über Lexer ausgeführt, sind reguläre Ausdrücke für die Erkennung von Strukturen gut geeignet. Sie sind jedoch nicht mächtig genug, um eine - diesmal - kontextfreie Sprache (hier: die zu entwickelnde Programmiersprache) zu beschreiben. Ihnen mangelt es an der Möglichkeit beliebig verschachtelter Strukturen, weshalb eine Erweiterung des Konzepts der regulären Grammatiken benötigt wird. Dies führt zum Einsatz kontextfreier Grammatiken.

Eine kontextfreie Grammatik besteht primär aus sogenannten Produktionen. Eine Produktion stellt eine Regel für eine bestimmte Struktur dar.

Ein Beispiel für eine Satzstellung aus der Linguistik ist das folgende:

Satz = Subjekt Verb Objekt

Diese Regel ist jedem bekannt: Eine Regel (von vielen) für den Aufbau eines deutschen (oder englischen) Satzes besteht darin, einem Subjekt ein Verb und dem wiederum ein Objekt folgen zu lassen. Ein Element der von dieser Grammatik erzeugten Sprache wäre folgender Satz:

Der Hund säuft Wasser.

Instinktiv wurden für diesen Beispielsatz die Begriffe der Regel Subjekt, Verb und Objekt durch entsprechende Wörter der deutschen Sprache ersetzt. Schränkt man die Regel wie folgt weiter ein, reduziert sich die Menge möglicher Sätze:

Objekt = "grüne Äpfel" | "Computer"
Verb   = "mag" | "liebt"
Satz   = "Florian" Verb Objekt

(Die Pipe (|) lässt sich mit “oder” übersetzen.) Die von diesem Satz produzierte Sprache ist nun eine Teilmenge der von dem vorigen Beispiel produzierten Sprache und produziert genau folgende Sätze:

Florian mag grüne Äpfel
Florian mag Computer
Florian liebt grüne Äpfel
Florian liebt Computer

Im Rahmen kontextfreier Grammatiken spricht man bei den Elementen, die einer Ersetzung bedürfen, von sogenannten Nichtterminalen (auch Nichtterminalsymbole; im obigen Beispiel also Satz, Verb und Objekt). Endgültige Elemente werden hingegen Terminale (auch Terminalsymbole) genannt (hier also “mag”, “liebt”, “grüne Äpfel”, “Computer” und “Florian”). Eine kontextfreie Grammatik weist stets ein Startsymbol auf (im obigen Fall Satz), von dem eine Ableitung (d. h. eine schrittweise Ersetzung) beginnt. Für kontextfreie Grammatiken gilt: Ein Nichtterminal (linke Seite der Produktion vor dem Gleichheitszeichen) leitet auf eine beliebige Folge von Terminal- und Nichtterminalsymbolen (rechte Seite der Produktion nach dem Gleichheitszeichen) ab. Es war zwar recht intuitiv, jedoch möchte ich die oben angewandte Ersetzungsregel, die auch allgemein für kontextfreie Grammatiken gilt, noch einmal konkretisieren: Ersetzt werden in Produktionen schrittweise auf rechten Seiten stets alle Nichtterminale durch die komplette rechte Seite ihrer jeweiligen Produktion, bis nur noch Nichtterminale übrig sind. Ein Beispiel für “Florian liebt Computer”:

"Florian" Verb Objekt => "Florian" "liebt" Objekt =>
"Florian" "liebt" "Computer"

Denkbar wäre übrigens auch die folgende Ableitung, die denselben Satz produziert:

"Florian" Verb Objekt => "Florian" Verb "Computer" =>
"Florian" "liebt" "Computer"

Je nach dem, von welcher “Seite” aus man beginnt, Nichtterminale zu ersetzen, spricht man zum einen von einer Linksableitung (d.h. von links beginnend) oder einer Rechtsableitung (d. h. von rechts beginnend). Diese Unterscheidung sollte man sich im Hinterkopf behalten, sie wird später bei der Charakterisierung von Parsern eine Rolle spielen. Unabhängig davon, ob eine Links- oder Rechtsableitung durchgeführt wurde, entwickelt sich aus den einzelnen Ableitungen derselbe Ableitungsbaum mit dem Startsymbol als Wurzelknoten, den Terminalsymbolen als Blätter und den Nichtterminalen als innere Knoten:

Ableitungsbaum für den Satz "Florian" "liebt" "Computer"

Produktionen kontextfreier Grammatiken haben auf der linken Seite (links vom Gleichheitszeichen) nur ein Nichtterminal (und sonst nichts) zu stehen. Genau dieser Umstand ist Wortgeber für den Zusatz “kontextfrei”. Es stehen zu jeder Zeit dieselben Produktionen für Ersetzungen zur Verfügung, die ohne Berücksichtigung eines Kontextes angewendet werden können. So kann also das Nichtterminal Objekt stets dort durch die entsprechende rechte Seite der Produktion ersetzt werden, in der es angewandt wird, ohne die Einbettungsumgebung des jeweiligen Nichtterminals zu betrachten.

Alle aus einer kontextfreien Grammatik produzierbaren Wörter (in der theoretischen Informatik bezeichnet man mit “Wort” schlicht eine Zeichenkette) ergeben die kontextfreie Sprache (analog wird eine reguläre Sprache von einem regulären Ausdruck beschrieben und von einer regulären Grammatik erzeugt).

Produktionen können in das sogenannte leere Wort (dargestellt als ɛ [Epsilon]) ableiten. Dies ist eine Zeichenkette der Länge Null und wird zum Beispiel in Produktionen genutzt, die nur optional eingesetzt werden sollen (Beispiel: Parameter einer Funktion). Auf diese Besonderheit komme ich später noch einmal zurück.

Produktionen werden üblicherweise in (Erweiterter) Backus-Naur-Form ([E]BNF) notiert. Diese Notation wurde oben bereits angewandt, ohne explizit darauf hinzuweisen. EBNF liefert als Metasprache einfache Strukturen zur Darstellung der Syntax einer Programmiersprache. Sofern notwendig, werden an gegebener Stelle weitere Elemente der EBNF erläutert. Bereits jetzt ein Hinweis zur Pipe (|)-Benutzung in Produktionen (ein Element der EBNF): Die einzelnen von der Pipe getrennten Optionen können als je eine einzelne Produktion mit demselben linken Nichtterminal notiert werden. In Anlehnung an das obige Beispiel sind also folgende Produktionen zulässig und inhaltlich identisch:

Objekt = "grüne Äpfel"
Objekt = "Computer" 

Reguläre Grammatiken (mit regulären Ausdrücken) sind, wie bereits ausgeführt, ausdrucksschwächer als kontextfreie Grammatiken. Daher ist es nicht verwunderlich, dass man die von einem regulären Ausdruck beschriebene Sprache auch durch eine entsprechende kontextfreie Grammatik erzeugen kann. Dies wird im Folgenden vorgestellt.

Sei folgender regulärer Ausdruck betrachtet, der einen Bezeichner in der gewohnten Definition beschreibt:

[a-zA-Z][a-zA-Z0-9_]*

Die durch diesen Ausdruck beschriebene Sprache wird von folgender kontextfreien Grammatik erzeugt:

Buchstaben = "a" | "b" | "c" | ... | "z"
Buchstaben = "A" | "B" | "C" | ... | "Z"
Zahlen = "0" | "1" | ... | "9"
BuchstabenZahlenUnterstrich = Buchstaben
BuchstabenZahlenUnterstrich = Zahlen
BuchstabenZahlenUnterstrich = "_"
Identifier = Buchstaben Identifier2
Identifier = Buchstaben
Identifier2 = BuchstabenZahlenUnterstrich Identifier2
Identifier2 = BuchstabenZahlenUnterstrich

Nichtterminale sind offensichtlich Buchstaben, Zahlen, BuchstabenZahlenUnterstrich sowie Identifier und Identifier2. Terminalsymbole alle Buchstaben des Alphabets von a bis z in Groß- und Kleinschreibung sowie alle Ziffern und der Unterstrich. Startsymbol ist Identifier. Die erzeugte kontextfreie Sprache ist offenbar die folgende und deckt damit offensichtlich die reguläre Sprache ab, die von dem regulären Ausdruck für Bezeichner beschrieben wird:

{a, b, ..., aa, ab, ac, ..., aA, aB, ... a0, ..., a_, aaa, aaaa, ..., aaaaA, ...}

Identifier2 wurde als Nichtterminal eingeführt, um die Restriktion “zu Beginn nur Buchstaben, danach auch Zahlen und Unterstriche” zu erfüllen.

Der Ableitungsbaum für eine Ableitung auf das Wort “Flo” ist in der nachfolgenden Abbildung dargestellt.

Ableitungsbaum für das Wort "Flo"

Im Kontext von Parsern macht es Sinn, die vom Lexer produzierten Token als Nichtterminale einzusetzen. Denkbar wäre daher zum Beispiel folgender Ausschnitt einer Grammatik für eine Variablendeklaration:

VarDecl = "var" IDENTIFIER "=" Expression ";"

IDENTIFIER ist ein Nichtterminal (Großschreibung signalisiert ein Token). Diese Grammatik könnte daher zum Beispiel folgende Variablendeklaration abdecken (sofern Expression entsprechend definiert ist, zum Beispiel als Ableitung auf NUMBER):

var a = 5;

Ableitung und Ableitungsbaum könnten wie folgt aussehen:

"var" IDENTIFIER "=" Expression ";" =>
"var" IDENTIFIER "=" NUMBER ";"

Ableitungsbaum für eine Variablendeklaration

Auf die Entwicklung einer geeigneten Grammatik für Blogmath komme ich im vierten Teil der Serie noch einmal zurück.

Einführung in Parser

Nachdem nun ein grundlegendes Verständnis für Grammatiken existiert, möchte ich die Techniken eines Parsers skizzieren. Ziel eines Parsers ist es, auf Basis seiner Grammatik und den Token einen Ableitungsbaum zu konstruieren. Dieser Baum (oder ein transformierter) dient den nachgelagerten Phasen als Input.

Der Ableitungsbaum wurde in Teil 1 bereits als konkreter Parsebaum bezeichnet. Es handelt sich hier also zunächst noch nicht um einen abstrakten Syntaxbaum. Ableitungsbäume geben den einzelnen Ableitungsverlauf (= die einzelnen Ersetzungen von Nichtterminalen) in Verbindung mit allen Terminalen (Token) wieder, vergessen jedoch die Reihenfolge, in der diese Ableitungen vorgenommen wurden (Links- oder Rechtsableitung).

Programme, die die konkrete Syntax und Struktur des eingelesenen Quelltextes beibehalten möchten (also zum Beispiel auch Klammern, Semikolons, usw.; beispielsweise notwendig für einen Syntaxhighlighter), werden in späteren Phasen einen konkreten Parsebaum verwenden. Compiler oder Interpreter werden einen (einfacheren) AST bevorzugen, der solche Details nicht mehr abbildet und eine einfachere Struktur zur Verfügung stellt, die sich leichter handhaben lässt.

Der oben vorgestellte Ableitungsbaum für eine Variablendeklaration nimmt, transformiert in einen AST, die folgenden Form an:

Abstrakter Syntaxbaum zu einem konkreten Parsebaum

Parser können auf zwei Weisen Ableitungsbäume konstruieren: über eine Links- oder eine Rechtsableitung. Dementsprechend werden sie unterschieden in Top-down- und Bottom-up-Parser.

Top-down-Parser berechnen Ableitungsbäume von oben (top) nach unten (down). Betrachtet man sich die oben dargestellten Ableitungsbäume wird offensichtlich, dass sie ausgehend vom Startsymbol (der Wurzel) schrittweise Ersetzungen gemäß der Produktionsregeln (den Ableitungen) durchführen (bis zu den Blättern, die die Terminalsymbole darstellen, wie oben bereits erläutert).

Bevor ich auf die die prinzipielle Entwicklung eines Top-down-Parsers eingehe, möchte ich zunächst die Grundprobleme in Bezug auf Grammatiken skizzieren, die während einer Top-down-Analyse auftreten können und für diese entsprechende Lösungsansätze aufzeigen.

Gegeben sei folgender Ausschnitt einer Beispielgrammatik:

ifStatement = IF condition THEN statements
ifStatement = IF condition THEN statements ELSE statements

Condition soll eine beliebig lange Bedingung sein (kann also auch sehr groß und umfangreich verschachtelt sein), statements sollen eine beliebige Anzahl Anweisungen (zum Beispiel Funktionsaufrufe) darstellen. Der Eingangsquelltext kann nur aus einem if-Statement bestehen. Nach dem if-Statement ist das Programm zu Ende.

Die Grammatik ist ein bekanntes Beispiel und als “dangling else”-Problem bekannt (mit Blick auf eine Mehrdeutigkeit in der Grammatik (die es stets zu verhindern gilt!), auf die jedoch hier nicht eingegangen werden soll; siehe auch das sehr einfache Beispiel bei Wikipedia zur Mehrdeutigkeit von Grammatiken).

Angenommen, der Parser ist in der Situation, den folgenden Quelltext gemäß der obigen Grammatik zu parsen:

if (a > 5) and (b < 10) or (c and d and f > 10) then a; b; c; d; e; else f; g; 

Ferner wird angenommen, dass die notwendige lexikalische Analyse (Tokenizing) durchgeführt wurde (nicht explizit dargestellt). Der Parser hat zunächst die Wahl zu treffen, welcher Ersetzungsregel er folgt. Zur Wahl stehen dem Parser die Option 1 ohne “else” und Option 2 mit “else”. Ihm stehen zur Entscheidung mehrere Strategien zur Verfügung.

Die erste denkbare Strategie wäre backtracking (Arbeiten nach trial-and-error). Der Parser probiert die einzelnen Optionen der Reihe nach durch und prüft, ob diese zum Erfolg führen. Hierzu vergleicht er Schritt für Schritt das jeweilige Token gegen das jeweilige Symbol der Grammatik (z. B. wird - wie von der Produktion gefordert - zuallererst ein if-Token erwartet; dies entspricht dem Beispielquelltext). Wählt der Parser also zunächst naiv die erste Option (ohne “else”), stellt er am Ende der Produktion fest (nachdem der Rest erfolgreich mit der Grammatik übereingestimmt hat), dass diese Option die falsche Wahl war. Der Parser hat gemäß Grammatik das Dateiende erwartet, findet jedoch noch abzuarbeitende Tokens (beginnend mit dem else-Token) vor. Alle bis dahin erzeugten Knoten im Ableitungsbaum müssen daher wieder gelöscht und alle bis dahin konsumierten (= verarbeiteten) Tokens auf den Ursprungszustand wiederhergestellt werden (“rollback”).

Rollback beim Backtracking (1. Option)

Im zweiten Anlauf testet der Parser die zweite Option und stellt fest, dass diese zutrifft. Er findet das Dateiende vor, es sind keine weiteren Tokens vorhanden. Ein Ableitungsbaum ist erzeugt.

Der Nachteil dieser Strategie liegt auf der Hand: Der Parser ist gezwungen, ein Management für das Testen von Optionen zu etablieren (d.h. insbesondere muss er in der Lage sein, Rollbacks durchführen zu können). Zudem verbraucht diese Methode, besonders bei größeren Grammatiken und/oder Eingangsquelltexten, besonders viel Rechenleistung. Im Extremfall muss ein Parser zunächst die ganze Datei untersuchen, um festzustellen, dass die gewählte Option die falsche war. Diese Strategie ist daher offensichtlich nicht zu bevorzugen.

Eine zweite überlegenswerte Strategie wäre, auf Basis der nächsten k Token des Tokenstreams eine Entscheidung der zu wählenden Option (mit/ohne “else”) im Voraus zu treffen (sogenanntes predictive parsing / vorausschauendes parsen). Wie das backtracking-Beispiel bereits gezeigt hat, wird dies jedoch im Falle der obigen Grammatik auch fehlschlagen, da k unter Umständen beliebig groß sein muss (da unbekannt ist, wie umfangreich condition und statements sind). Gelänge es jedoch, k sehr klein zu halten (zum Beispiel durch eine Umformung der Grammatik), erscheint diese Strategie recht elegant für die Wahl der Produktionswahl. Neben der offensichtlich zu sparenden Rechenzeit (es müssen nicht mehrere Optionen getestet werden), entfällt das Management für das Rollback. Der Tokenstream kann und muss nur einmal sequentiell durchlaufen werden.

vorausschauender Parser mit k = 6

Wie bereits angedeutet, lässt sich das Problem durch Umformung der Grammatik lösen. Hierzu wird eine sogenannte Linksfaktorisierung eingesetzt, die zunächst am konkreten Beispiel und danach für beliebige Produktionen gezeigt werden soll:

ifStatement   = IF condition THEN statements elseStatement
elseStatement = ELSE statements | ɛ

Die obligatorischen Gemeinsamkeiten beider Produktionen wurden in der Produktion ifStatement “vor die Klammer” gezogen, der else-Teil hingegen als optional gekennzeichnet. Dies wurde erreicht, indem ein neues Nichtterminal elseStatement eingeführt wurde, dass entweder den else-Teil berücksichtigt oder nach ɛ ableitet. Die Ableitung nach ɛ führt dazu, dass elseStatement optional wird. Warum ist das so? Nach der erfolgreichen Abarbeitung der Produktion ifStatement (bis direkt vor elseStatement) kann entweder ein else folgen, oder nichts. ɛ (Epsilon) ist, wie oben bereits erwähnt, als”leeres Wort” (Zeichenkette der Länge Null) definiert. Wie ɛ in einem Parser Berücksichtigung findet, wird noch zu klären sein.

Allgemein lassen sich Grammatiken, die ein solches Problem aufweisen, wie folgt linksfaktorisieren:

A = X | X Y Z

wird zu

A = X B
B = Y Z | ɛ

Ein weiteres Problem in Bezug auf Top-down-Parser und Grammatiken tritt bei folgender Grammatik auf:

E = E + T | T

Ausgehend von der Annahme, dass ein Top-down-Parser stets Linksableitungen ermittelt, würde dieser in eine rekursive Falle abgleiten, da er stets versucht, das erste Nichtterminal der rechten Seite (E) zu ersetzen, das jedoch genau das Nichtterminal ist, an dem er gerade arbeitet (dargestellt in nachfolgender Abbildung).

Endlose Rekursion für den Input "T+T" der fehlerhaften Grammatik

Dieses Problem ist unter dem Begriff Linksrekursion bekannt und kann durch folgende Umformung der Grammatik gelöst werden:

E  = T E'
E' = + T E' | ɛ

Ableitungsbaum für Input "T+T" der um Linksrekursion bereinigten Grammatik

Direkte Linksrekursion (es gibt auch indirekte, wie man sich leicht vor Augen führen kann, wenn man Nichtterminale in die Rekursion “zwischenschaltet”) lässt sich nach folgendem Schema auflösen (entnommen dem Literaturtipp Compilerbau (Teil 1) von Aho/Sethi/Ullmann):

A = Aα_1 | Aα_2 | ... | Aα_n | β_1 | β_2 | ... | β_n

wird transformiert zu

A  = β_1 A' | β_2 A' | ... | β_n A'
A' = α_1 A' | α_2 A' | ... | α_m A' | ɛ

(mit α und β jeweils beliebigen Folgen von Terminalen und Nichtterminalen.)

Wichtigster Vertreter der Top-down-Parser sind sogenannte LL(k)-Parser (das erste L steht für das Lesen der Tokens (= Eingabe) von Links nach rechts; das zweite L steht für die Art der Ableitungen, die LL(k)-Parser ermitteln: Links*ableitungen). Der Parameter *k (der sogenannte Lookahead) gibt an, auf wie viele Tokens der Parser vorausschauen kann, um Entscheidungen bezüglich der Wahl (wenn er denn eine hat) geeigneter Produktionsregeln zu treffen (zum Beispiel LL(1) für eine Vorausschau auf das jeweils nächste Token). Damit entspricht die zuletzt vorgestellte Strategie des vorausschauenden Parsers der eines LL(k)-Parsers. Notwendige Voraussetzung für einen LL(k)-Parser ist eine LL(k)-Grammatik. Eine Grammatik ist offenbar dann eine LL(k)-Grammatik, wenn unter Voraussicht auf die nächsten k Token jeder Ableitungsschritt eindeutig bestimmt ist. Die Linksfaktorisierung und Behebung der Linksrekursion sind, wie sich gezeigt hat, zwei notwendige Schritte zur LL(k)-Grammatik. Wie man prüft, ob eine Grammatik tatsächlich vom Typ LL(k), zeige ich ggfs. in einem späteren Blogpost. Prinzipiell gilt: Je größer k ist, desto mehr Möglichkeiten eröffnen sich für die gewünschte Sprache (= desto mächtiger ist die Sprachklasse), je komplexer ist jedoch auch deren Umsetzung als Parser. Eine LL(k)-Grammatik kann als Teilmenge kontextfreier Grammatiken angesehen werden. Eine durchaus auch in der Praxis zur Anwendung kommende Implementation eines LL(k)-Parsers ist ein recursive descent parser (dt. “rekursiver Abstieg”; beispielsweise ist das C-Frontend des GCC ein handgeschriebener recursive descent parser), dessen Implementation ich im Folgenden exemplarisch vorstellen möchte.

Sei folgende Grammatik für Ausdrücke angenommen (Nichtterminale sind {E, F}, Terminale sind {+, NUM}, Startsymbol ist E):

E = F + E | F
F = NUM

Sie erlaubt zum Beispiel das Parsen des folgenden Ausdrucks:

5 + 2 + 1 + 9 

Die Grammatik ist noch nicht linksfaktorisiert, was jetzt gemäß obiger Regel nachgeholt wird (Produktionen zudem nun nummeriert zur einfachen Referenzierung):

(1) E  = F E'
(2) E' = + E
(3) E' = ɛ
(4) F  = NUM

Der Parser stellt zunächst einmal folgendes Toolset bereit (in Pseudocode):

// next() holt das nächste Token aus dem Tokenstream
var symbol = next(); // enthält global das aktuelle Token
consume() {
    // holt das nächste Token und speichert es ab
    symbol = next();
}
match(t) {
    // prüft, ob ein erwartetes Token mit dem
    // aktuellen übereinstimmt. Falls nicht, Fehler!
    if (symbol != t) error("Syntaxerror");
    consume();
}

Die Idee des rekursiven Abstiegs ist nun, für jedes Nichtterminal eine Funktion zu erzeugen und die jeweils zugehörige rechte Seite des Nichtterminals abzuarbeiten. Terminale werden mit match() konsumiert, für Nichtterminale wird die entsprechende Funktion aufgerufen. Ein Beispiel für die obige Grammatik:

e() { // (1) E  = F E'
    f();
    e'();
}
f() { // (4) F  = NUM
    match(NUM);
}

Diese Funktionen sind trivial. Interessanter hingegen ist die Funktion des Nichtterminals E’. Diese Funktion weist offenbar Optionen auf, d. h. der Parser ist dazu aufgefordert, von seinem Lookahead Gebrauch zu machen und eine Entscheidung zu treffen, welche Produktion (entweder “E’ = + E” oder “E’ = ɛ”) er wählt. Für die erste Produktion fällt die Entscheidung leicht: Diese Option wählt er, wenn das nächste Token ein + ist. Die Menge derjenigen Terminale, die für eine Option infrage kommen, werden als Steuermenge (sogenannte director sets, kurz D) bezeichnet. Es existieren Algorithmen (ggfs. zeige ich ihre Anwendung im Rahmen eines nächsten Blogposts, für diesen ist es jedenfalls genug!), mit denen diese Steuermengen berechnet werden können. D(2) (d. h. die Steuermenge der Produktion 2) ist demnach {+}. Kurzer Nachtrag, da nun die Steuermengen eingeführt sind: Die Berechnung der Steuermengen aller Produktionen ist notwendig, um sicherzustellen, dass eine Grammatik eine LL(k)-Grammatik ist (genauer: Steuermengen der Produktionen eines Nichtterminals müssen disjunkt sein). Wie aber bereits erwähnt, obliegt dies ggfs. späteren Blogposts.

Wie sieht jedoch die Steuermenge für eine Ableitung nach Epsilon, also D(3), aus? In solchen Fällen ist die Grammatik an den Stellen zu untersuchen, an denen das Nichtterminal (hier E’) auf rechten Seiten in Produktionen eingesetzt wird. Alle Terminale, die nach dem eingesetzten Nichtterminal auftreten, gehören zur Steuermenge (was ja auch logisch ist: Man sucht die Symbole, die auf E’ folgen können, da E’ im Fall der Produktion 3 eine “leere Zeichenkette” darstellt). Dies ist offensichtlich nur in E = F E’ der Fall. Es existiert ein besonderes Symbol, das das Ende eines Dokuments signalisiert: $ (Dollarzeichen). D(3) ist demnach {$}.

Auf Basis der Steuermengen wird jetzt in der Nichtterminalfunktion eine Fallunterscheidung für jede einzelne Option wie folgt vorgenommen.

 e'() {
    if symbol in {+} { // (2) E' = + E
        match(+);
        e();
    } else if symbol in {$} { // (3) E' = ɛ
        // Dokumentenende, nichts tun.
    } else error("Syntaxerror");
} 

Da das Startsymbol der Grammatik als E definiert ist, muss der Parser-Prozess die Funktion des Nichtterminals E aufrufen. Mit jedem Aufruf der Nichtterminal- und Matchfunktionen könnte man nun den Aufbau einer internen Baumstruktur verknüpfen. Dies wird unter anderem Gegenstand des nächsten Blogposts sein. Die folgende Grafik zeigt den Ableitungsbaum sowie die jeweiligen Funktionsaufrufe des oben implementierten recursive descent parsers für den Ausdruck 5 + 2.

Ableitungsbaum und Visualisierung der Funktionsaufrufe für den Ausdruck "5+2"

Diese Einführung in Top-down-Parser im Allgemeinen und LL(k)-Parsern mit recursive descent parsern im Speziellen soll an dieser Stelle genügen. Die Berechnung von Steuermengen ist ein Thema, das im Zuge der Erstellung eigener Grammatiken in jedem Fall noch einmal auftauchen wird. Ob ich die Mengen nur durch “rhythmisches Hinsehen” ermitteln werde oder explizit aufzeige, wie die entsprechenden Algorithmen zur Ermittlung anzuwenden sind, werde ich mit dem Schreiben des nächsten Posts entscheiden. Bis dahin steht es dem interessierten Leser frei, sich bereits jetzt mit der Theorie dahinter auf der entsprechenden Wikipedia-Seite zu beschäftigen (und diesbezüglich gerne Fragen in den Kommentaren zu stellen!). :-)

Ich habe jetzt bereits die Funktionsweise eines Top-down-Parsers hinreichend skizziert. Da Bottom-up-Parser in der “händischen” Praxis eine untergeordnete Rolle spielen (und vielmehr von sogenannten Parsergeneratoren, wie zum Beispiel yacc, automatisch erzeugt werden), möchte ich zu diesen nur folgendes anmerken: Bottom-up-Parser erzeugen (gegensätzlich zu Top-down-Parsern) einen Ableitungsbaum ausgehend von syntaktisch kleineren Strukturen (bottom) hin zu größeren Strukturen (up), bis sie beim Startsymbol der Grammatik angelangt sind. Die wichtigsten Unterklassen dieser Parser sind zum einen die LR(k)-Parser (von L*inks nach Rechts lesen, *R*echtsableitungen erzeugen, Vorausschau auf die nächsten *k Token) und zum anderen die Operatorpräzedenzparser, die auf Basis einer definierten Präzedenz zwischen allen vorkommenden Operatoren Ableitungsbäume konstruieren. Bottom-up-Parser berechnen Rechtsreduktionen (umgedrehte Rechtsableitungen). Für ein kleines Beispiel verweise ich auf die entsprechende Wikipedia-Seite. Wenn Interesse besteht, werde ich gegebenenfalls den Bottom-up-Parsern auch einen ausführlicheren Blogpost widmen.

Ich hoffe, ich konnte in aller Kürze und Knappheit die Grundlagen von kontextfreien Grammatiken, Top-down-Parsern und die Umsetzung in recursive descent parser verständlich erklären. Im nächsten Blogpost werde ich für Blogmath eine geeignete Grammatik entwickeln und einen recursive descent parser in Python entwickeln. Falls sich beim Lesen Fragen ergeben haben, wie immer: Kommentar schreiben. :-) Vielen Dank für’s Lesen. Bis dahin!


New comment

Comments are moderated and therefore are not published instantly.





Comments

No comments yet. Be the first! :-)