Ich will Gott sein!

Paper Snippets 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> ::= '-' <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_ParserGenerator-0.1.5
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

<?php
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

/* This is an example for a Parser in PHP */
%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:

<?php
///////
// 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.

19 Gedanken zu „Eine eigene Programmiersprache erschaffen? Lexer und Parser in PHP!“

Franz Reinthaler sagte am 1. November 2007 um 12:11 :

Danke, habe es mal meinem Programierern zum Testen gegeben. Werde weiter darüber berichten
smee sagte am 14. November 2007 um 18:31 :

Grossartig, danke vielmals! (Leider gibt es ja sonst keinen Beispielcode fuer PHP_ParserGenerator…)
Boris sagte am 19. Mai 2008 um 14:57 :

Hi,
bin gerade über dein Beispiel gestolpert. Man kann mit lemon auch Prioritäten für einzelne Regel festlegen.

%left PLUS MINUS. 
%left MULTIPLICATION DIVISION. 
%left UNARY. 
 
expression(res) ::= PLUS expression(e). [UNARY] { res = +e; } 
expression(res) ::= MINUS expression(e). [UNARY] { res = -e; }
skaldrom sagte am 20. Mai 2008 um 09:35 :

@Boris Ui, spannend! Vielen Dank!!! Das vereinfacht einiges…
Rylon sagte am 28. August 2008 um 15:42 :

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
skaldrom sagte am 28. August 2008 um 15:52 :

Das klingt interessant… Ich habe mich schon gemeldet…
Pingback: Parser für logische Ausdrücke - Seite 2 - php.de
Taras sagte am 23. Dezember 2008 um 16:19 :

Thanks, it really 😉 have worked for me!
OriginalCopy sagte am 30. Oktober 2009 um 15:33 :

Wie würde man den Lexer schreiben müssen, sodass er eigentlich Tokens aus dem Stream token_get_all() zurückliefert?

Ist es möglich, ohne die Verwendung von PHP_LexerGenerator, dies zu implementieren? Bitte einen Beispiel, der von der Eingabe ‚<?php $foo = $bar;" ausgehend, einen Parsebaum erstellt.
skaldrom sagte am 30. Oktober 2009 um 17:09 :

Das ist nicht so einfach. Um den Parsebaum zu erstellen, brauchst Du die EBNF von PHP.

Die Funktion token_get_all() verwendet eigene Tokenwerte, die mit dem im Parser generierten nicht identisch sind. Man müsste sie also synchronisieren.

Einen PHP-Parser in PHP zu erstellen ist ein aufwändigeres Projekt, bitte hab Verständniss, dass ich das nicht mal so nebenher machen kann…
OriginalCopy sagte am 30. Oktober 2009 um 23:48 :

Das ist mir bewußt, deshalb habe ich mich auch in der Anfrage nur auf 3 Symbole beschränkt: T_VARIABLE, ‚=‘ und ‚;‘ (naja und es wäre noch T_WHITESPACE, das ignoriert werden kann, ist aber ein kleines Detail). Mich würde nur die Vorgehensweise interessieren (versuche gerade einen PHP-Subset von nur 10 Tokentypen zu schreiben), nicht das komplette AST für PHP (was eh in Zend/zend_language_parser.y steht).
skaldrom sagte am 31. Oktober 2009 um 20:01 :

Klingt Interessant, ich hab Dir gemailt.
Bountin sagte am 6. November 2009 um 13:39 :

Ich möchte für ein Browsergame eine Skriptsprache entwickeln, mit der die Game Designer arbeiten können ohne Kenntnisse von PHP zu haben, aber trotzdem relativ ungebunden sind. Zuerst habe ich an RegEx gedacht und angefangen damit zu arbeiten, aber schon nach kurzer Zeit haben sich Ausnahmen und Fehler gehäuft. Dann bin ich auf dieses Blogeintrag gestoßen und hab mir das mal angeschaut und ausprobiert.

Wäre es mit PHP_{Lexer,Parser}Generator möglich so eine Skriptsprache zu bauen oder gibt es vielleicht eine andere Lösung (abgesehen von jedem Designer ein PHP Buch in die Hand zu drücken und das Resultat durch eval() zu jagen)?

Vielleicht noch ein paar Worte zu dem Umfang der Skriptsprache: Es sollen die typischen Kontrollstrukturen vorhanden sein, sowie „normales Rechnen“ (+-*/%) und vorallem das wichtigste: Vordefinierte Funktionen, die eine Art Wrapper für Funktionen der bereits existierenden Klassenstruktur sind.
skaldrom sagte am 6. November 2009 um 15:38 :

Ja, durch dieses Tal des Leidens bin ich auch gegangen: Zuerst mit RegEx und viiiiiiiiiiiiielen „ifs“, bis es nur noch ein Chaos ist.

So über den Daumen gepeilt denke ich, dass diese beiden Tools echt ideal sind für Dein Use Case.
Bountin sagte am 6. November 2009 um 18:40 :

Jaa ich hab etwas sehr hilfreiches gefunden, was vielleicht auch OriginalCopy hilft: EBNF von PHP: http://www.icosaedro.it/articoli/php-syntax-ebnf.txt
SheldonC sagte am 14. Dezember 2009 um 18:08 :

Hallo.
Das ist ein sehr gutes Beispiel zu den leider sehr schlecht dokumentierten Generatoren.
„Eine eigene Programmiersprache“ würde aber auch Kontrollstrukturen abverlangen. Gibt es eine Dokumentation, wie man dem ParserGenerator z.B. „if/else“ beibringen kann?
Ich möchte eine simple Pseudosprache erstellen und bin für jede Hilfe dankbar.
skaldrom sagte am 15. Dezember 2009 um 16:17 :

Eigentlich würde das im EBNF ganz ähnlich aussehen, beispielsweise – in einer einfachen version – so:

ALTERATION ::= ‚if‘ BOOLEANTERM ‚then‘ BLOCK ‚else‘ BLOCK ‚end if‘

BLOCK wäre eine liste von STATEMENTs, und ALTERATION ist auch ein Statement, so dass es verschachtelt werden kann. Ist das ein Start für Dich?
SheldonC sagte am 17. Dezember 2009 um 12:10 :

Hi,
ja, vielen Dank schon mal. Das ist ein guter Anfang für mich!
Pingback: “hello world” parser for lemon • PHP Help Coding Programming

Technik, Gothic und Anderes

Technik ist Spiel, Gothic ist ernst und Zeit hat man zuviel

Eine eigene Programmiersprache erschaffen? Lexer und Parser in PHP!