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 (1052 Downloads) Viel Spaß damit.
Permalink
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
Permalink
Ich hätte mir den Output von Doxywizzard doch ansehen sollen. Fixed.
Fixed.
Ne, ich finds so besser. Zu große Methoden sind nicht unbedingt übersichtlich.
Danke. Und auch nochmals danke für deine Hilfe.
mfg
Christian
Permalink