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:
///////
// Parser and lexer have to be created only once! They create two files you can use later
//////
// 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
// These are the created files
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…
Nachtrag September 2008
Um es klarer zu beschreiben: PHP_LexerGenerator und PHP_ParserGenerator werden nur zum erzeugen des Lexers und des Parsers gebraucht. Es werden zwei php-Dateien generiert, die ganz normal verwendet werden können.
2007-11-01 um 12.11 pm
Danke, habe es mal meinem Programierern zum Testen gegeben. Werde weiter darüber berichten
2007-11-14 um 6.31 pm
Grossartig, danke vielmals! (Leider gibt es ja sonst keinen Beispielcode fuer PHP_ParserGenerator…)
2008-05-19 um 2.57 pm
Hi,
bin gerade über dein Beispiel gestolpert. Man kann mit lemon auch Prioritäten für einzelne Regel festlegen.
%left MULTIPLICATION DIVISION.
%left UNARY.
expression(res) ::= PLUS expression(e). [UNARY] { res = +e; }
expression(res) ::= MINUS expression(e). [UNARY] { res = -e; }
2008-05-20 um 9.35 am
@Boris Ui, spannend! Vielen Dank!!! Das vereinfacht einiges…
2008-08-28 um 3.42 pm
Hi skaldrom,
ich habe diesen Artikel (eine-eigene-programmiersprache-erschaffen-lexer-und-parser-in-php) gelesen und würde mich gerne ein wenig mit dir drüber austauschen, sofern du da Interesse dran hast. Leider habe ich keinerlei Kontaktmöglichkeiten auf deiner Website gefunden. Deshalb schmier ich hier einen Kommentar in deinen Blog ;-P.
EMail müsstest du ja sehen können
Grüße Rylon
2008-08-28 um 3.52 pm
Das klingt interessant… Ich habe mich schon gemeldet…