InterpreterDemo

In letzter Zeit hab ich mich ein bisschen mit Design Patterns beschäftigt. Dabei bin ich auch auf das Interpreter-Pattern gestoßen. Und da ich Parser ebenfalls interessant finde und eh mal ein bisschen C++ wiederholen musste, hab ich ne kleine Demo geschrieben. Gezeigt wird eine Hook-Methode (GoF:325), ein LL(1)-Parser und das Interpreter-Muster.

Das Programm parst arithmetische Ausdrücke in Infix-Notation und wertet sie aus. Beispiel:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
user@host:~$ ./interpreter
Usage: interpreter "<expression>"

<expression> is a mathematical expression in infix-notation.
It may contain +, -, *, / and parentheses.
Only integers are allowed.

Example: interpreter "42-(3*(2+7)-56)"
user@host:~$
user@host:~$ ./interpreter "42-(3*(2+7)-56)"
71
user@host:~$
user@host:~$ ./interpreter "42-(3%*(2+7)-56)"  # Das Programm erkennt Syntaxfehler
Unrecognized character: '%'
user@host:~$
user@host:~$ ./interpreter "42++2"   # Das Programm erkennt Syntaxfehler
Number expected but Plus found

Der Tokenizer prinzipiell relativ einfach gestaltet. Er geht den übergebenen String durch und scannt nach bekannten Tokens. Um die Klasse Tokenizer ableitbar zu machen, wird eine Hook-Methode readCustomTokens() eingeführt, die in Subklassen überschreiben werden kann um zusätzliche Tokens erkennen zu können.

Der Parser benutzt den Tokenizer um aus den einzelnen Tokens einen Syntaxbaum aus Expression-Objekten aufzubauen. Dazu bedient er sich der Technik des rekursiven Abstiegs, was die Implementierung relativ leicht macht. Zu jeder Produktion der Grammatik existiert eine Methode, die sie parst.

Die folgende Grammatik wird vom Parser akzeptiert:

1
2
3
4
5
expression = firstPartOfExpression {('+'|'-') term} ;
firstPartOfExpression = ['+'|'-'] term ;
term = factor {('/'|'*') factor} ;
factor = 'number' | parenthesis ;
parenthesis = '('expression')' ;

Wobei „number“ hier ein Terminalsymbol ist, das der Tokenizer erkennt. „number“ sieht dann folgendermaßen aus:

1
number = '0'|'1'|...|'9' {'0'|'1'|...|'9'} ;

Um dann auch den Syntaxbaum auswerten zu können, d.h. konkret: um das Ergebnis zu berechnen, definiert Expression eine Methode interpret(), die den Syntaxbaum rekursiv abarbeitet. Das ist letztendlich genau das Interpreter-Pattern (GoF:243) der Viererbande.

Näheres zum Code kann man der Dokumentation entnehmen. Diese erstellt man am einfachsten mit make doc.

Der Code kann beliebig verwendet werden. InterpreterDemo (461 Downloads) Viel Spaß damit.

3 Kommentare


  1. ziegler[12]:~/tmp/InterpreterDemo$ make doc
    […]
    Error: tag OUTPUT_DIRECTORY: Output directory `/home/christian/NetBeansProjects/Interpreter/doc‘ does not exist and cannot be created
    Exiting…
    make: *** [doc] Fehler 1

    Ich würde außerdem das zip so anlegen, dass es ein Unterverzeichnis „InterpreterDemo“ erzeugt. Habe mir so aus Versehen alles in den Ober-Ordner tmp extrahiert, in dem ich es nicht haben wollte. (Meine Schuld, ok).

    Außerdem würde ich die 2. und die 5. Produktion in die 1. bzw. 4. ziehen und auch dort parsen. Das geht, und es ist für den Leser verwirrend, warum das eine eigene Produktion sein soll.

    Ansonsten solide Arbeit!

    Grüße,
    Joachim


  2. Error: tag OUTPUT_DIRECTORY:

    Ich hätte mir den Output von Doxywizzard doch ansehen sollen. Fixed.

    Ich würde außerdem das zip so anlegen, dass es ein Unterverzeichnis “InterpreterDemo” erzeugt.

    Fixed.

    Außerdem würde ich die 2. und die 5. Produktion in die 1. bzw. 4. ziehen und auch dort parsen. Das geht, und es ist für den Leser verwirrend, warum das eine eigene Produktion sein soll.

    Ne, ich finds so besser. Zu große Methoden sind nicht unbedingt übersichtlich.

    Ansonsten solide Arbeit!

    Danke. Und auch nochmals danke für deine Hilfe.

    mfg

    Christian


Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.