Eine eigene Programmiersprache erschaffen? Lexer und Parser in PHP!
Geschrieben von skaldrom am 25. October 2007
Ich will Gott sein!
Wer träumt nicht davon: Eine eigene Programmiersprache, denn der Syntax und das Wort sind Ausdruck! Einen Schritt weiter gehen und vom Programmiersprachenanwender zum Programmiersprachenerschaffer aufsteigen! Auch dies ist nun möglich in PHP, doch leider nur mit minimaler Dokumentation.
Ich gehe davon aus, dass die Leserin/Der Leser Grundlagen im Compilerbau besitzt. Ansonsten müsste man sich diese noch aneignen. Compilerbau ist rekursiv und somit göttlich! *schwärm*.
Das Beispiel
Ich möchte einen Interpreter bauen für normale, arithmetische Ausdrücke wie 9*(8+6)-2/(-4). Klar könnte man diesen einfach durch eval hauen, aber erstens macht das nicht so viel Spass und zweitens ist dieses Beispiel sowas wie das Hello World des Compilerbaus.
Als BNF habe ich folgendes vor:
<Expression> ::= '-' <Expression> // Unäres - (Vorzeichen)
<Expression> ::= <Term>
<Expression> ::= <Expression> '+' <Term>
<Expression> ::= <Expression> '-' <Term>
<Term> ::= <Factor>
<Term> ::= <Term> '*' <Factor>
<Term> ::= <Term> '/' <Factor>
<Factor> ::= NUMBER // Ok, hier hab ich abgekürzt ;) Soll der Lexer erledigen...
<Factor> ::= '(' <Expression> ')'
Ein Problem stellen die unären Plus- und Minusoperatoren dar. Sie besitzen das gleiche Symbol, nicht aber die gleiche Priorität wie ihre binären Kollegen. Lemon erlaubt keine änderung der Priorität nach Regeln und so funzen jetzt halt auch Konstrukte wie —+++—+1…
Die Werkzeuge
Ich verwende PHP_LexerGenerator, der kompatibel zum re2c Format ist und den PHP_ParserGenerator der in grossen Teilen dem LEMON Parser Generator entspricht. Heruntergeladen werden können sie mittels folgenden Zeilen, die allerdings unter Umständen noch eine Anpassungen der Versionsnummer brauchen:
pear install channel://pear.php.net/PHP_LexerGenerator-0.3.4
Als einziges, weiteres Beispiel für diese Libs ausserhalb der Doku habe ich nur dieses Drupalmodul gefunden.
Die Realisierung
Der Lexer
Für den Lexer muss eine plex Datei erstellt werden. Sie beinhaltet den Rumpf des Lexerobjekts und die lexikalischen Regeln:
TermLexer.plex
class TermLexer
{
private $data;
public $counter;
public $token;
public $value;
public $node;
public $line;
private $state = 1;
function __construct($data)
{
$this->data = $data;
$this->counter = 0;
$this->line = 1;
}
/*!lex2php
%input $this->data
%counter $this->counter
%token $this->token
%value $this->value
%line $this->line
number = /[0-9]+(\.[0-9]+)?/
multiplication = /\*/
division = @/@
plus = /\+/
minus = /\-/
openP = /\(/
closeP = /\)/
other = /./
*/
/*!lex2php
%statename START
multiplication {
$this->token = TermParser::TP_MULTIPLICATION;
//echo "multiplication: ".$this->value."\n";
}
division {
$this->token = TermParser::TP_DIVISION;
//echo "division: ".$this->value."\n";
}
plus{
$this->token = TermParser::TP_PLUS;
//echo "plus: ".$this->value."\n";
}
minus{
$this->token = TermParser::TP_MINUS;
//echo "plus: ".$this->value."\n";
}
openP {
$this->token = TermParser::TP_OPENP;
//echo "openP: ".$this->value."\n";
}
closeP {
$this->token = TermParser::TP_CLOSEP;
//echo "closeP: ".$this->value."\n";
}
number {
$this->token = TermParser::TP_NUMBER;
//echo "number: ".$this->value."\n";
}
other {
return false;
}
*/
}
So richtig laufen tuts aber noch nicht, da er Konstanten des Parsers benötigt. Die stehen erst zur Verfügung wenn wir den Parser auch gebaut haben.
Der Parser
Der Parser wird vom Lexer mit Tokens gefüttert. Die Notation im Lemon-Style unterscheidet sich von Lex und Yacc, ist aber durchaus logisch. Hier der ganze Code, mal hingeknallt:
TermParser.y
%name TP_
%declare_class {class TermParser}
%include_class
{
// states whether the parse was successful or not
public $successful = true;
public $retvalue = 0;
private $lex;
private $internalError = false;
function __construct($lex) {
$this->lex = $lex;
}
}
%token_prefix TP_
%parse_accept
{
$this->successful = !$this->internalError;
$this->internalError = false;
$this->retvalue = $this->_retvalue;
echo "WORKED!!\n\n";
}
%syntax_error
{
$this->internalError = true;
echo "Syntax Error on line " . $this->lex->line . ": token '" .
$this->lex->value . "' count ".$this->lex->counter." while parsing rule: ";
foreach ($this->yystack as $entry) {
echo $this->tokenName($entry->major) . '->';
}
foreach ($this->yy_get_expected_tokens($yymajor) as $token) {
$expect[] = self::$yyTokenName[$token];
}
echo "\n";
throw new Exception('Unexpected ' . $this->tokenName($yymajor) . '(' . $TOKEN. '), expected one of: ' . implode(',', $expect));
}
%left PLUS MINUS.
%left MULTIPLICATION DIVISION.
start(res) ::= expression(expr). { res = expr; }
/* Unary minus or plus */
expression(res) ::= PLUS expression(e). { res = +e; }
expression(res) ::= MINUS expression(e). { res = -e; }
/* The common stuff */
expression(res) ::= term(t). { res = t; }
expression(res) ::= expression(e1) PLUS term(t2). { res = e1+t2; }
expression(res) ::= expression(e1) MINUS term(t2). { res = e1-t2; }
term(res) ::= factor(f). { res = f; }
term(res) ::= term(t1) MULTIPLICATION factor(f2). { res = t1*f2; }
term(res) ::= term(t1) DIVISION factor(f2). { res = t1/f2; }
factor(res) ::= NUMBER(n). { res = n; }
factor(res) ::= OPENP expression(e) CLOSEP. { res = e; }
Generieren der eigentlichen Parser und Lexer
Damit Parser und Lexer generiert werden und Terme gefüttert werden können, sei hier ein kleines Beispiel gegeben:
// Create Parser
passthru('php /usr/share/php/PHP/ParserGenerator/cli.php TermParser.y');
// Create Lexer
require_once 'PHP/LexerGenerator.php';
$lex = new PHP_LexerGenerator('TermLexer.plex');
# Test
include_once("TermParser.php");
include_once("TermLexer.php");
$teststr='9*(8+6)-2/(-4)';
$lex = new TermLexer($teststr);
// $lex = new TermLexer(file_get_contents($lexerfile));
echo "-------------------------------\n";
echo " Parsing $teststr\n";
echo "-------------------------------\n";
$parser = new TermParser($lex);
while ($lex->yylex()) {
echo "Parsing {$lex->token} Token {$lex->value} \n";
$parser->doParse($lex->token, $lex->value);
}
$parser->doParse(0, 0);
print "Returnvalue: ".$parser->retvalue."\n";
?>
Und nu?
Nun viel Spass… Ich bin auf der Suche nach der EBNF für RegExps, wenn die jemand hat 
…. Ihr könnt den ganzen Code hier auch downloaden…
Ähnliche Artikel
Eingeordnet in Theorie und Schnipsel | 7 Komentare »
Auf vielfachen Schülerwunsch hin habe ich einen Block für unser Learning Management System 
An unserer Schule wird 
Die Regeln von Schere, Stein, Papier sind weitherum bekannt. Zwei Mitspieler zeigen gleichzeitig ein Symbol, danach wird ausgewertet: Schere wird von Stein geschlagen → Stein wird von Papier geschlagen → Papier wird von Schere geschlagen. Die Gewinne sind im Kreis herum (zirkulär wie der geneigte Klugscheisser sagen würde). Diese Kreisbewertung gibt es oft, auch wenn mir jetzt überhaupt kein Beispiel dazu einfällt 
.
Normalerweise läuft es mir kalt den Rücken runter wenn ich das Wort Pattern höre. Ich will keine 
. Nun muss man halt zusammenleimen, sonst wärs noch kürzer…