Wenn man in seinem Programm mathematische Ausdrücke, die vom Nutzer eingegeben wurden, auswerten möchte, so kann man dies entweder mit Hilfe bösartiger Konstrukte tun, oder aber, mit Hilfe eines Parsers, die Ausdrücke selber auswerten und dann in einer kontrollierten Umgebung ausführen. Die Möglichkeit einer solchen kontrollierten Ausführung ist in Script-Sprachen wie JavaScript notwendig, kann aber auch in Template-Systemen gute Dienste leisten, wenn mit den dem Template übergebenen Daten noch Berechnungen zu erledigen sind, oder einfache Transformationen zu implementieren sind.
Einleitung
Der Bereich der Informatik, in die diese Thematik fällt, wird als Compilerbau bezeichnet und beschäftigt sich damit, wie gegebene Ausdrücke eingelesen und strukturell umgebaut werden können. Meist handelt es sich bei der Eingabe um menschenlesbaren Quelltext, (z.B. in einer Hochsprache wie C), während die Ausgabe durch Bytecode oder in Maschinensprache erfolgt.
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ücke verarbeiten können. So ist es zwar möglich, reinen Assembler mit einem einzigen Durchlauf durch den Quelltext zu übersetzen, sobald aber z.B. die Verarbeitung von Variablen für die Erzeugung der Ausgabe wichtig wird, ergeben sich hierfür eine Reihe von Hürden, die meist durch mehrmaliges Lesen des Quelltextes in aufeinander folgenden Phasen gelöst werden.
Da ich diesen Beitrag aber speziell an Leute richten möchte, die bisher noch nicht mit dem Thema Compilerbau in Berührung gekommen sind, werde ich hier keinen vollständigen Compiler vorstellen, sondern mich darauf beschränken einen Code-Parser zu beschreiben. Als Programmiersprache dient hierbei PHP, während die von diesem Parser akzeptierte Syntax eine Anlehnung an C bzw. PHP darstellt. Wer etwas tiefer in das Thema einsteigen möchte und zudem Delphi beherrscht, dem sei das Tutorial zu Scriptsprachen (Teil 1 und Teil 2) ans Herz gelegt. Eine vollständiige Abhandlung des Themas würde hier aber den Rahmen sprengen – was auch schon so der Fall sein wird.
Die Syntax
Wie bereits angedeutet, ähnelt die Syntax ein wenig C und PHP, wobei die Operatoren im Wesentlichen der C-Semantik folgen, während Variablen der Syntax von PHP entsprechen. Neben den bereits aus diesen Sprachen bekannten Rechenoperationen werden als Teil unseres Parsers eine Reihe zusätzlicher Operationen entstehen, die in keiner von beiden Sprachen implementiert sind.
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ür den Parser bereits Tokens erhalten, d.h. unser Quelltext bereits in seine einzelnen Teile zerlegt wurde und daher bereits ein Array mit allen für das Analysieren des Quelltexts notwendigen Elementen vorliegt.
Aus diesen Elementen soll im Laufe der Verarbeitung eine äquivalente Darstellung erzeugt werden, die sich einfach von einer Maschine interpretieren lässt. Eine mögliche solche Darstellung ist der sogenannte Syntax-Baum bzw. Parser Tree. Dieser speichert in jedem Knoten einen Operator und in den zugehörigen Kindknoten die benötigten Operatoren. Gefundene Argumente bilden hierbei die Blätter dieses Baumes.
Ein für unsere Definition gültiger Ausdruck ist z.B. 1 + 2 * 3 + 4. Dieser soll im weiteren Verlauf in einen etwa folgende Baumstruktur überführt werden:
OpBinaryPlus:
OpBinaryPlus:
ArgNumber:
1
OpBinaryMultiply:
ArgNumber:
2
ArgNumber:
3
ArgNumber:
4
Vorbereitungen
Bevor wir aber mit dem eigentlichen Bau des Parsers beginnen können, muss neben der Syntax auch noch das Verhalten von Operatoren geklärt werden, denn nicht jeder Operator verhält sich gleich. Nehmen wir hierzu einmal folgende 3 Beispiele:
!$verstanden $hinz & $kunz 42 ? $true++ : --$false
Während das erste Beispiel mit dem logischen NOT-Operator einen unären Präfix-Operator enthält, finden sich im zweiten Beispiel ein bitweiser, binärer AND-Operator. Das dritte Beispiel besteht gar aus 3 Operatoren: einem ternären Operator (a ? b : c), einem unären Präfix-Operator für Prädekrementation, sowie einem unären Suffix-Operator für Post-Inkrementation.
Schaut man sich insbesondere das dritte Beispiel an, so bleibt die Frage, wie man dieses Beispiel korrekt analysieren kann. Das Schlüsselwort hierfür ist Operatorrangfolge:
$gleicher = $gleich == $gleich
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ücken zwar grundlegend erst einmal von links nach rechts, treffen wir jedoch auf einen Operator, der seine Argumente stärker bindet, als die Operation links davon, so können wir uns um diese „höher priorisierte“ Operation Klammern vorstellen, die entsprechend zuerst ausgerechnet werden müssen.
Diese Prüfung der Priorität kann im einfachsten Fall durch die Reihenfolge der Suche nach Operatoren innerhalb des Parsers erfolgen, benötigt für unseren Fall aber noch etwas Feintuning, wie sich später zeigen wird. Da sich viele der Operatoren in Bezug auf die Argumente aber ähneln, insbesondere beim Aufbau, werden wir diese Chance ergreifen und entsprehcend Gruppen von Operatoren bilden:
- Unäre Präfix-Operatoren (+, -, ++, –, ~, !)
- Unäre Postfix-Operatoren (++, –, !)
- Binäre Operatoren (+, -, *, /, %, &, &&, |, ||, ^, ^^, ., =, <, >, <=, >=, ==, !=, ===, !==, ::, ->)
- Ternäre Operatoren (?:)
- Sonstige (z.B. Klammern, Array-Zugriffe, Funktionsaufrufe)
Neben der Rangfolge sollten wir uns später zusätzlich auch um die Assoziativität der Operatoren kümmern, da diese in der Regel linksassoziativ ist, für den hier vorgestellten Parser aber vorrangig rechtsassoziativ sein wird (der Einfachheit halber). Aber auch dazu mehr, denn für die meisten Berechnungen, bei denen das Distributivgesetz gilt, spielt die Assoziativität keine Rolle; und ist maximal von der Auswertungsreihenfolge gewöhnungsbedürftig.
Erster Code
define ('PARSE_TERM', 1);
define ('PARSE_SUBTERM', 2);
define ('PARSE_EOF', 3);
abstract class Term {
public abstract function compile();
public abstract function check();
public abstract function evaluate();
public function isWritable() {
return false;
}
public function dump($level = 0) {
$space = str_repeat(' ', $level);
echo $space;
echo get_class($this);
echo ":\n";
}
}
Mit der Klasse Term haben wir hier unsere wichtigste Klasse, neben dem Parser. Von Term werden sowohl alle Argumente, als auch alle Operatoren abgeleitet. Die Funktion compile ist für den eigentlichen Parser nicht nötig, kann aber wenn man alles richtig implementiert hat, verwendet werden, um den fertigen Ausdruck in gültiges PHP zu übersetzen. Diese Möglichkeit ergibt sich direkt aus unserem Parser-Baum und erfordert auch nicht allzu viel Aufwand. Aber dazu gleich mehr. Die Methode check überprüft die syntaktische Korrektheit der in einem Term gespeicherten Bestandteile. Die Methode evaluate schließlich erlaubt die Ausführung bzw. Auswertung unseres Ausdrucks. Ähnlich wie die Methode zum „Compilen“ ergibt sich auch diese Methode fast automatisch.
abstract class Argument extends Term {
public $value = null;
public abstract function canParse($symbol);
public function dump($level = 0) {
parent::dump($level);
$space = str_repeat(' ', $level+1);
echo $space;
echo $this->value;
echo "\n";
}
}
Die Klasse Argument schließlich definiert die Grundlagen für alle auftauchenden Argumente im Quelltext. Neben einem Wert, der den Inhalt dieses Symbols angibt, gibt es mit der Methode canParse den ersten elementaren Bestandteil des Parsers. Die Funktion canParse gibt hierbei an, ob das gegebene Symbol wie gewünscht geparst werden kann, sprich ob „$abc“ eine Zahl ist oder nicht (in dem Fall würde ArgVariable ja sagen). Rückgabe ist hierbei entweder false für „kann ich nicht verarbeiten“ oder eine Instanz der jeweiligen Klasse, die das value-Feld korrekt initialisiert hat, um später den Quelltext reproduzieren zu können.
Aber weiter zur nächsten wichtigen Klasse, ohne die unser Parser sonst gar keinen Spaß machen würde: Einen Operator!
abstract class Operator extends Term {
protected $args = array();
public abstract function canParse($symbol, $lterms, $opsym);
public function storeArgs($arguments) {
$this->args = $arguments;
}
public function dump($level = 0) {
parent::dump($level);
foreach($this->args as $arg) {
$arg->dump($level+1);
}
}
}
Jeder Operator besteht hierbei aus einer Reihe von anderen Termen, den sogenannten Argumenten für diesen Operator. Ferner besitzt ein Operator analog zu Argumenten die Möglichkeit, zu sagen, ob er mit einem Token zurecht kommt. Token sind hierbei entwerder Argumente, bereits geparste Terme oder Operatoren, die als Strings übergeben werden. Zusätzlich besitzt jeder Operator eine Methode, um die in einem Kontext gefundenen Argumente (Terme) abzuspeichern. Diese Methode wird uns später beim Aufbau des Parser Trees noch einmal begegnen.
Parsen von Argumenten
Da wir nun die grundlegenden Bestandteile des Parser Trees kurz vorgestellt haben, können wir nun mit dem ersten Teil der Parsing-Arbeit beginnen. Nehmen wir uns nun erst einmal den einfachen Teil heraus: Die Argumente:
class ArgNumber extends Argument {
public function compile() {
return ''.$this->value;
}
public function check() {
return is_numeric($this->value);
}
public function evaluate() {
return $this->value;
}
public function canParse($symbol) {
if(!is_numeric($symbol)) {
return false;
}
$obj = new self();
$obj->value = (float)$symbol;
return $obj;
}
}
class ArgString extends Argument {
public function compile() {
return "'".str_replace("'", "\\'", str_replace('\\', '\\\\', $this->value)). "'";
}
public function check() {
return is_string($this->value);
}
public function evaluate() {
return $this->value;
}
public function canParse($symbol) {
if(!is_string($symbol)) {
return false;
}
if(2 > strlen($symbol)) {
return false;
}
if("'" != $symbol[0]) {
return false;
}
if("'" != $symbol[strlen($symbol)-1]) {
return false;
}
$obj = new self();
$obj->value = substr($symbol, 1, -1);
$obj->value = str_replace('\\\'', '\'', $obj->value);
$obj->value = str_replace('\\\\', '\\', $obj->value);
return $obj;
}
}
class ArgVariable extends Argument {
public function compile() {
return '$'.$this->value;
}
public function check() {
return true;
}
public function evaluate() {
return $GLOBALS[$this->value];
}
public function isWritable() {
return true;
}
public function canParse($symbol) {
if(!is_string($symbol)) {
return false;
}
if(!strlen($symbol)) {
return false;
}
if('$' != $symbol[0]) {
return false;
}
$obj = new self();
$obj->value = substr($symbol, 1);
return $obj;
}
}
An dieser Stelle dürfte es vorerst keine Überraschungen geben, abgesehen davon, dass dieser Source nicht unbedingt der effizienteste ist. Aber zur Demonstration reicht es durchaus aus. Dank OOP können wir später immer noch recht einfach Anpassungen an das Verhalten vornehmen. Insbesondere bei Variablen sollte noch ein Fehler auffallen, der sich aber leicht durch eine zusätzliche Prüfung beheben lässt.
Die Operatoren
Etwas aufwändiger sieht es nun bei den Operatoren aus, da es davon einfach eine ganze Menge gibt. Wie oben aber bereits angedeutet wurde, lässt sich hier eine ganze Menge Arbeit sparen, wenn man an die Evolutionstheorie glaubt und diese daher für sich zu nutzen weiß. Statt also blind alle Operatoren mit einem Mal zu definieren, legen wir erstmal ein paar Grundklassen an, von denen wir später einfach ableiten können:
abstract class UnaryOperator extends Operator {
public function canParse($symbol, $lterms, $opsym) {
if(empty($lterms) && empty($opsym)) {
//The first part ist the operator?
if(is_string($symbol)) {
//If we get a non-string value, this can't be an operator
return $this->opSign == $symbol ? PARSE_TERM : false;
}
return false;
}
if(!empty($opsym)) {
if(is_string($symbol)) {
return false;
}
//We already got an operator? If we also got an value, this is an error!
return empty($lterms) ? PARSE_EOF : false;
}
if(!empty($lterms)) {
//We already got a value? If we didn't get an operator, this is an error!
return empty($opsym) ? false : PARSE_EOF;
}
//We should never reach here!
return false;
}
public function compile() {
return $this->opSign . $this->args[0]->compile();
}
public function check() {
return 1 == count($this->args);
}
}
abstract class UnaryPostOperator extends UnaryOperator {
public function canParse($symbol, $lterms, $opsym) {
if(empty($lterms) && empty($opsym)) {
//The first part is some term
return PARSE_TERM;
}
if(!empty($opsym)) {
return false;
}
if(!empty($lterms)) {
//The first part ist the operator?
return $this->opSign == $symbol ? PARSE_EOF : false;
}
//We should never reach here!
return false;
}
public function compile() {
return $this->args[0]->compile() . $this->opSign;
}
}
abstract class BinaryOperator extends Operator {
public function canParse($symbol, $lterms, $opsym) {
if(empty($lterms) && empty($opsym)) {
return PARSE_TERM;
}
//We need a term to the left
if(empty($lterms)) {
if(is_string($symbol)) {
//The first can't be an operator
return false;
}
//We can handle any argument
return true;
}
//We also have an operator
if(empty($opsym)) {
if(is_string($symbol)) {
// We got the first argument and just got the operator
return $this->opSign == $symbol ? PARSE_TERM : false;
} else {
//Error: Two arguments after each other
return false;
}
}
//We got another operator?
if(is_string($symbol)) {
//We don't like it :P
return false;
}
if(1 == count($lterms) && 1 == count($opsym)) {
return PARSE_EOF;
}
//We should never reach here!
return false;
}
public function compile() {
return $this->args[0]->compile() . $this->opSign . $this->args[1]->compile();
}
public function check() {
return 2 == count($this->args);
}
}
abstract class TernaryOperator extends Operator {
public function compile() {
return false; //Unimplemented for now.
return $this->args[0]->compile() . $this->opSign1 . $this->args[1]->compile() . $this->opSign2 . $this->args[2]->compile();
}
public function check() {
return 3 == count($this->args);
}
}
Wie angekündigt, ersparen wir uns durch diese Vorbereitungen einiges an Arbeit. Dies macht es aber umso wichtiger, dass genau dieser Aspekt des Parsers sehr gut verstanden ist, um später den Abläufen folgen zu können. Lassen wir hierzu die Methoden check und compile einmal außen vor, so verbleibt nur die canParse-Methode, deren Aufgabe die strukturelle Analyse der Eingabedaten ist.
Die canParse-Methode besitzt 3 Parameter:
- $symbol: Das aktuelle, zum Operator hinzuzufügende Symbol
- $lterms: Bereits links vom aktuellen Punkt gefundene Terme
- $opsyms: Bereits gefundene Operator-Symbole für den aktuellen Kontext
Der Aufruf der Methode erfolgt immer wenn ein Operator in einem Kontext (dazu unten im Parser mehr) gefunden wird, oder wenn auf Grund von Baum-Umstrukturierungen ein neuer Term in den Kontext einzuordnen ist. Die Methode canParse beschreibt somit anhand des Rückgabewertes, welche Transitionen für den Operatoren-Parser Tree möglich sind. Ein einfaches Beispiel stellen hierbei die unären Präfix-Operatoren dar, deren Transitionen wie folgt verlaufen:
- Wenn noch nichts im Kontext vorhanden ist, suche nach unserem Operator. Wird dieser in Symbol übergeben, akzeptieren wir diesen und sagen an, dass wir als nächstes einen Operator brauchen, der gleich stark oder stärker bindet, als wir.
- Wir haben bereits unseren Operator uns fehlt aber noch ein Argument. Wir prüfen, dass wir einen Term (Argument oder fertigen Operator) übergeben bekommen und geben wenn dies der Fall ist zurück, dass unser Kontext somit abgeschlossen ist. Wird uns ein zweiter Operator übergeben, geben wir einen Fehler zurück.
- Befinden wir uns in einem beliebigen anderen Zustand, geben wir einen Fehler zurück
Nun mag gegebenenfalls verwunderlich sein, was im Falle von
!!$var
passiert. Das sollte sich aber bei einem kurzen Blick auf die Rückgabewerte der canParse-Methode verdeutlichen:
- false: dieser Token ist an der aktuellen Position unzulässig.
- true: Der Token ist an der aktuellen Position zulässig und keine Kontext-Operation ist nötig.
- PARSE_TERM: der Token ist gültig und nachfolgend wird ein Term erwartet, der gleich oder stärker bindet als unser Operator.
- PARSE_SUBTERM: Der Token ist gültig und es wird ein Term erwartet, in dem alle anderen Operatoren zulässig sind. Die Rangfolge ist durch Begrenzungszeichen durch unseren Operator eindeutig.
- PARSE_EOF: Der Token ist gültig und beendet den aktuellen Kontext.
Kontext-Operation heißt hierbei, dass der Parser innerhalb des Parser Trees eine neue Ebene anfängt, oder eine solche beendet, indem die bisher gesammelten Terme der Ebene einsammelt und zu einem Operator-Objekt zusammenfasst, was an den Parent übergeben wird. Aber dazu gleich mehr.
Der Parser
Nach dem wir nun die ganzen Vorbereitungen hinter uns haben, können wir uns nun um den eigentlichen Parser kümmern. Da dieser Schritt aber etwas umfangreicher wird, bauen wir den Parser an dieser Stelle Schritt für Schritt zusammen.
class ParserTree {
private $root = null;
public function dump() {
echo "Generierter Parser-Tree:\n";
echo "----\n";
if(!is_object($this->root)) {
echo "Kein Parser-Tree vorhanden!\n";
} else {
$this->root->dump();
}
echo "----\n";
}
private $availableOps = array();
private $availableArgs = array();
public function registerArguments($args)
{
$this->availableArgs = $args;
foreach($this->availableArgs as &$arg) {
$arg[1] = new $arg[0];
}
}
public function registerOperators($ops)
{
$this->availableOps = $ops;
foreach($this->availableOps as &$op) {
$op[1] = new $op[0];
}
}
//...
}
Diese Methoden sind erst einmal Verwaltungsmethoden, auf deren Arbeit wir später eingehen. Anhand des Namens dürfte aber auch bereits jetzt ersichtlich werden, was diese tun. Wichtiger sind eher die folgenden Methoden, die uns innerhalb des Parsers eine Menge an Arbeit abnehmen und ein paar Code-Dopplungen zu vermeiden helfen:
private $level = 0;
private $context = array();
private function addContext($AllowedOps) {
$ctx = array(
'Args' => array(),
'Ops' => array(),
'Allow' => $AllowedOps
);
array_push($this->context, $ctx);
$this->level = count($this->context)-1;
}
private function &removeContext() {
$ctx = array_pop($this->context);
$this->level = count($this->context)-1;
if(empty($this->context)) {
$this->addContext($this->availableOps);
}
return $ctx;
}
private function isArgument($token) {
foreach($this->availableArgs as $type) {
$canParse = $type[1]->canParse($token);
if(false !== $canParse) {
//This token could be parsed as some argument
return $canParse;
}
}
return false;
}
private function &getContext() {
return $this->context[$this->level];
}
private function hasContextOps() {
$ctx =& $this->getContext();
return count($ctx['Ops']);
}
private function hasContextTerms() {
$ctx =& $this->getContext();
return count($ctx['Args']);
}
private function getContextOp() {
$ctx =& $this->getContext();
return $ctx['Ops'][0][1];
}
public function filterOps($ops, $curOp) {
//Start with all operations allowed, but remove everything, until we find the operator
while($checkOp = array_shift($ops)) {
if($curOp[0] == $checkOp[0]) {
array_unshift($ops, $checkOp);
break;
}
}
return $ops;
}
Zuerst ein paar Worte zu den beiden Variablen $level und $context: $context bildet, wie man im Source erkennen kann, einen Stapel einer Struktur, die aus drei Teilen besteht. Diese 3 Teile sind Args für die in dieser Ebene gespeicherte Argumente/Terme, Ops für in dieser Ebene gespeicherte Operatoren und Allow für in dieser Ebene erlaubte Operatoren. $level bildet eine Abkürzung für den aktuell gültigen Kontext, damit dieser nicht immer durch Zählen ermittelt werden muss.
Die Methode addContext fügt einen neuen, leeren Kontext ein und initialisiert, welche Operationen für diesen Kontext zulässig sind. Die Methode removeContext entfernt den aktuellen Kontext und gibt diesen zurück. Außerdem stellt removeContext sicher, dass immer ein gültiger Kontext existiert, was ggf. durch Anlegen eines leeren Kontext, in dem alle Operatoren erlaubt sind, erreicht wird. Mit den Methoden getContext und getContextOp kann der aktuelle Kontext, bzw. die in diesem gültige Rechenoperation abgefragt werden.
Die Methode filterOps schließlich ermöglicht es, aus der Liste der Operatoren all diejenigen zu entfernen, die weniger stark als ein gegebener Operator binden. Hierbei richtet sich die Priorität eines Operators nach der Reihenfolge in der Operatorenliste, wobei später aufgeführte Operatoren stärker binden.
Die Token-Analyse
Womit wir glaube bei dem Kapitel wären, worauf die meisten sehr lange gewartet haben: Wie wird denn nun der eigentliche Parser Tree erzeugt? Auch hier bietet es sich an, den Quelltext etwas aufzuteilen, da dieser auf Grund der Komplexität recht umfangreich ist:
private $parseToken = array();
public function parse($tokenlist) {
//We have an empty expression ...
$this->context = array();
$this->addContext($this->availableOps);
//Start with the whole expression ...
$this->parseToken = $tokenlist;
//As long as we still have tokens ...
while(count($this->parseToken) || $this->level || $this->hasContextOps()) {
//Handle EOF.
if(!count($this->parseToken)) {
array_unshift($this->parseToken, array('eof', ''));
}
//Grab one ...
$token = array_shift($this->parseToken);
//...
}
$this->root = $this->context[0]['Args'][0];
return true;
}
Der erste Teil unseres eigentlichen Parsers wird durch einen kurzen Teil für eine Reihe kleinerer Initialisierungen gebildet, der von der Hauptschleife gefolgt wird und schließlich mit ein paar Aufräumarbeiten beendet wird. Wer sich jetzt wundert, wie das mit dem $this->context[0][‚Args‘][0] zu Stande kommt: Das besagt einfach nur, vom letzten verbleibenden Kontext bitte das erste Argument nehmen. Dieses existiert an dieser Stelle immer, da der Baum zur Not solange reduziert und zusammengefasst wird, bis keine verbleibende Operation mehr vorliegt. Lässt sich aus den vorhandenen Operationen nicht der gesamte Baum reduzieren, wird dies bereits in der Schleife erkannt und als Fehler gemeldet.
In jedem Verarbeitungsschritt wird nun ein Token eingelesen und in der Baumstruktur eingeordnet. Hier gibt es 2 voneinander getrennte Schritte: Prüfen auf Argumente vs. verarbeiten von Operatoren.
//Check if it's an argument
$tokenArgType = $this->isArgument($token);
//If we have an argument, let's check how to continue ...
if(false !== $tokenArgType) {
//Do we already have an operator
if($this->hasContextOps()) {
//There are three possibilities:
$ctx =& $this->getContext();
$parseState = $this->getContextOp()->canParse($token, $ctx['Args'], $ctx['Ops']);
// ...
}
//Put the argument in place!
$ctx =& $this->getContext();
array_push($ctx['Args'], $tokenArgType);
//Continue with next token
continue;
}
// ...
Treffen wir bei unserer Suche auf ein Argument, so gibt es zwei Fälle, die wir betrachten müssen, denn entweder haben wir bereits einen Operator verfügbar oder wir haben bisher einen leeren Kontext. Ist der Kontext bisher leer, gehen wir einfach einmal davon aus, dass wir einfach das Argument speichern und im nächsten Schritt dann mehr dazu erfahren. Gibt es bereits einen Operator für diesen Kontext, müssen wir natürlich auswerten, ob dieser mit dem gefundenen Argument einverstanden ist:
if(false == $parseState) {
//0. The operator can't handle this
echo "Syntaxfehler: Operator kann Token nicht parsen\n";
} else if(true === $parseState) {
//1. The operator just want's more data ;-)
//e.g. Identifier -->"("< -- Term ) --> Function call
//To get this token, if we get the identifier here, we just need to continue.
} else if(PARSE_TERM == $parseState) {
// 2. The Parser requires a second operator
// This value means: all operators including more-binding ones are allowed
$ctx =& $this->getContext();
$ctxOp = $ctx['Ops'][0];
$newOps = $this->filterOps($ctx['Allow'], $ctxOp);
$this->addContext($newOps);
} else if(PARSE_SUBTERM == $parseState) {
// 3. The Parser requires a sub-expression
// This value means: all operators are allowed
$this->addContext($this->availableOps);
} else if(PARSE_EOF == $parseState) {
// 4. The Parser can terminate this state
//The goal here is to fill in the params into a new object and replace the current level's contents with this object
$ctx =& $this->removeContext();
array_push($ctx['Args'], $tokenArgType);
$tokenArgType = clone $this->getContextOp();
$tokenArgType->storeArgs($ctx['Args']);
} else {
// 5. We have an internal error
echo "Interner Fehler\n";
return false;
}
In $parserState steht für diese Verarbeitung die Rückgabe der oben bereits besprochenen canParse-Methode. Standard-Aktion ist hierbei für alle Token, dass sie entweder einen neuen Kontext für nachfolgende Operationen anlegen, oder einen bestehenden Kontext auflösen, um daraus einen abgeschlossenen Operator zu bilden, der dann im aktuellen Kontext eingefügt wird.
Ist dieser Schritt erledigt, können wir zwar bereits Argumente einsortieren, da wir aber bisher keine Operatoren verarbeiten, kommen wir insgesamt nicht allzu weit. Das ändert sich aber im folgenden Schritt:
$ctx =& $this->getContext();
//We seem to have gotten an operator
$canParseOps = array();
foreach($ctx['Allow'] as $allowedOp) {
$canParse = $allowedOp[1]->canParse($token, $ctx['Args'], $ctx['Ops']);
if($canParse) {
$canParseOps[] = array($allowedOp, $canParse);
}
}
//More than one operator can handle this; but we can't ;-)
if(1 < count($canParseOps)) {
echo "Syntaxfehler (Multi Ops!)\n";
var_dump($canParseOps, $ctx);
return false;
}
//There are no operators left to handle this; try unstacking ;-)
if(0 == count($canParseOps)) {
// ...
}
$currentOp = array_shift($canParseOps);
list($tokenArgType, $parseState) = $currentOp;
if(false === $parseState) {
//This should never get reached!
echo "Interner Fehler\n";
return;
}
$ctx =& $this->getContext();
array_push($ctx['Ops'], $tokenArgType);
// ...
Im Falle eines Operators ist die Arbeit etwas umfangreicher. Zuerst fragen wir bei allen Operatoren an, ob diese mit dem aktuellen Kontext etwas anfangen können und schauen dann, dass sich hoffentlich nur einer meldet. Melden sich mehrere, ist dies aller wahrscheinlichkeit ein Syntax-Fehler, oder wir haben uns vertan 😉 In jedem Fall können wir aber unseren Operator beruhigt auf den Operatoren-Stack legen, da Operatoren, die bereits vorher bereits einmal nein gesagt haben, aus der aktuellen Behandlung bereits ausgeschlossen wurden. Ein plötzliches „ach doch“ ist somit unwahrscheinlich und deutet daher auf einen Fehler in unserer Implementierung der Operatoren hin, sollte es doch passieren.
Mit unserem frisch geparsten Operator auf dem Stack können wir uns nun um die Verarbeitung des $parserState kümmern, was analog der bereits für Argumente gesehenen Verarbeitung erfolgt:
if(true === $parseState) {
} else if(PARSE_TERM == $parseState) {
// 2. The Parser requires a second operator
// This value means: all operators including more-binding ones are allowed
$ctx =& $this->getContext();
$ctxOp = $ctx['Ops'][0];
$newOps = $this->filterOps($ctx['Allow'], $ctxOp);
$this->addContext($newOps);
} else if(PARSE_SUBTERM == $parseState) {
// 3. The Parser requires a sub-expression
// This value means: all operators are allowed
$this->addContext($this->availableOps);
} else if(PARSE_EOF == $parseState) {
// 4. The Parser can terminate this state
//The goal here is to fill in the params into a new object and replace the current level's contents with this object
$tokenArgType = clone $this->getContextOp();
$ctx =& $this->removeContext();
$tokenArgType->storeArgs($ctx['Args']);
//Put the argument in place!
$ctx =& $this->getContext();
array_push($ctx['Args'], $tokenArgType);
} else {
// 5. We have an internal error
echo "Interner Fehler (Unimplemented)\n";
return false;
}
Womit wir auch schon die normale Verarbeitung von Argumenten und Operatoren abgeschlossen hätten. Jetzt kommen wir zu den Sonderfällen 😉 Denn manchmal kommt es vor, dass in einem Zustand keiner unserer Operatoren einen bestimmten Token haben möchte. In diesem Fall gibt es zwei Möglichkeiten:
if(!$this->hasContextOps()) {
// ...
} else if($this->hasContextTerms()) {
// ...
} else {
//No arguments and no terms ... It's an error!
echo "Syntaxfehler (No Ops!)\n";
$ctx =& $this->getContext();
var_dump($ctx);
return false;
}
if(!empty($token)) {
array_unshift($this->parseToken, $token);
}
continue;
Sollten wir hierbei einen Token bekommen haben, der nicht das Ende des Ausdrucks angibt, so geben wir bescheid, dass wir diesen noch einmal vorgelegt brauchen, da wir uns nicht um diesen kümmern konnten, da wir erst einmal am Parser Tree kleinere Umbauarbeiten vorzunehmen hatten.
Im Falle, dass wir bisher noch keinen Operator für einen Kontext haben, können wir unser Glück damit versuchen, dass wir den aktuellen Kontext auflösen und die bisherigen Ergebnisse an den Parent überreichen, was wie folgt umgesetzt werden kann:
// Only try unstacking if we don't have any operator on this level
//Also, for now, only unstack for one single argument
if(1 != $this->hasContextTerms()) {
echo "Syntaxfehler (Unstack Arg Mismatch!)\n";
var_dump($ctx);
return false;
}
//Restore the previous level
$ctx =& $this->removeContext();
$args = $ctx['Args'];
//We got all we need from the child context; switch to the current one.
$ctx =& $this->getContext();
//Apply the last argument on this level
$currentOp = $this->getContextOp();
$parseState = $currentOp->canParse($args[0], $ctx['Args'], $ctx['Ops']);
//Check if we got some more finished tokens
if(false === $parseState) {
echo "Syntaxfehler (Unstack Token Syntax!)\n";
var_dump($ctx);
return false;
}
//Store the argument as part of the current context
array_push($ctx['Args'], $args[0]);
if(true === $parseState) {
//No need for further actions; we'll continue in the next step
} else if(PARSE_TERM == $parseState) {
//The next thing expected is a sub-extression.
//So we just create one.
$ctx =& $this->getContext();
$ctxOp = $ctx['Ops'][0];
$newOps = $this->filterOps($ctx['Allow'], $ctxOp);
$this->addContext($newOps);
} else if(PARSE_SUBTERM === $parseState) {
//The next thing expected is a whole new expression allowing all arguments
//So we just create one.
$this->addContext($this->availableOps);
} else if(PARSE_EOF === $parseState) {
//This operation just finished one token.
//Exit this context and round things up.
//Put the argument in place!
$tokenArgType = clone $this->getContextOp();
$ctx =& $this->removeContext();
$tokenArgType->storeArgs($ctx['Args']);
//Put the argument in place!
$ctx =& $this->getContext();
array_push($ctx['Args'], $tokenArgType);
}
Für den Fall, dass wir bereits einen Operator haben, fragen wir diesen einfach, ob das zuletzt hinzugefügte Argument diesen abgeschlossen hat:
//We have an operator; let's pretend, the last operation was just performed
$ctx =& $this->getContext();
$tokenArgType = array_pop($ctx['Args']);
$currentOp = $this->getContextOp();
$parseState = $currentOp->canParse($tokenArgType, $ctx['Args'], $ctx['Ops']);
array_push($ctx['Args'], $tokenArgType);
//Check if we got some more finished tokens
if(false === $parseState) {
echo "Syntaxfehler (Unstack MultiToken Syntax!)\n";
var_dump($ctx);
return false;
} else if(true === $parseState) {
//We got a token, that can't be handled, but the previous one was asked to continue --> Syntax error
echo "Syntaxfehler (Unstack Continuation Requested!)\n";
var_dump($ctx);
return false;
} else if(PARSE_TERM == $parseState) {
//We got a token, that can't be handled, but the previous one was asked for a term --> Syntax error
echo "Syntaxfehler (Unstack Term Requested!)\n";
var_dump($ctx);
return false;
} else if(PARSE_SUBTERM === $parseState) {
//We got a token, that can't be handled, but the previous one was asked for a subterm --> Syntax error
echo "Syntaxfehler (Unstack Subterm Requested!)\n";
var_dump($ctx);
return false;
} else if(PARSE_EOF === $parseState) {
//This operation just finished one token.
//Exit this context and round things up.
$tokenArgType = clone $this->getContextOp();
$ctx =& $this->removeContext();
$tokenArgType->storeArgs($ctx['Args']);
//Put the argument in place!
$ctx =& $this->getContext();
array_push($ctx['Args'], $tokenArgType);
}
Was hier auffallen sollte, ist die Tatsache, dass außer PARSE_EOF alle möglichen Schritte zu einem Parser-Fehler führen, was insofern logisch ist, dass der Parser zu dem hier erneut hinzugefügten Parser bereits einmal zugestimmt hat. Da diese Prüfung aber rein deterministisch sein muss, um einen konsistenten Parser-Baum zu erhalten, ist in diesem Fall nur PARSE_EOF zulässig. Ferner führen PARSE_TERM und PARSE_SUBTERM an dieser Stelle zu einem Widerspruch, da der Parser aufgefordert wird, mit dem aktuellen Kontext fortzusetzen, was aber niemand tun möchte.
Womit wir auch bereits durch wären … Naja, nicht ganz 😛
Der Testlauf
Denn wenn wir einfach nur uns den bisher erstellten Parser instantiieren würden, um dann
$tree->parse($expr);
aufzurufen, würde uns der Parser mit Unglaube anschauen und seinen Dienst vereiteln. Da fehlt nämlich noch was, was wir oben mit als erstes für den Parser implementiert haben. Richtig! Die verfügbaren Argumente und Operatoren.Übergeben wir diese vor dem Parsen, geht es:
$example = array(
'1',
'+',
'2',
'*',
'3',
'+',
'4',
);
echo "<pre>";
echo "Test:\n";
$tree = new ParserTree();
$tree->registerArguments(array(
array('ArgNumber'),
array('ArgString'),
array('ArgVariable'),
));
$tree->registerOperators(array(
//Brackets have highest Priority
//array('OpLeftBracket'),
array('OpBinaryFieldStatic'),
array('OpBinaryFieldObject'),
array('OpUnaryPreIncrement'),
array('OpUnaryPreDecrement'),
array('OpUnaryPostIncrement'),
array('OpUnaryPostDecrement'),
array('OpBinaryAssign'),
array('OpUnaryPlus'),
array('OpUnaryMinus'),
array('OpUnaryBitNot'),
array('OpUnaryLogicNot'),
array('OpBinaryConcat'),
array('OpBinaryPlus'),
array('OpBinaryMinus'),
array('OpBinaryMultiply'),
array('OpBinaryDivide'),
array('OpBinaryModulo'),
array('OpBinaryPower'),
array('OpBinaryBitAND'),
array('OpBinaryLogicAND'),
array('OpBinaryBitOR'),
array('OpBinaryLogicOR'),
array('OpBinaryBitXOR'),
array('OpBinaryLogicXOR'),
array('OpBinaryEqual'),
array('OpBinaryNotEqual'),
array('OpBinaryIdentical'),
array('OpBinaryNotIdentical'),
array('OpTernaryIf'),
));
$tree->parse($example);
$tree->dump();
echo "</pre>";
Läuft alles wie gewünscht, sehen wir einen netten Parser-Baum auf unserem Bildschirm:
Generierter Parser-Tree:
----
OpBinaryPlus:
OpBinaryPlus:
ArgNumber:
1
OpBinaryMultiply:
ArgNumber:
2
ArgNumber:
3
ArgNumber:
4
----
Bindungskräfte
Was nun noch fehlt, ist die korrekte Behandlung von Operator-Assoziativität und das Erlauben gleichrangiger Operatoren. Das ist in diesem einfachen Parser bisher noch nicht implementiert, läuft aber auf Grund der Art, wie derzeit die Baumstruktur aufgebaut wird, auf eine bevorzugt rechtsassoziative Behandlung von Operatoren hinaus. Dies mag zwar für viele Fälle reichen, erzeugt aber bereits bei Ketten-Divisionen nicht ganz offensichtliche Effekte. Denn definiert man die Division rechtsassoziativ, so ist 1 / 2 / 3 durchaus korrekt 1.5, während uns die Schulmathematik weißmachen möchte, dass da 1 / 6 rauskommt. Aber dazu an anderer Stelle einmal mehr, weil es sonst diesen bereits sehr länglichen Beitrag entgültig sprengen würde.
Zum Abschluss
Bliebe beim Abschluss dieses Beitrags nur noch zu erwähnen, dass dieser Parser bei weitem nicht vollständig ist und durchaus eine Reihe von Problemen aufweist, die auf Anhieb nicht auffallen mögen. Aber bereits bei Dingen wie einem Operator, der abhängig vom nächsten Schlüsselwort binär oder trinär ist, scheitert der Parser in dieser Form. hierfür lässt sich prinzipiell eine Lösung finden, die durch ein „Look Ahead“ durch die canParse-Methode möglich ist, aber die hierfür am Parser nötigen Änderungen sind nicht offensichtlich und führen wie eine ganze Reihe anderer möglicher Änderungen etwas zu weit. Interessanterweise lässt sich die foreach-Syntx von PHP jedoch parsen, obwohl diese variabel ist, da man mit Hilfe des =>-Operators als Hilfsmittel beide Fälle für den Schleifenkopf abdecken kann.
Ich habe in diesem Beitrag bewusst auch nicht die Implementierung aller Operatoren angegeben, da diese bis auf wenige Ausnahmen offensichtlich sind und daher hier unnötig ~400 Zeilen verschlucken würden (Ja, die Operatoren erzeugen auf Grund ihrer Anzahl extrem Spaghetti-Code). Wer den gesamten Parser einmal haben möchte, kann mir bescheid geben, dann sende ich ihm eine Kopie.
Ansonsten hoffe ich, dieser Beitrag war informativ. Wer noch fragen hat, darf diese wie immer gern in den Kommentaren anbringen, oder direkt an mich via Mail zusenden.
Entwickelst du den Parser noch weiter?
Kommentar by neo — 08.03.2011 @ 23:47:49