{"id":1002,"date":"2011-03-01T17:56:05","date_gmt":"2011-03-01T16:56:05","guid":{"rendered":"http:\/\/blog.benny-baumann.de\/?p=1002"},"modified":"2011-10-08T14:37:51","modified_gmt":"2011-10-08T12:37:51","slug":"parser-bau-fur-einsteiger","status":"publish","type":"post","link":"http:\/\/blog.benny-baumann.de\/?p=1002","title":{"rendered":"Parser-Bau f\u00fcr Einsteiger"},"content":{"rendered":"

Wenn man in seinem Programm mathematische Ausdr\u00fccke, die vom Nutzer eingegeben wurden, auswerten m\u00f6chte, so kann man dies entweder mit Hilfe b\u00f6sartiger Konstrukte<\/a> tun, oder aber, mit Hilfe eines Parsers, die Ausdr\u00fccke selber auswerten und dann in einer kontrollierten Umgebung ausf\u00fchren. Die M\u00f6glichkeit einer solchen kontrollierten Ausf\u00fchrung ist in Script-Sprachen wie JavaScript notwendig, kann aber auch in Template-Systemen gute Dienste leisten, wenn mit den dem Template \u00fcbergebenen Daten noch Berechnungen zu erledigen sind, oder einfache Transformationen zu implementieren sind.<\/p>\n

Einleitung<\/h2>\n

Der Bereich der Informatik, in die diese Thematik f\u00e4llt, wird als Compilerbau<\/a> bezeichnet und besch\u00e4ftigt sich damit, wie gegebene Ausdr\u00fccke eingelesen und strukturell umgebaut werden k\u00f6nnen. Meist handelt es sich bei der Eingabe um menschenlesbaren Quelltext, (z.B. in einer Hochsprache wie C), w\u00e4hrend die Ausgabe durch Bytecode oder in Maschinensprache erfolgt.<\/p>\n

Ein Compiler besteht dabei aus einer ganzen Reihe von einzelnen Verarbeitungsschritte, die je nach Architektur des Compilers (Single Pass vs. Multi Pass vs. JIT) unterschiedlich konstruiert werden und basierend auf dieser Architektur unterschiedlich komplexe Ausdr\u00fccke verarbeiten k\u00f6nnen. So ist es zwar m\u00f6glich, reinen Assembler mit einem einzigen Durchlauf durch den Quelltext zu \u00fcbersetzen, sobald aber z.B. die Verarbeitung von Variablen f\u00fcr die Erzeugung der Ausgabe wichtig wird, ergeben sich hierf\u00fcr eine Reihe von H\u00fcrden, die meist durch mehrmaliges Lesen des Quelltextes in aufeinander folgenden Phasen gel\u00f6st werden.<\/p>\n

Da ich diesen Beitrag aber speziell an Leute richten m\u00f6chte, die bisher noch nicht mit dem Thema Compilerbau in Ber\u00fchrung gekommen sind, werde ich hier keinen vollst\u00e4ndigen Compiler vorstellen, sondern mich darauf beschr\u00e4nken einen Code-Parser zu beschreiben. Als Programmiersprache dient hierbei PHP, w\u00e4hrend die von diesem Parser akzeptierte Syntax<\/a> eine Anlehnung an C bzw. PHP darstellt. Wer etwas tiefer in das Thema einsteigen m\u00f6chte und zudem Delphi beherrscht, dem sei das Tutorial zu Scriptsprachen (Teil 1<\/a> und Teil 2<\/a>) ans Herz gelegt. Eine vollst\u00e4ndiige Abhandlung des Themas w\u00fcrde hier aber den Rahmen sprengen – was auch schon so der Fall sein wird.<\/p>\n

Die Syntax<\/h2>\n

Wie bereits angedeutet, \u00e4hnelt die Syntax ein wenig C und PHP, wobei die Operatoren im Wesentlichen der C-Semantik folgen, w\u00e4hrend Variablen der Syntax von PHP entsprechen. Neben den bereits aus diesen Sprachen bekannten Rechenoperationen werden als Teil unseres Parsers eine Reihe zus\u00e4tzlicher Operationen entstehen, die in keiner von beiden Sprachen implementiert sind.<\/p>\n

Die Syntax der Sprache unterscheidet (auf Parser-Ebene) zwischen Argumenten und Operatoren. Argumente sind hierbei entweder Literale, d.h. Ganzzahlen, Gleitkomma-Zahlen oder Strings, oder Variablen. Operatoren sind jegliche anderen Symbole, die im Quelltext auftauchen, wobei Whitespace (Leerzeichen und Tabulatoren) ignoriert werden. Der Einfachheit halber nehmen wir zudem an, dass wir als Eingabe f\u00fcr den Parser bereits Tokens erhalten, d.h. unser Quelltext bereits in seine einzelnen Teile zerlegt wurde und daher bereits ein Array mit allen f\u00fcr das Analysieren des Quelltexts notwendigen Elementen vorliegt. <\/p>\n

Aus diesen Elementen soll im Laufe der Verarbeitung eine \u00e4quivalente Darstellung erzeugt werden, die sich einfach von einer Maschine interpretieren l\u00e4sst. Eine m\u00f6gliche solche Darstellung ist der sogenannte Syntax-Baum bzw. Parser Tree. Dieser speichert in jedem Knoten einen Operator und in den zugeh\u00f6rigen Kindknoten die ben\u00f6tigten Operatoren. Gefundene Argumente bilden hierbei die Bl\u00e4tter dieses Baumes.<\/p>\n

Ein f\u00fcr unsere Definition g\u00fcltiger Ausdruck ist z.B. 1 + 2 * 3 + 4. Dieser soll im weiteren Verlauf in einen etwa folgende Baumstruktur \u00fcberf\u00fchrt werden:<\/p>\n

\r\nOpBinaryPlus:\r\n  OpBinaryPlus:\r\n    ArgNumber:\r\n      1\r\n    OpBinaryMultiply:\r\n      ArgNumber:\r\n        2\r\n      ArgNumber:\r\n        3\r\n  ArgNumber:\r\n    4\r\n<\/pre>\n
Vorbereitungen<\/h2>\n
Bevor wir aber mit dem eigentlichen Bau des Parsers beginnen k\u00f6nnen, muss neben der Syntax auch noch das Verhalten von Operatoren gekl\u00e4rt werden, denn nicht jeder Operator verh\u00e4lt sich gleich. Nehmen wir hierzu einmal folgende 3 Beispiele:<\/p>\n
\r\n!$verstanden\r\n$hinz & $kunz\r\n42 ? $true++ : --$false\r\n<\/pre>\n
W\u00e4hrend das erste Beispiel mit dem logischen NOT-Operator einen un\u00e4ren Pr\u00e4fix-Operator enth\u00e4lt, finden sich im zweiten Beispiel ein bitweiser, bin\u00e4rer AND-Operator. Das dritte Beispiel besteht gar aus 3 Operatoren: einem tern\u00e4ren Operator (a ? b : c), einem un\u00e4ren Pr\u00e4fix-Operator f\u00fcr Pr\u00e4dekrementation, sowie einem un\u00e4ren Suffix-Operator f\u00fcr Post-Inkrementation.<\/p>\n
Schaut man sich insbesondere das dritte Beispiel an, so bleibt die Frage, wie man dieses Beispiel korrekt analysieren kann. Das Schl\u00fcsselwort hierf\u00fcr ist Operatorrangfolge<\/a>:<\/p>\n
$gleicher = $gleich == $gleich<\/pre>\n
Die Operatoren-Rangfolge ist hierbei analog den bereits aus der Schule bekannten Vorrang-Regeln Punkt-vor-Strich sowie den diversen Klammer-Regeln zu verstehen. So erfolgt die Auswertung von Ausdr\u00fccken zwar grundlegend erst einmal von links nach rechts, treffen wir jedoch auf einen Operator, der seine Argumente st\u00e4rker bindet, als die Operation links davon, so k\u00f6nnen wir uns um diese „h\u00f6her priorisierte“ Operation Klammern vorstellen, die entsprechend zuerst ausgerechnet werden m\u00fcssen.<\/p>\n
Diese Pr\u00fcfung der Priorit\u00e4t kann im einfachsten Fall durch die Reihenfolge der Suche nach Operatoren innerhalb des Parsers erfolgen, ben\u00f6tigt f\u00fcr unseren Fall aber noch etwas Feintuning, wie sich sp\u00e4ter zeigen wird. Da sich viele der Operatoren in Bezug auf die Argumente aber \u00e4hneln, insbesondere beim Aufbau, werden wir diese Chance ergreifen und entsprehcend Gruppen von Operatoren bilden:<\/p>\n