Die Klasse Parser stellt die (abstrakte) Basisklasse für alle Parser und Compiler dar. Die Methode startSymbol, die in der Methode compile aufgerufen wird, muss in einer abgeleiteten Klasse implementiert werden.
Ein konkreter Parser wird anhand einer Grammatik nach der Recursive-Descent-Methode geschrieben. Hierzu wird eine konkrete Parser-Klasse erstellt, die von der Klasse Parser abgeleitet wird. In der konkreten Klasse muss die Methode startSymbol implementiert sein.
Als Beispiel betrachten wir folgende Grammatik:
S | aSb | ε |
Die Grammatik erzeugt die Sprache { anbn | n ∈ ℕ0 }.
In der Methode startSymbol wird das Startsymbol der Grammatik, hier S, aufgerufen.
Mit folgenden Anweisungen wird ein Objekt vom Typ ParserAnbn erzeugt und anschließend das Wort aabb analysiert.
Während ein Parser nur die Syntax prüft, übersetzt ein Compiler zusätzlich den Eingabestring in einen Wert. Dieser Wert kann eine Zahl sein, ebenfalls wieder ein String, oder ein beliebiges Objekt.
Der folgende Compiler übersetzt logische Formeln, die aus den Konstanten 0 und 1 sowie den Operanden +, * und ! gebildet sind, in einen Wahrheitswert. Hierbei stehen 0 und 1 für die Wahrheitswerte False und True; die Operatoren +, * und ! stehen für die logischen Verknüpfungen Oder, Und und Nicht. Die Auswertungsreihenfolge kann durch Klammern gesteuert werden; zusätzlich gilt: Der Operator ! bindet am stärksten, der Operator * am zweitstärksten, und der Operator + bindet am schwächsten (Punktrechnung geht vor Strichrechnung).
Die entsprechende Grammatik ist folgende:
expr | term (+ term)* | |
term | factor (* factor)* | |
factor | ! factor | ( expr ) | literal | |
literal | 0 | 1 |
Aus der Grammatik ergibt sich folgender Recursive-Descent-Übersetzer:
Mit folgenden Anweisungen wird ein Objekt vom Typ CompilerLogic erzeugt und anschließend das Wort 0+!0*1+!0 analysiert.