Kaum ein anderer Vorgang ist in der Programmierung so allgegenwärtig wie das Parsen, das Einlesen und Verarbeiten von Informationen in Textform. Ob es der Quelltext einer Internetseite im Browser, eine Formel oder die gespeicherten Einstellungen unserer Anwendung sind: Alles, von einer schlichten Zahl, die die Benutzer eingibt, bis hin zu riesigen Sourcecodes komplexer Programmiersprachen, ist textuelle Information, die nun irgendwie in eine für den Computer nutzbare Form übersetzt werden muss. Im Weiteren geht es nun um Ansätze und Tricks, solche Parser effizient zu entwickeln.

Mit freundlichen Grüßen,
Dario Stein

Inhalt

	Konventionelle Mittel
	Reguläre Ausdrücke
	Sprache und Grammatik
	Parsergeneratoren und Grammatiken
	Grober Ablauf beim Parsen
	Parser schreiben mit Coco/R
	Die erste Grammatik
	Taschenrechner
	Aktiver Code
	Taschenrechner, die letzte
	Coco/R in Projekten einsetzen
	Schlusswort
	Downloads und Links

Wie schon gesagt kann selbst eine Benutzereingabe auf der Konsole schon als Anwendungsfall von Parsern betrachtet werden: Klar - Die Eingabe "2.5" besteht zunächst ja nur aus drei unscheinbaren Zeichen. Erst durch eine entsprechende Funktion wird daraus eine Speicher-Repräsentation der Kommazahl 2,5. In .NET heißt diese passenderweise Double.Parse.

Kleine Rekapitulation: Funktionen, die wir beim Parsing oft und gerne einsetzen, sind die grundlegende String-Manipulationen.

Dim Eingabe       = "{ 1, 2, 3 }"
Dim Mittelteil    = Eingabe.Substring(1, Eingabe.Length - 2)
Dim Ergebnisliste = From Teil In Mittelteil.Split(","c) _
                    Select Integer.Parse(Teil.Trim())

Listing 1: Grundlegende String-Verarbeitung

Also weiter zum nächsten Schritt: XML-Attribute auslesen:

<person name="Max" nachname="Mustermann">
    <auto index="1">...</auto>
    <auto index="2">...</auto>
</person>

Wie vorgehen? An den öffnenden spitzen Klammern splitten und die schließenden durchzählen. Dann alles mit Schrägstrich weglassen und nochmal an den Gleichheitszeichen splitten? Eh ... Man sieht, so kommt man nicht weiter - Ein mächtigerer, strukturierterer Mechanismus muss her.

Zum Glück existieren mittlerweile für die meisten Programmiersprachen Implementierungen eines verbreiteten und sehr nützlichen Konstrukts: Des Regulären Ausdrucks (RegEx). So ein RegEx ist eine etwas kryptisch aussehende Zeichenfolge, die ein Muster für Zeichenfolgen darstellt. So passt beispielsweise das Muster

\d{1, 3}

auf alle maximal dreistelligen Zahlen.
Das obige Problem lässt sich somit folgendermaßen formulieren:

For Each Tag As Match In Regex.Matches(Eingabe, "<\w+? ([^>]+?)>")
    Dim Attribs = Tag.Groups(1).Value
    For Each attrib As Match In Regex.Matches(Attribs, "(\w+?)=" & """" & "(\w+?)" & """")
        Console.WriteLine("{0} -> {1}", attrib.Groups(1).Value, attrib.Groups(2).Value)
    Next
Next

Listing 2: Parsen mit Regulären Ausdrücken

Tatsächlich lassen sich eine ganze Menge von Parsern durch die üblichen String-Funktionen und Reguläre Ausdrücke ausreichend beschreiben. Aber für komplexere Probleme benötigt man, wie wir sehen werden, noch mächtigere Techniken.

Dies führt uns zu dem trivial aussehenden Problem, dass uns den nächsten Teil dieses Artikels begleiten wird: Einem Taschenrechner . Die Spezifikation ist dabei einfach: Wir tippen in der Konsole einen arithmetischen Ausdruck wie 3 * (2 + 1) ein und das Programm soll diesen ausrechnen.

Ironischerweise ist dieser unscheinbare Parser mit bisherigen Mitteln eine große Herausforderung. Probieren sich sich doch einmal daran - versuchen sie zum Beispiel, einen Regulären Ausdruck für einen solchen Term zu schreiben. Es funktioniert schlichtweg nicht! Mit anderen elementaren Mitteln der Stringverarbeitung ist eine Lösung natürlich möglich, aber sehr kompliziert - sehen sie sich dazu beispielsweise  Einfache arithmetische Ausdrücke auswerten [Tipp 703] an. Soetwas wie verlinkte Code erfordert schon ein hohes Maß an Können und hat nichtsdestotrotz einen hohen Umfang: 250 Zeilen in diesem Beispiel.

Das kann es doch irgendwie nicht sein? Wenn schon so eine Menge Code für einen Nullachtfünfzehn-Matheausdruck drauf geht, wie sollen wir dann erst eine Programmiersprache schreiben?

Nehmen wir einmal die Idee der Regulären Ausdrücke als Basis: Was ist eigentlich geschehen? Ein RegEx definiert ein Muster für Text-Eingaben. Der Ausdruck

a

passt einzig auf die Eingabe a. Spannender ist hier

a(b*)

Auf einmal ist Wiederholung drin und schon sieht die mögliche Eingabemenge anders aus:

a
ab
abb
abbbb
abbbbbbbbbbbbbbbbbbbbbbb
.......

Was hier vorliegt, ist höchst interessant. Wir haben es mit einem Regulären Ausdruck geschafft, eine Beschreibung für eine unendlich große Menge von möglichen Eingaben gegeben. Und dieser Ausdruck ist wohlgemerkt endlich, sogar ziemlich klein.

Diese Menge möglicher Eingaben nennen wir ab jetzt Sprache , und die Menge von Wörtern dieser Sprache ist abzählbar unendlich groß. Wir haben es allerdings geschafft, alle diese Wörter der Sprache mit einer endlichen Bildungsvorschrift zu beschreiben. Und eine Bildungsvorschrift für Sprachen kennen wir schon aus der Schule, z.B. dem Deutsch- oder Lateinunterricht: Die Grammatik .

Violà - Das ist unsere Erkenntnis: Ein Regulärer Ausdruck ist eine einfache Form von Grammatik, mit der wir Sprachen beschreiben können, nämlich die Sprache aus all den Wörtern, die auf das entsprechende Muster passen. Und was sind noch alles Sprachen? Na alles, jede Form von Eingabe, die es zu parsen gilt : Unsere Terme, Programmiersprachen, Deutsch, Englisch ... Sie alle können in der obigen Ausdrucksweise zusammengefasst werden. Um also Parsing verstehen zu können, müssen wir Sprachen verstehen.

Nach einer kleinen Verschnaufspause geht es zur nächsten Feststellung. Am Beispiel des arithmetischen Terms haben wir festgestellt, dass wir dort mit Regulären Ausdrücken nicht so recht weiterkommen. Mit unserem neu gewonnenen Wortschatz können wir das auch so bezeichnen: Die Sprache der arithmetischen Terme ist mit Regulären Ausdrücken als Grammatik nicht beschreibbar.

Wir müssen also feststellen, dass Sprachen offenbar über verschiedene Schwierigkeitsstufen verfügen. Unsere abbbbb-Sprache ist in dieser Hierarchie offenbar niedriger angesiedelt als die Terme. Und genau hier liegt, um auf das vorige Kapitel zurückzukommen, unsere Hoffnung, doch noch unseren Taschenrechner und irgendwann die weltbewegende Programmiersprache schreiben zu können: Wenn uns Reguläre Ausdrücke für die Beschreibung unserer Sprache nicht reichen, dann brauchen wir einfach eine mächtigere Form der Grammatik.

Die Hierarchie der Sprachen und Grammatiken, die ich oben eingeführt habe, trägt den Namen Chomsky-Hierarchie. Auf der untersten Stufe stehen die sog. regulären Sprachen, also jene, die durch Reguläre Ausdrücke beschrieben werden können (daher kommt auch das ominöse regulär). Da uns diese Stufe offenbar für unsere astronomischen Ziele mit dem Taschenrechner nicht ausreicht, erklimmen wir die nächsthöhere: Kontextfreie Sprachen.

Zu solchen kontextfreien Sprachen zählen zum Glück die meisten Programmiersprachen und damit auch die arithmetischen Terme. Mit kontextfreien Grammatiken haben wir also endlich das Mittel unserer Wünsche gefunden.

Nach der ganzen, gewiss spannenden Theorie wird der folgende Teil nun etwas interaktiver. Bevor wir nämlich Grammatiken zu schreiben beginnen, bespreche ich den nächsten Schritt vorweg. Was tun wir mit einem Regulären Ausdruck? Wir geben ihn an eine Regular Expression Engine (wie die des .NET-Framworks) und diese ... klar, sie parst ihn. Und dann berechnet sie selbst die Funktionen, um dem Ausdruck entsprechend Eingaben verarbeiten zu können. Das heißt, wir haben eine Grammatik und geben diese in ein Programm, das daraus ein weiteres Programm schreibt. Und bei dem, was jetzt kommt, ist das wörtlich zu nehmen: Ein Parsergenerator .

Parsergeneratoren (im Englischen compiler compiler) sind nichts als Programme, die eine in unserem Falle kontextfreie Grammatik entgegennehmen und daraus automatisch den kompletten Quellcode eines Parsers in unserer gewünschten Programmiersprache generieren.

Der interne Ablauf beim Parsen erfolgt (grob dargestellt) in zwei Schritten. Schritt 1 ist das sog. Lexing , in dem der Eingabezeichenstrom von einem sog. Scanner in kleine zusammenhängende sinnvolle Bestandteile ( Tokens ) zerhackt wird. Für den arithmetischen Ausdruck 332 * (22 + 1) würden die Tokens beispielsweise derartig ermittelt:

Tabelle 1: Token-Zerlegung eines arithmetischen Ausdrucks

Im 2. Schritt kommt der eigentliche Parser ins Spiel, der diese "Wörter" zu einem sinnvollen Satz zusammenbaut. Dabei entsteht gewöhnlich ein Parsebaum bzw. ein sog. Abstrakter Syntaxbaum, der die Beziehungen zwischen den entstandenenen Teilen repräsentiert. Unser Term könnte somit in dieser Weise als Baumstruktur repräsentiert werden:

Abbildung 1: Syntaxbaum eines arithmetischen Ausdrucks

Hiermit haben wir eine perfekte interne Darstellung des Terms (z.B. durch Klassen/Zeiger) im Speicher. Je nachdem, was wir für ein Programm schreiben, kann das nun ausgerechnet (Rechner), beantwortet (Sprach-Interaktion) oder interpretiert/kompiliert werden, wenn es um Programmiersprachen geht. Also an die Arbeit.

Es existieren zahllose Parsergeneratoren für die verschiedensten Ziel-Programmiersprachen. Ich werde hier Coco/R verwenden, ein kleiner aber feiner Parsergenerator, der an der Universität von Linz entwickelt wurde und, wie ich finde, sehr leicht zu handhaben ist. Er ist kostenlos verfügbar und existiert in Varianten für die meisten gängigen Programmiersprachen. Aufgrund seiner knappen Syntax werde ich hier die C#-Version verwenden, für VB, Ruby etc. funktioniert das Programm allerdings ähnlich.

Die Verwendung ist denkbar einfach. Beim Download erhält man drei Dateien - Coco.exe, Scanner.frame und Parser.frame. Nun schreibt man irgendwo hin eine Datei mit der Erweiterung .atg (Attributed Grammar), die die gewünschte Grammatik enthält, und zieht diese auf coco.exe. Coco wird das dann kommentieren (Fehlerausgaben etc.) und wenn alles glatt geht erhalten wir eine Scanner.cs und Parser.cs, die die beiden von uns gewünschten Komponenten benutzungsfertig enthalten.

Worauf genau geachtet werden muss werde ich am Ende des Artikels noch einmal zusammenfassen. Bis dahin können wir aber das kleine Programm Coco/Interactive verwenden, dass den gesamten Dateihaushalt mitsamt Kompilation automatisch abwickelt und uns bequeme und v.A. interaktive erste Schritte ermöglicht.

Zuerstmal muss das Programm heruntergeladen und gestartet werden (als Quellcode oder ausführbar - Alle benötigten Komponenten sind enthalten). Im entstehenden Fenster wird links die gewünschte Grammatik eingegeben und mit F9 kompiliert. Rechts unten kann dann eine Eingabe gemacht werden, die automatisch geparst und deren Ergebnis ausgegeben werden.

Grammatiken wie Coco/R sie verwendet werden durch eine Meta-Sprache, die sog. "Erweiterte Backus-Naur-Form" (EBNF) notiert. Ich werde einfach mal mit einem hoffentlich aussagekräftigen Beispiel vorangehen:

COMPILER Example
PRODUCTIONS
    Example = "Hello".
END Example.

Listing 3: Die erste Grammatik

Wenn wir das interaktiv ausführen und mit ein paar Eingaben testen, erhalten wir so eine Ausgabe:

Abbildung 2: Erste Interaktivausgabe

Die Eingabe "Hello" wird vom Parser angenommen, "xyz" wird mit Fehlermeldung abgewiesen.

So, nun die Erklärung im Detail: In der ersten und letzten Zeile geben wir dem zu erstellenden Parser ("Compiler") nur einen Namen, was in unserem Falle irrelevant ist. Das wirklich entscheidende unserer Grammatik sind die sog. Produktionen . Der Parse-Vorgang startet immer bei der Initialproduktion , hier Example, die den Namen des Compilers trägt. Die folgenden Regeln sind einfach: Eine Eingabe gehört zur definierten Sprache, wenn sie sich irgendwie durch Ersetzungen der Produktionen herstellen lässt. Die einzige Eingabe, die sich hier durch Ersetzung von Example herstellen lässt, ist "Hello".

Leerzeichen oder Zeilenumbrüche in der Grammatik keine Rolle, Produktionen werden immer großgeschrieben und wie alle anderen Deklarationen mit einem Punkt beendet. Nun geht es darum, Ausdrücke zu kombinieren, wofür in EBNF u.A. folgende Notationen vorgesehen sind:

Tabelle 2: EBNF-Syntaxelemente

Damit lässt sich die "abbbb-Sprache" leicht in unserer neuen Grammatik-Form schreiben:

COMPILER Example
PRODUCTIONS
    Example = "a" { "b" }.
END Example.

Listing 4: Abbbb-Sprache als kontextfreie Grammatik

Mit diesem Wissen geht es jetzt stark in Richtung Taschenrechner.

Als ersten neuen Punkt führen wir Zeichendefinitionen ( Characters ) ein, also Bezeichner für die kleinsten Datenbausteine. Wir arbeiten hier mit Zahlen und deren kleinste Bestandteile sind Ziffern (Digits):

COMPILER Expr
CHARACTERS
     digit = '0'..'9'.
END Expr.

Listing 5: Eine Zeichenklasse für Ziffern definieren

Solche Zeichenmengen werden klein geschrieben und können auf verschiedene Weise gebildet und kombiniert werden, z.B. mit dem Bereichsoperator (..), als einfacher String oder mit Plus und Minus (Vereinigung/Differenz). Ein weiteres Beispiel für ein paar Zeichemengen:

digit    = "0123456789".
hexDigit = digit + "ABCDEF".
letter   = 'A' .. 'Z'.
eol      = '\r'.
noDigit  = ANY - digit.

Als nächstes spezifizieren wir zusammenhängende Einheiten ( Tokens ) als Verbund von Characters. Eine Zahl besteht aus mindestens einer Ziffer:

COMPILER Expr
CHARACTERS
     digit = '0'..'9'.
TOKENS
     number = digit { digit }.
END Expr.

Listing 6: Token-Deklarationen

Genau genommen steht dort nun: Eine Zahl besteht aus einer ersten Ziffer und beliebig vielen folgenden. Ein solches Token tritt in der weiteren Verarbeitung immer als zusammenhängende, also nicht weiter zerlegte Einheit (Terminalsymbol) auf.

Und jetzt können wir mit den Produktionen loslegen. Das gestaltet sich erstaunlich einfach. Lassen wir Punktrechnung erstmal außen vor und betrachten Terme wie:

1 - 2 - 3 + 4

Das könnten wir doch so beschreiben, dass eine Zahl vorkommt und dann ggf. immer wieder ein Rechenzeichen mit einer nächsten Zahl.

COMPILER Expr
CHARACTERS
     digit = '0'..'9'.
TOKENS
     number = digit { digit }.
PRODUCTIONS
       Expr = number { ("+" | "-") number }.
END Expr.

Listing 7: Rechnungen mit Plus und Minus beschreiben

Damit sind solche Ausdrücke grammatikalisch beschrieben. Jetzt beziehen wir in diese Überlegung die Punktrechnung mit ein:

1 * 2 * 3 + 2 + 3 / 4

Wir sehen: Unser Ausdruck mit allen Operatoren ist im Grunde eine Menge aus Produkten (Punktrechnungen), zwischen denen wiederum Plus oder Minus steht.

COMPILER Expr
CHARACTERS
        digit = '0'..'9'.
TOKENS
     number = digit { digit }.
PRODUCTIONS
       Expr = Prod { ("+" | "-") Prod }.
       ...
END Expr.

Listing 8: Punktrechnungen mitdefinieren

Ein Ausdruck ist also immer ein Produkt und ggf. viele weitere mit Rechenzeichen dazwischen. Ein Produkt können wir in genau der selben Weise weiter zerlegen. Ein Produkt ist eine Menge aus Faktoren, zwischen denen Mal oder Geteilt stehen. Ein Faktor ist eine einfache Zahl oder ein geklammerter Ausdruck.

COMPILER Expr
CHARACTERS
     digit = '0'..'9'.
TOKENS
     number = digit { digit }.
PRODUCTIONS
       Expr = Prod { ("+" | "-") Prod }.
       Prod = Fact { ("*" | "/") Fact }.
       Fact = number | "(" Expr ")".
END Expr.

Listing 9: Vollständige Grammatik

Das war's! Die komplette Grammatik für arithmetische Ausdrücke. Der Parser ist übrigens vollständig rekursiv, Verschachtelung von Ausdrücken ist daher kein Problem.

Prüfen, ob's stimmt:

Abbildung 3: Arithmetische Ausdrücke getestet

Verdächtig korrekt ;) Alle richtigen Ausdrücke werden vom Parser angenommen, alle falschen zurückgewiesen. Für motivierte Leser stelle ich einfach mal die Übung in den Raum, einen Potenzoperator oder eine Funktionssyntax wie sin(x) einzubauen.

Eines fehlt jetzt noch: Wie kommen wir an den berechneten Wert? Die Vorgehensweise ist wieder einfach: Jede Produktion kann mit C#-Code (oder VB, je nachdem welche Sprache verwendet wird) angereichert werden, der während des Parsens ausgeführt wird. Dieser Code, auch semantische Aktion genannt, wird in (. .) gefasst und vom Generator einfach an die entsprechenden Stellen im generierten Parser kopiert. Beispiel:

COMPILER Foo
PRODUCTIONS
       Foo =   "Hallo" (. c("Hallo ebenso"); .)
             | "Welt"  (. c("Du Trottel, erst kommt das Hallo"); .).
END Foo.

Listing 10: Semantische Aktionen

Dieser Grammatik beschreibt eine Sprache, die nur die Wörter "Hallo" und "Welt" kennt. Je nach Eingabe wird aber der angegebene C#-Code ausgeführt (Die c-Funktion ist eigentlich kein Teil von Coco/R, sondern von mir eingefügt worden, um Text im Interaktivfenster auszugeben). Man sieht:

Abbildung 4: Action!

Was jetzt zum Berechnen nur noch fehlt, ist eine Möglichkeit, dass Produktionen miteinander kommunizieren. Dazu gibt es Attribute . Sie stehen in spitzen Klammern und funktionieren wie normale Funktionsparameter der Zielsprache. Sie werden vom Generator ebenfalls einfach in den Ziel-Code kopiert - man kann sie sozusagen als Parameter einer Produktion auffassen. Werden hier Referenzwerte angegeben, gibt dies uns die Möglichkeit, Rückgabewerte für Produktionen zu formulieren.

COMPILER Foo
PRODUCTIONS
        Foo = (. string Ausgabe; .)
              HalloMatchen<out Ausgabe>
              (. c("Die Funktion sagt: " + Ausgabe); .).

        HalloMatchen<out string res> = "Hallo" (. res = "Na toll ..."; .).
END Foo.

Listing 11: Semantische Aktionen

Und tatsächlich erhalten wir die Ausgabe:

> Hallo
Die Funktion sagt: Na toll ...

Foo deklariert in der ersten Aktion also zunächst eine String-Variable, um in dieser die Ausgabe von HalloMatchen aufzunehmen. Darauf folgt die eigentliche Produktion, der eine Referenz auf diese Variable übergeben wird, und schließlich wird die Rückgabe in der letzten Aktion ausgegeben. Innerhalb von HalloMatchen kann dieser Ausgabeparameter innerhalb einer Aktion normal beschrieben werden.

So. Jetzt müssen wir diese Techiken nur noch mit unserer Grammatik kombinieren und fertig ist das Programm:

COMPILER Expr
CHARACTERS
    digit = '0'..'9'.
TOKENS
        number = digit { digit }.
PRODUCTIONS
       Expr = (. int res = 0; .)
              Plus<ref res>
              (. c(res.ToString()); .)
       .

       Plus<ref int a> = (. int b = 0; .)
                         Prod<ref a> { 
                               "+" Prod<ref b> (. a += b; .)
                             | "-" Prod<ref b> (. a -= b; .) }
       .

       Prod<ref int a> = (. int b = 0; .)
                         Fact<ref a> { 
                               "*" Fact<ref b> (. a *= b; .)
                             | "/" Fact<ref b> (. a = (int)((double)a / (double)b); .) }
       .

    Fact<ref int a> = Number<ref a> | "(" Plus<ref a> ")".
    Number<ref int a> = number (. a = int.Parse(t.val); .).
END Expr.

Listing 12: Der fertige Taschenrechner

Die Grammatikdefinition ist die selbe wie beim ersten Taschenrechner-Beispiel (es wurden zwecks Übersichtlichkeit nur zwei neue Produktionen eingeführt). Was sich geändert hat ist, dass alle Produktionen mit Außnahme der obersten jetzt einen Ausgabeparameter für ihr berechnetes Ergebnis haben. In den Produktionen für die einzelnen Terme wird eine lokale Variable (b) generiert, die das Ergebnis der folgenden Produktionen aufnimmt und die mit dem aktuellen Ergebnis verrechnet wieder ausgegeben wird.

Noch neu ist die Aktion in der letzten Produktion Number. Die Variable t ist hier vom Parsergenerator gestellt und gibt immer das aktuelle Token an - in diesem Fall also die Zahl, die Number gerade parst. Das abschließende Beweisfoto und unser Taschenrechner ist endlich fertig:

Abbildung 5: Unser Taschenrechner in Aktion

Bis jetzt haben wir einiges geschafft! Allerdings haben wir bis jetzt aber nur unseren Code in der leidigen Interaktivkonsole testen können. Jetzt geht es noch darum, den erstellten Parsergenerator in ein richtiges Projekt einzubauen. Davon legen wir ersteinmal ein neues an, nennen wir es ParserTest und speichern es. Nun kopieren wir coco.exe und seine beiden .frame-Dateien in den Ordner, in dem die übrigen Code-Dateien des Projektes ansässig sind, und legen die gewünschte Grammatik-Datei an.

In Taschenrechner.atg kommt unser Code und jetzt muss nichts weiter getan werden, als coco.exe diese Datei in der Kommandozeile zu übergeben. Das kann man tun, indem man sie einfach auf coco.exe zieht, oder indem man im Befehlsfenster (Start->Ausführen->cmd.exe) beide Dateien hintereinander auf die schwarze Fläche zieht und Enter drückt.

Als Ausgabe wird Coco uns auf etwaige Fehler in der Grammatik hinweisen oder andernfalls, wie schon gesagt, Scanner.cs und Parser.cs im aktuellen Ordner generieren. Diese beiden Quellcodedateien müssen wir nun unserem Projekt hinzufügen (Projekt -> Hinzufügen -> Vorhandenes Element). Darin definiert sind zwei Klassen - Scanner und Parser. Im Konstruktor erwartet der Parser einen Scanner und der Scanner einen zu verarbeitenden Datenstrom oder einen Dateinamen. Über die Parser-Klasse können wir den kompletten Parse-Vorgang steuern und auch gefundene Fehler abfragen.

Ein beispielhafter Aufruf sieht daher so aus:

using System;
using System.IO;

class Program {
    static void Main(string[] args) {
        var Input = Console.ReadLine();

        using (MemoryStream Memo = new System.IO.MemoryStream(System.Text.Encoding.UTF8.GetBytes(Input))) {
            Scanner Scanner = new Scanner(Memo);
            Parser Parser = new Parser(Scanner);
            Parser.Parse();
            Console.WriteLine("{0} Fehler gefunden", Parser.errors.count);
        }
    }
}

Listing 13: Verwendung des generierten Parsers aus C#

Um den Taschenrechner kompilieren zu können, müssen wir noch eine Rückgabemöglichkeit für das Ergebnis einrichten (Bitte achten Sie darauf, dass Sie die ursprünglichen Frame-Dateien und nicht jene aus der Interaktivkonsole weiterverwenden, dort sind Funktionen definiert, die in normalen Projekten nicht existieren). Dazu können wir im Kopf der Grammatikdeklaration eine öffentliche Rückgabevariable der Parser-Klasse einführen und diese direkt zuweisen. Damit lautet die atg-Datei folgendermaßen:

COMPILER Expr
        public int result = 0;
CHARACTERS
        digit = '0'..'9'.
TOKENS
        number = digit { digit }.
PRODUCTIONS
       Expr = Plus<ref result>.

       <Weiter wie gehabt ...>
END Expr.

Listing 14: Rückgabevariablen im Parser

Und nachdem daraus die Dateien neu generiert wurden, kann man die Hauptfunktion so schreiben:

using System;
using System.IO;

public static class Program {
    static void Main(string[] args) {
        var Input = Console.ReadLine();

        using (MemoryStream Memo = new System.IO.MemoryStream(System.Text.Encoding.UTF8.GetBytes(Input))) {
            Scanner Scanner = new Scanner(Memo);
            Parser Parser = new Parser(Scanner);
            Parser.Parse();
            Console.WriteLine("{0} = {1}", Input, Parser.result);
        }

        Console.ReadKey();
    }
}

Listing 15: Fertige C#-Anwendung

Ich hoffe sehr, dass ich Sie für dieses Thema begeistern und zum Experimentieren anregen konnte. Was nach viel aussieht, ist letzendlich nur eine Frage der Eingewöhnung und dann stehen einem ungeahnte Möglichkeiten zur Verfügung, komplizierte Parser so einfach wie nie zu formulieren. Vielleicht schaffe ich demnächst einen Folgeartikel, in dem eine kleine Programmiersprache formuliert wird.

Aber natürlich ist mit dieser Einführung nur an der Oberfläche der Fähigkeiten von Parsergeneratioren gekratzt. Wer sich weitergehend informieren möchte, kann das z.B. mit dem unter den Download-Links angegebenen Lehr-Dokument zu Coco/R tun, in dem auch eine Mini-Programmiersprache geschrieben wird.

Was übrigens die Interaktivkonsole angeht: Sie ist auch nur ein erster Versuch meinerseits, interaktiv Grammatiken auszuwerten und enthält natürlich noch massiv Verbesserungspotenzial. Wer möchte, kann gerne dran herumschrauben und uns eine verbesserte neue Version anbieten (Auch sei an dieser Stelle auf Fabian hingewiesen, der mir sein Syntaxhervorhebungs-Steuerelement aus diesem Thread freundlicherweise zur Verfügung gestellt hat).

Vielen Dank und bis zum 2. Teil.

Links

1. Offizielle Coco/R-Website mit Downloads
2. Offizielles Coco/R-Tutorial

Weitere Parsergeneratoren

1. ANTLRWorks - Kostenloser Parsergenerator mit IDE
2. GOLD - Kostenloser Parsergenerator mit IDE und hoher Sprachvielfalt (Auch VB6)

Downloads

Coco/Interactive

Coco/Interactive [VB.NET - Quellcode]

Beispielprojekt dieses Tutorials