LEXERBau fuer PHP

[target]

Hallo an alle Hardcore-phpler.

Hier geht es nicht direkt um PHP, sondern viel eher um einen Algorithmus, wie man einen Lexer in PHP implementiert.

Ausfuehrlich:
Ich moechte eine kleine Programmiersprache basteln, die dann von PHP interpretiert wird.

Dafuer brauche ich einen sog. Lexer, der den Quellcode der zu interpretierenden Sprache ausliest, in tokens zerlegt, und diese Tokens dann an den Interpreter schickt.

Jetzt wollte ich einfach mal ne Diskussion anfangen, wie man diesen Lexer am guenstigsten implementiert.

Ich bin auf vernuenftige Beitraege gespannt!


P.S. Hier mal ein kurzel Beispiel mit ein paar Elementen der Sprache:

[quest]
[asign $x="Beispielstring mit whitespaces"]
[asign $z=5]
[if $z>666]
 Das hier ist normaler Text, der auf dem Bildschirm ausgegeben wird.
 Hier muessen whitespaces und Zeilenumbrueche erhalten bleiben.
[/if]
[/quest]

ein token waere z.b. [asign $z=5] in einem vernuenftigen Format, z.B.
$token[typ] = "asign"
$token[args] = "$z+5"
$token[line]=3

Noch eine Bemerkung: ich frage mich im moment vor allem, wie man am besten mit whitespaces umgeht, da diese im code keinerlei bedeutung haben sollten, in strings aber beibehalten werden muessen.

 

[mefistulo]

Macht es Sinn mit einer Scriptsprache eine weiter zu Parsende Sprache zu schreiben. Gut, Templates (vorallem Smarty) sind eine eigene Scriptsprache, die mit PHP umgesetzt worden sind. Bei Fragen zu Parsern und Compilern kann ich dir ich dich wenn du willst ein meinen Kollegen weiterleiten, der gerade eine XQuery Implementierung (Parser, Compiler) macht. Sonst gibt es gute Vorlesungen und Literatur bezüglich diesem Thema. Meines Wissens ein Guru von der ETH in Zürich hat "Pascal" grundlegend geprägt mit seinen Compiler und Parser Knowhow. War glaube ich Niklaus Wirth (Buch "Grundlagen und Techniken des Compilerbaus")

Dein Syntax errinnert an BB-Code. Bei PEAR gibt es einen BB-Code Parser. Als Grundlage sicherlich nicht schlecht.

Was ist dein Verwednungszweck?

Habe noch was gefunden von Harry Fuecks: Implementing Lexers in PHP

 

[Sicaine]

hm warum muss man den alles immer neu erfinden? Ich sehs als nich wirklich nötig geschweige den als Sinnvoll an.

 

[target]

ich bin dabei ein browsergame zu basteln, in dem es auch quests geben soll.
Diese quests sollen von mehreren Leuten geschrieben werden (auch von erfahrenen Spielern) und dafür ist php 1. zu mächtig, 2. zu kompliziert.
Deshalb eine eigene Questsprache, die ich den Bedürfnissen anpassen kann.

mir gehts nicht drum, simplen bbcode zu parsen.
leider hilft mir auch der bbparser (den hatte ich mir schon mal runtergeladen) nicht wesentlich weiter, da der eben nur textteile durch htmlcode ersetzt, allerdings gibt es da keine Wertzuweisungen [asign $var=value] und keine if-bedingungen etc.

So viel zum Sinn oder Unsinn des Parsers in php.
Hat vielleicht schon jemand erfahrung mit parsern und allem was dazugehört gesammelt? evtl auch in einer anderen Sprache? Wie gesagt, hier gehts hauptsächlich um den Logarithmus, weniger um die konkrete umsetzung in php.

 

[hpvw]

Du könntest Dir einen Parser in Anlehnung an Automaten/Touringmaschinen bauen.
Da diese aber Zeichen für Zeichen vorgehen ist das sehr langsam.
Kombiniert mit regulären Ausdrücken, also abweichend von dem Zeichen für Zeichen Konzept könnte man das sicher beschleunigen. Mit preg_match und preg_match_all, auch mit dem Parameter "Versatz" (dt. php.net Version), könntest Du Deinen Code erstmal zerlegen.
Ich würde ihn dann in ein mehrdimensionales Array zerlegen, um einen ParseTree zu erhalten.

$token[0]['typ']="";
$token[0]['wert1']="";
$token[0]['wert2']="";
$token[0]['...']="";
$token[0]['subtokens'][0]['typ']="";
$token[0]['subtokens'][0]['...']="";
$token[1]['typ']="";
$token[1]['wert1']="";
$token[1]['wert2']="";
$token[1]['...']="";
$token[1]['subtokens'][0]['typ']="";
$token[1]['subtokens'][0]['...']="";
$token[1]['subtokens'][1]['typ']="";
$token[1]['subtokens'][1]['...']="";

So in der Art würde ich das Array aufbauen.

Die Leerzeichen sollten bei Verwendung von regulären Ausdrücken entfernbar/ignorierbar sein.

Ich kann Dir mal einen Beispielausdruck für eine TemplateSyntax hinschreiben:
Die Syntax ist kurzgefasst ungefähr so:

<[var varname weitererParameter="Text Bla" nochEinWeitererParameter=andererParameter]>
" im Text ist \" und \ im Text \\

Der reguläre Ausdruck der das unabhängig von Leerzeichen und Zeilenumbrüchen und Tabs zwischen den Parametern parsed sieht so aus (ich habe sicher noch nicht jede Eventualität getestet, bin also jederzeit für Fehlermeldungen dankbar):

        $splits = preg_match_all("/<\[([a-zA-Z0-9_]+)"
            ." ([\/a-zA-Z0-9_-]+)"
            ."(([\n\t\r ]*([a-zA-Z0-9_]+)="
            ."([\"](()|(.*?[^\\\\])|(.*?([\\\\][\\\\])+?))[\"]|"
            ."[a-zA-Z0-9_]+))*)\]>/",
            $templateContent,$matches,PREG_SET_ORDER|PREG_OFFSET_CAPTURE);

Vielleicht konnte ich Dir ja ein paar Anregungen geben, auch wenn es nicht genau Dein Problem trifft.
Aber, wenn Du Dich an sowas rantraust, gehe ich einfach mal davon aus, dass Du das abstrahieren und auf Dein Problem übertragen kannst.

Ich bin selbst gerade dabei, zu überlegen, wie ich aus bbCode ähnlicher Syntax 100% valides XHTML erzeugen kann, ohne irgendwelche DIV's rumzubauen und werde das wohl über einen ParseTree lösen. Bitte schreibe doch, wenn Du weiterkommst, was Du als "richtigen" Weg empfunden hast.

Gruß hpvw

 

[target]

ich bin grad dabei mir ne gramatik für den Lexer zu schreiben. die sieht dann in etwa so aus:

program -> Symprogram (block)+
Symprogram -> "[quest]"
block -> Sprungmarke (statement)+
Sprungmarke -> ("["."(0-9)+"."]")
statement -> (print)* (assignment)* (bedingung)* ......
print -> ....
assignment -> "[asign " varname "=" expression "]"
varname -> ("alle zeichen die für Variablen zulässig sind")
expression -> (zahl)? (string)? (plusexpression)? (varname)?
zahl ->("0-9")+ (",".("0-9")+)?
string -> "\"" ("a-z...")+ "\""
plusexpression -> expression "+" expression
......

Das muss ich dann nur noch in den Syntax für preg_match_all bringen, mit dem ich mich noch nicht auseinandergesetzt hab.
Aber so kann der Lexer dann jedes element aus dem Code erkennen, als token zusammenfassen und an den parser schicken. und das ganze ist sehr flexibel und schnell erweiterbar.
whitespaces werden da im mom noch nicht beachtet, aber das is dann ja auch kein problem mehr.

Ich glaube, das is ne recht vernünftige Lösung, die allerdings erstmal n Brocken Arbeit is... mal schaun, ob das was wird

 

[Sicaine]

Und das mit der Scriptsprache kannst nich gleich sagen?

Hierfür gehste mal auf http://www.softgames.de/developia und suchst dir bei tuts "Meine eigenen Scriptsprache" oder sowas raus. Ne eigene Scriptsprache is nämlich ein kleines bischen komplizierter

 

[target]

dankeschoen, der link is recht interessant, allerdings ist gleich im ersten teil des tuts die Rede von CppCC .
Sowas steht mir allerdings in php nicht zur verfuegung, d.h. selber basteln.
Und genau darum geht es ja unter anderem.