Compilerbau in Python

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Samstag 27. Oktober 2007, 23:47

Edit (Leonidas): Von dem Thread Python parsergeneratoren abgetrennt.

Hallo,

Kontext: Ich wollte einen Compiler bauen und habe Parsergeneratoren gesucht. Dabei ist meine Wahl nach einigem Abwiegen auf PLY gefallen...

Habe in den letzten Tagen etwas gewerkelt und muss sagen, dass ich mit meiner Wahl ziemlich zufrieden bin. Ein Argument, welches sehr stark für PLY spricht, ist die großartige Dokumentation. Sie ist kurz und bündig und hat mir bisher vermutlich mehr geholfen als das Textbook, welches ziemlich langatmig ist.

Der Parsergenerator ist sehr angenehm zu nutzen, wenn man sich erstmal mit der etwas eigentümlichen Art von PLY vertraut gemacht hat. Er ist Hybrid, d.h. die Tabellen werden automatisch in Python-Code (oder Code der von der Python-VM ausgeführt werden kann, Beispiel) generiert, der Rest ist handgeschrieben. Ich bin zwar nicht der Fan von Codegeneration, aber das ist ein guter Kompromiss. Ich habe den Parser ganz einfach mit meinem schon fertigen AST verbinden können (dabei noch einen teilweise selbstgeschriebenen Call-Graph-Tracer verwendet, für Debugging sehr nett).

Und demnächst geht es an MiniJava selbst..

Edit (Leonidas): Von dem Thread Python parsergeneratoren abgetrennt.
Zuletzt geändert von Leonidas am Samstag 3. November 2007, 12:55, insgesamt 1-mal geändert.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Samstag 3. November 2007, 00:57

@Leonidas: Was macht denn Dein MiniJava-Compiler?
Ich habe mich jetzt ein bisschen mit PLY beschäftigt. Das scheint mir wirklich eine gute Wahl zu sein. Die beiliegenden Examples lassen aber nicht erkennen, wie man damit einen Compiler erzeugt. Ich habe lediglich ein Beispiel für einen abgespeckten C-Compiler gefunden: http://people.cs.uchicago.edu/~varmaa/mini_c/. Der sieht aber ziemlich kompliziert aus. Es würde mich deshalb interessieren, wie Du das realisierst.
Übrigens: Hast Du irgendwelche Bücher über Compilerbau gelesen? Was könntest Du da empfehlen? Das Drachenbuch wird ja etwas kontrovers beurteilt.
MfG
HWK
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Samstag 3. November 2007, 10:15

HWK hat geschrieben:@Leonidas: Was macht denn Dein MiniJava-Compiler?
Ich habe gestern den Lexer für den Compiler fertig gestellt, werde wohl in nächster Zeit den Parser machen müssen.
Was ich dir anbieten kann ist ein kompletter Interpreter für Straight-Line-Programme (d.h. eine kleine Programmiersprache ohne Kontrollkonstrukte). Letztendlich sieht der Aufbau so aus:
  • Lexer generiert aus dem Bytestrom die Tokens
  • Parser hat Callbacks die auf Regeln in der Grammatik reagieren, erstellt daraus einen AST
  • dieser AST wird einfach nur noch evaluiert.
HWK hat geschrieben:Ich habe mich jetzt ein bisschen mit PLY beschäftigt. Das scheint mir wirklich eine gute Wahl zu sein. Die beiliegenden Examples lassen aber nicht erkennen, wie man damit einen Compiler erzeugt.
PLY ist nur ein Lexer und Parsergenerator, den Compiler zu schreiben bleibt einem selbst überlassen.
HWK hat geschrieben:Ich habe lediglich ein Beispiel für einen abgespeckten C-Compiler gefunden: http://people.cs.uchicago.edu/~varmaa/mini_c/. Der sieht aber ziemlich kompliziert aus. Es würde mich deshalb interessieren, wie Du das realisierst.
Danke, das kannte ich noch nicht - eignet sich aber sicherlich gut um daraus Dinge abzuschauen. Wie ich den Compiler realisiere weiß ich selbst noch nicht. Vermutlich werde ich den AST in Zwischencode (Assembler?) wandeln.

Womit ich wohl noch experimentieren werde ist das Extrinsic Visitor Pattern.
HWK hat geschrieben:Übrigens: Hast Du irgendwelche Bücher über Compilerbau gelesen? Was könntest Du da empfehlen? Das Drachenbuch wird ja etwas kontrovers beurteilt.
Ich habe jetzt sowohl das Drachenbuch als auch Modern Compiler Implementation in Java auf dem Schreibtisch liegen. Bisher bin ich von beiden nicht so sehr berauscht, was teilweise auch daran liegt, dass ich die Theorie etwas unter den Tisch fallen lasse (ich habe aber zu viel zu tun, als das ich mich mit der Theorie jetzt ausgiebig beschäftigen könnte).
Es gibt auch noch das Tutorial Let's Build a Compiler von Jack Crenshaw.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Samstag 3. November 2007, 11:41

Ich habe noch folgende Docs gefunden:
http://vhb.fh-regensburg.de/co/kursdate ... o_buch.pdf und http://www.oberon.ethz.ch/WirthPubl/CBEAll.pdf. Gerade Wirths Buch wird oft gelobt.
Lexer generiert aus dem Bytestrom die Tokens
Wie machst Du das mit dem Bytestrom? Kannst Du dabei die Daten byteweise an den Lexer senden? Bisher habe ich die Daten immer zeilenweise an den Lexer/Parser gesandt.
Falls das byteweise ginge, könnte ich damit ein Terminalprogramm, in dem ich die Daten bisher in einer FSM 'parse', evtl. etwas eleganter umschreiben.
Gibt es irgendwo Beispiele für das Erstellen eines Abstract Syntax Tree?
MfG
HWK
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Samstag 3. November 2007, 12:50

HWK hat geschrieben:Wie machst Du das mit dem Bytestrom? Kannst Du dabei die Daten byteweise an den Lexer senden?
Etwa so:

Code: Alles auswählen

lexer = lex.lex()
lexer.input("quellcode")
Hmm, das Wirth-Buch sieht in der Tat nicht schlecht aus. Werde ich mir ansehen, wenn es mal nicht weitergeht.

Habe grade eben die Idee mit dem Visitor verworfen und stattdessen über PJEs RuleDispatch generische Funktionen verwendet um einen AST zu prettyprinten. Ich muss sagen, das hat ziemlich gut funktioniert, nachdem ich die Nodes etwas angepasst habe (`child_nodes` eingefügt).

Wobei was generische Funktionen angeht muss ich zugeben, gibt es in Python echt viel zu entdecken: PyDispatcher und Louie, PyProtocols.dispatch aka RuleDispatch, Guidos Multimethods, Bob Ippolitos Multimethods, Ian Bickings Multimethods, David Mertz Multimethods (Charming Python-Artikel dazu). Ist ja fast so wie das Spiel mit den Web-Frameworks.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Samstag 3. November 2007, 14:38

Leonidas hat geschrieben:Etwa so:

Code: Alles auswählen

lexer = lex.lex()
lexer.input("quellcode")
Das ist klar. Ich hatte aber die Hoffnung, man könnte die Daten auch Byte für Byte übergeben. Über ein Netzwerk kommen die Daten schließlich nacheinander und ein Ende ist auch nicht vorhersehbar. Aber das geht wohl mit Lex nicht?!
MfG
HWK
Edit: Wo kann man sich über RuleDispatch informieren, möglichst mit Beispielen? Ich habe es mir zwar runtergeladen, aber was man damit machen kann, kann ich mir noch nicht so recht vorstellen.
Zuletzt geändert von HWK am Samstag 3. November 2007, 16:39, insgesamt 2-mal geändert.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Samstag 3. November 2007, 16:20

HWK hat geschrieben:Ich hatte aber die Hoffnung, man könnte die Daten auch Byte für Byte übergeben. Über ein Netzwerk kommen die Daten schließlich nacheinander und ein Ende ist auch nicht vorhersehbar. Aber das geht wohl mit Lex nicht?!
Hast du mal versucht `input()` mehrmals aufzurufen? Ich kann es gerade nicht testen..

Ansonsten denke ich mal, dass es technisch aus dem gleichen Grund nicht möglich ist, warum auch Pygments nicht mit Streams zureckt kommt: wegen `re`. Aber da musst du wohl birkenfeld fragen, wenn du die genauen Details wissen willst.

Edit:
HWK hat geschrieben:Edit: Wo kann man sich über RuleDispatch informieren, möglichst mit Beispielen? Ich habe es mir zwar runtergeladen, aber was man damit machen kann, kann ich mir noch nicht so recht vorstellen.
Schau dir doch die Charming Python-Artikel von David Mertz über PEAK an, Scaling a new PEAK (da geht es um Dispatch) und The Python Enterprise Application Kit (hier geht es eher um Protocols).
Man muss zugeben, PEAK hat schon durchaus interessante Seitenprojekte, PJE ist teilweise ziemlich erstaunlich.

Wobei für meinen Ansatz sich die anderen Dispatcher auch geeignet hätten. PyDispatcher wird ja beispielsweise in Django verwendet.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Samstag 3. November 2007, 16:43

Leonidas hat geschrieben:Hast du mal versucht `input()` mehrmals aufzurufen? Ich kann es gerade nicht testen..
Ja. Es wird immer nur der letzte Input ausgewertet.
Langsam durchschaue ich das mit Dispatch bzw. Multimethods.
Edit: Bei einfachen Anwendungen sind die Multimethods m.E. aber kaum ein Vorteil. Man kann das doch genauso gut mit If-Abfragen in einer einzigen Funktion lösen. Aber wenn man immer wieder Ergänzungen mit neuen Typen vornehmen muss, ist es wahrscheinlich schöner, eine neue Funktion für diese Typen hinzuzufügen als die einzige Funktion ständig zu verändern.
MfG
HWK
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Samstag 3. November 2007, 19:53

HWK hat geschrieben:
Leonidas hat geschrieben:Hast du mal versucht `input()` mehrmals aufzurufen? Ich kann es gerade nicht testen..
Ja. Es wird immer nur der letzte Input ausgewertet.
Naja, wenn es wirklich nötig ist, kannst du dich ja auch auf `ply-hack` anmelden und mit dem Autor darüber sprachen. Aber ich glaube nicht, dass ich in nächster Zeit das Bedürfnis haben werde, da Quelltext in Stücken einlesen zu lassen. Andererseits hindert dich nichts daran, einen eigenen Lexer zu schreiben. Habe heute sogar einen Blog-Post darüber gelesen, finde ihn im Moment aber nicht.
Es gibt ansonsten auch PyBison, welches scheinbar streaming unterstützt (siehe den Text zu PLY dort). Jedoch wurden in PLY 2.x einige Limitierungen aufgehoben (mehr als 100 verschiedene Token & LALR werden nun unterstützt).
HWK hat geschrieben:Edit: Bei einfachen Anwendungen sind die Multimethods m.E. aber kaum ein Vorteil. Man kann das doch genauso gut mit If-Abfragen in einer einzigen Funktion lösen. Aber wenn man immer wieder Ergänzungen mit neuen Typen vornehmen muss, ist es wahrscheinlich schöner, eine neue Funktion für diese Typen hinzuzufügen als die einzige Funktion ständig zu verändern.
Wobei RuleDispatch angeblich ziemlich performant sein soll. Wobei mich die Multimethods einfach nur an Überladen von Funktionen erinnern. Das kann aber nicht alles sein, ich vermute aber mal, dass die Projekte um PEAK rum noch einige Überraschungen beinhalten. Da kann man vermutlich noch etwas rausholen, aber im Moment brauche ich ja gar nichts besseres.

Kommt es nur mir so vor, oder sind Pocoo mit seinen Unterprojekten und PEAK mit dessen Unterprojekten vom Konzept her ähnlich? :D
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Samstag 3. November 2007, 22:21

Du hast recht:

Code: Alles auswählen

PLY's lexer requires the full input string to be made available in one chunk,
making it unsuitable for parsing streams of unpredictable length, whereas Bison and Flex can work from a continuous stream.
Aber leider:

Code: Alles auswählen

Presently, PyBison is only working on Linux (and possibly *BSD-based) systems.
Also nichts für mich auf Windows XP.
Nebenbei: Wie ist das mit AST? Kannst Du mal ein kleines Beispiel zeigen, wie Du den Baum erstellst?
MfG
HWK
Edit: Ah! Ich hab's doch für Windows gefunden: http://ppm.activestate.com/PPMPackages/ ... 32.2.2.zip. Leider nur 0.1.0.0 statt 0.1.8.
Edit2: Diese Seite sollte man sich ansehen: http://nedbatchelder.com/text/python-parsers.html. GOLD Parser sieht hier interessant aus, scheint aber etwas gewöhnungsbedürftig zu sein.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 4. November 2007, 11:06

HWK hat geschrieben:Aber leider:

Code: Alles auswählen

Presently, PyBison is only working on Linux (and possibly *BSD-based) systems.
Also nichts für mich auf Windows XP.
Du kannst versuchen es selbst zu kompilieren.
HWK hat geschrieben:Nebenbei: Wie ist das mit AST? Kannst Du mal ein kleines Beispiel zeigen, wie Du den Baum erstellst?
Schau mal in meinem Git-Repository,am besten checkst du das "lmu" Repository aus. Kannst aber auch einen Tarball ziehen. Dort findest du unter "colombo/parser.py" wie ich den AST konstruiere. Im Branch "colombo-maint" findest du hingegen einen AST-Evaluator der RuleDispatch einsetzt und einen Pretty-Printer für ASTs.

Ich werde einige Informationen auch noch auf dieser Seite versuchen aktuell zu halten. Also zum Beispiel Snapshots des Repositories.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Mittwoch 7. November 2007, 14:01

@Leonidas: Sorry, dass ich mich erst jetzt wieder melde. Ich bin momentan leider anderweitig sehr beschäftigt. Danke erst mal für den Link. Ich konnte Deinen Code allerdings noch nicht in Ruhe durcharbeiten. Die Erstellung des Baumes ist mir aber mittlerweile durch dieses Script klar: http://www.rexx.com/~dkuhlman/python_20 ... er_ply.txt.
Deine Auswertung des Baumes interessiert mich aber weiterhin. Ich werde mir also demnächst Deinen Code einmal genauer ansehen.
MfG
HWK
Zuletzt geändert von HWK am Mittwoch 7. November 2007, 15:45, insgesamt 1-mal geändert.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 7. November 2007, 14:07

Den Baum baue ich ganz ähnlich auf, nur dass ich dafür Klassen definiert habe, statt einen generellen 'ASTNode' zu verwenden. Das war, bevor ich mich mit dem Visitor-Pattern beschäftigt habe auch sinnvoll so. Jetzt würde ich vermutlich das ähnlich wie in dem von dir verlinkten Code machen oder, eher noch, die Klassen über Metaklassen erzeugen, das funktioniert dann auch mit den Multimethods (dieser Ansatz nicht direkt, da das Dispatch momentan auf den Typen aufbaut).
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 11. November 2007, 18:08

Status-Update: Ich habe nun (hoffentlich) eine korrekte Grammatik für MiniJava gebaut, die Parser-Tabelle zeigt keine Konflikte. Auf der Seite ist auch ein AST-Dump eines Factorial-Programmes zu finden, allerdings ist er etwas outdated, sieht nun inzwischen etwas besser aus.

Kommentare im Quelltext funktionieren nun ebenso, sowohl Single-Line Kommentare als auch Multi-Line Kommentare (für diese ändert man am einfachsten den Lexer-State, in `COMMENT`). Der Lexer zeigt nun bei Fehlern eine Fehlermeldung die ein `^` verwendet um auf das Problem zu zeigen (kommt sicher jedem bekannt vor, der den Python-Interpreter nutzt).

Achja, da ich darüber gestolpert bin: Ich habe Wirths Buch in Papierform durchgeblättert. Jedoch hat mir ein anderes Buch so beim blättern besser gefallen, ich glaube es war Compiler bauen mit UNIX (bin mir nicht sicher wie es hieß), welches zwar auch etwas älter ist, aber so wie ich das gesehen habe recht praxisnah ist. Kann man wohl für PLY übernehmen.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Antworten