Technik, Gothic und Anderes

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

  • Kategorien

  • Tags

  • Archiv

  • Links

    zu Bee5

    blog.oncode.info läuft bei Cyon und ich bin sehr glücklich damit.

Eine eigene Programmiersprache erschaffen? Lexer und Parser in PHP!

Geschrieben von skaldrom am 25. October 2007

Ich will Gott sein!

Paper SnippetsWer 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 Antworten zu “Eine eigene Programmiersprache erschaffen? Lexer und Parser in PHP!”

Kommentare

  1. Franz Reinthaler Schreibt:

    Danke, habe es mal meinem Programierern zum Testen gegeben. Werde weiter darüber berichten

  2. smee Schreibt:

    Grossartig, danke vielmals! (Leider gibt es ja sonst keinen Beispielcode fuer PHP_ParserGenerator…)

  3. Boris Schreibt:

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

    %left PLUS MINUS. <br>
    %left MULTIPLICATION DIVISION. <br>
    %left UNARY. <br>
    <br>
    expression(res)  ::= PLUS expression(e). [UNARY] { res = +e; } <br>
    expression(res)  ::= MINUS expression(e). [UNARY] { res = -e; } <br>
  4. skaldrom Schreibt:

    @Boris Ui, spannend! Vielen Dank!!! Das vereinfacht einiges…

  5. Rylon Schreibt:

    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

  6. skaldrom Schreibt:

    Das klingt interessant… Ich habe mich schon gemeldet…

  7. Taras Schreibt:

    Thanks, it really ;) have worked for me!

  8. OriginalCopy Schreibt:

    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.

  9. skaldrom Schreibt:

    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…

  10. OriginalCopy Schreibt:

    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).

  11. skaldrom Schreibt:

    Klingt Interessant, ich hab Dir gemailt.

  12. Bountin Schreibt:

    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.

  13. skaldrom Schreibt:

    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.

  14. Bountin Schreibt:

    Jaa ich hab etwas sehr hilfreiches gefunden, was vielleicht auch OriginalCopy hilft: EBNF von PHP: http://www.icosaedro.it/articoli/php-syntax-ebnf.txt

  15. SheldonC Schreibt:

    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.

  16. skaldrom Schreibt:

    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?

  17. SheldonC Schreibt:

    Hi,
    ja, vielen Dank schon mal. Das ist ein guter Anfang für mich!

Trackbacks


  1. Parser für logische Ausdrücke - Seite 2 - php.de

    […] dann aber doch wieder erinnern, und bei der weiteren Suche im Web bin ich auf folgendes gestoßen: Eine eigene Programmiersprache erschaffen? Lexer und Parser in PHP! | Technik, Gothic und Anderes Dort wird kurz erläutert, wie mit einem Lex aus dem Pear Paket ein Interpreter für arithmetische […]


  2. “hello world” parser for lemon • PHP Help Coding Programming

    […] used this (German) tutorial and yes it’s nice to have a calculator tutorial, but at the end, I want to parse some more […]

  3. Lassen Sie eine Antwort hier...

    XHTML: Sie können folgende Tags verwenden: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


    2 × = two