Python Parsergeneratoren

[Leonidas]

Hallo!

Ich bin dabei eine Programmiersprache zu implementieren und suche im Moment Tools die mir dabei helfen. Optimalerweise bräuchte ich Python-Equivalents zu JLex oder JFlex und CUP.

Bisher habe ich die Wiki-Seite LanguageParsing gefunden, aber darüber hinaus echt wenig, daher würde es mich freuen wenn ihr mir ein paar Tipps in die richtige Richtung geben könntet.

[mitsuhiko]

Ich hab mir dir bis jetzt noch nicht wirklich angetan, weil die meisten *grausigen* Code generieren. Warum nicht Parser selber schreiben?

[birkenfeld]

Weil das zwar ne gute Übung ist, aber mit der Zeit langweilig wird?

[BlackJack]

Wenn ich einen Parser brauche verwende ich gerne PyParsing.

[Leonidas]

Warum nicht Parser selber schreiben?

Weil das mit Hand schreiben zwar nett ist, aber wie ich in der letzten Zeit gemerkt habe, sehr leicht zu Fehlern führt, dass man etwas übersetzt, etc. Das wäre eben ein Fall wo Unit-Testing *sehr* nützlich ist.

Ich habe von mitsuhiko noch Ned Batchelders Parserliste bekommen.

Was auf den ersten Blick so brauchbar aussah:

• pyparsing - BlackJacks Empfehlung
• ZestyParser - ist vielleicht mächtiger als pyparsing, aber die Syntax gefällt mir nicht besonders.
• yeanpypa (eine Mischung aus pyparsing und boost::spirit)
• SPARK (ist nun tatsächlich in Python enthalten - habe es geprüft) allerdings ist das letzte Release von 2002 und die Dokumentation ist nicht so berauschend. Es gibt allerdings einen Charming Python-Artikel von David Mertz
• Plex - vom Pyrex-Autor, recht aktuell aber leider nur ``lex``-Funktionalität, eine ``yacc/bison``-Kombi wäre praktischer.
• PLY von David Beazley, einer eher bekannten Person in der Python-Welt, auch ziemlich aktuell
• aperiot recht neue Software, sieht auf den ersten Blick brauchbar aus.
• Toy Parser Generator
• Parsing - scheint zumindest von den Spezifikationen ganz brauchbar zu sein. Kaum Dokumentation

[mitsuhiko]

Weil das zwar ne gute Übung ist, aber mit der Zeit langweilig wird?

Das mag schon sein aber ich hab noch nichts in Python gefunden, dass einen schönen Syntax Baum und sauberen Quellcode liefert

[Jona]

was ist mit javaCC?

[Granino]

Ich hab mir die bis jetzt noch nicht wirklich angetan, weil die meisten *grausigen* Code generieren. Warum nicht Parser selber schreiben?

Darüberhinaus zeigen Parser- oder Codegeneratoren ein grausiges Fehlerverhalten. Ein gutes Beispiel ist Python selbst. Wohl in der Hälfte aller Fälle führen einen die Fehlermeldungen in die Irre.

Beim rekursicen Abstieg (recursive descent) hat man das Fehlerverhalten dagegen voll im Griff.

Gruß Granino

[Leonidas]

was ist mit javaCC?

Generiert soweit ich sehe nur Java-Code. Da kann ich auch Bison-in-a-box nehmen, das aus dem Bison-C Python übersetzt

Alternativ auch ANTLR oder SableCC, die beide Python-Output (experimentell) unterstützen. Aber ich sehe eigentlich keinen Grund, eine Java-Software unnötigerweise ins Boot zu holen, da ich mit keinem dieser Tools Erfahrung habe habe ich somit auch keinen Vorteil dass ich es schon kenne.

[birkenfeld]

Darüberhinaus zeigen Parser- oder Codegeneratoren ein grausiges Fehlerverhalten. Ein gutes Beispiel ist Python selbst. Wohl in der Hälfte aller Fälle führen einen die Fehlermeldungen in die Irre.

Was meinst du denn damit?

[Leonidas]

Ok, soweit ich sehe kommen zwei in die engere Auswahl: PLY (weil es scheinbar extra für diesen Zweck geschrieben wurde) und pyparsing (weil es eine bessere Syntax als ZestyParser & Co hat + zudem Dokumentation).

Aperiot ist wegen der Codegeneration weggefallen, yeanpypa wegen der geringen Verbreitung, ZestyParser wegen der auf den ersten Blick echt unübersichtlichen API, SPARK weil mir die API da auch nicht gefällt und es unmaintained ausschaut, Plex wegen der geringen Verbreitung, TPG weden der API, Parsing wegen der geringen Verbreitung.

Schade, dass modelnine nichts mehr in die Richtung macht, sein Pyrr hätte eine brauchbare Alternative sein können.

[mitsuhiko]

Darüberhinaus zeigen Parser- oder Codegeneratoren ein grausiges Fehlerverhalten. Ein gutes Beispiel ist Python selbst. Wohl in der Hälfte aller Fälle führen einen die Fehlermeldungen in die Irre.

Was meinst du denn damit?

Code: Alles auswählen

[(foo])

Da kommt zb nur ein allgeimeiner "Syntax Error". Allerdings können auch generierte Parser schöne Debug Meldungen haben

[BlackJack]

Das ist aber keine Meldung, die in die Irre führt. Es wird ganz deutlich auf die erste schliessende, eckige Klammer verwiesen und genau da liegt auch das Problem.

[Granino]

@ Birkenfeld,
ein kleines Beispiel:

x = {2*3 + 4**5)

mit der Fehlermeldung: 'invalid Syntax' vor dem x.

Bei einem längeren Programmtext ist insbesondere für den Anfänger nicht klar, ob er den Fehler vor dieser Zeile oder ab dieser Zeile suchen muss.

Beim Parsen nach dem 'recursive descent' kann eine präzisere Meldung ausgegeben werden. Daneben wird die exakte Position (Spalte) markiert.
Weiterer Vorteil: Enthält ein längeres Programm gleich N Fehler, wird die Syntaxanalyse an der nächst möglichen Textpassage wieder aufgenommen. Mit etwas Glück werden in einem Durchgang alle N Fehler gemeldet.

Gruß Granino

[rayo]

Hi

Also bei mir zeigt er den Fehler bei der runden Klammer:

Code: Alles auswählen

>>>x = {2*3 + 4**5)
  File "<console>", line 1
    x = {2*3 + 4**5)
                   ^
SyntaxError: invalid syntax

Genau da wo er ist

*edit* ein angezeigter Fehler ist mir eigentlich lieber als 10 Folgefehler

Gruss

[birkenfeld]

@ Birkenfeld,
ein kleines Beispiel:

x = {2*3 + 4**5)

mit der Fehlermeldung: 'invalid Syntax' vor dem x.

Hier ist der "Fehlercursor" auch auf der schließenden Klammer.

Bei einem längeren Programmtext ist insbesondere für den Anfänger nicht klar, ob er den Fehler vor dieser Zeile oder ab dieser Zeile suchen muss.

Der Fehler kann immer irgendwo vor der angegebenen Stelle liegen, wenn man ein Konstrukt "falsch" anfängt und "richtig" beendet - wie oben mit den Klammern demonstriert.

Beim Parsen nach dem 'recursive descent' kann eine präzisere Meldung ausgegeben werden. Daneben wird die exakte Position (Spalte) markiert.
Weiterer Vorteil: Enthält ein längeres Programm gleich N Fehler, wird die Syntaxanalyse an der nächst möglichen Textpassage wieder aufgenommen. Mit etwas Glück werden in einem Durchgang alle N Fehler gemeldet.

Und mit etwas Unglück interpretiert dein Parser genau das Falsche in den Code hinein, und anstatt den Code an den 10 Stellen mit gemeldeten Fehlern zu korrigieren, musst du woanders etwas ändern. Soviel zum Thema "irreführend".

[Granino]

Tut mir leid,
aber ich habe den Einzeiler unter IDLE getestet, daher die Unterschiede.
Mein Test lief also nicht unter realen Bedingungen.

Doch das Problem ist nicht das Fehlerverhalten von Python, sondern ich möchte aufzeigen, dass Parser nach dem 'rekursiven Abstieg' ein exzellentes Fehlerverhalten haben. Und das liegt schlicht daran, dass der Programmierer exakt nach der Syntax den Parserteil programmiert. Jedem Nonterminal entspricht dann dem Aufruf einer (gleichnamigen) Prozedur.

Der Parser erhält von der lexikalischenn Analyse zu jedem Token (Variablennamen, Schlüsselwörter, Operatoren usw.) zugleich auch deren Zeile/Spalte im Quelltext zur genauen Positionsangabe des Fehlers.

Wenn der Anwender aber beispielsweise einem Pythonparser einen LISP-Quelltext anbietet wird es wohl problematisch. Doch wennn der Programmierer die wichtigsten Sprachen kennt, kann er sogar dafür sorgen, dass bei Verwendung fremder Sprachelemente sinnvolle Meldungen erscheinen. Anderes Beispiel

If a = b : # Wollte der Anwender hier '==' schreiben?

Ein intelligenter Parser würde am Gleichheitszeichen hier eine Warnung (per Option abschaltbar) ausgeben, dass es sich um eine Zuweisung und nicht um einen Vergleich handelt.

Unsinnige Fehlermeldungen sind fast nicht möglich. Der Preis: Der Parser muss völlig von Hand programmiert werden. Aber bei den automatisch generierten Parsern wird einem ja auch nichts geschenkt, die Syntax muss gewaltig überarbeitet werden, damit sie den Nebenbedingungen der Parsergenerators genügt.

Gruß Granino

[BlackJack]

Das umschreiben muss man bei rekursiv absteigenden Parsern doch auch machen. Linksrekursion beseitigen zum Beispiel. Wenn es nicht gerade um das Lehrbuchbeispiel eines einfachen Parsers für Rechenausdrücke geht, wird das alles per Hand in der Regel ziemlich mühselig zu implementieren.

[Leonidas]

Für alle die es interessiert, die vielleicht mal in die gleiche Situation kommen wie ich: habe mich nun für PLY entschieden.
Es funktioniert auch ziemlich gut, aber die API ist etwas seltsam (die Reihenfolge der Tokens über die Reihenfolge der ihnen zugeordneten Regulären Ausdrücke definieren? Was?!). Werde wohl auf der ``ply-hack`` ML das zur Sprache bringen.

Bisher habe ich allerdings nur einen funktionsfähigen Lexer gebaut (ist aber wirklich einfach gewesen), der Parser wird in den nächsten Tagen folgen.

[poker]

Hi, Leonidas.

Ich finde SimpleParse ganz gut Du musst natürlich die EBNF Beschreibung mögen. PyParsing finde ich irgendwie nicht so schön, da ich mich mit EBNF wohler fühle.

Nun mal ein par Fakten:
1. Fakt ist das die meisten Pure Python Parser Generatoren Arschlangsamen Code erzeugen PyParsing ist da so ein Kandidat und auch SimpleParse. -- Hängt natürlich davon ab was du implementieren willst. Der Python Gramma in PyParsing implementiert und dann mit ca. 10.000 - 30.000 Zeilen gefüttert ist unzumutbar...

2. Fakt ist das ich es auch so wie BlackBird sehe das ich bisher keinen Parser Generator gesehen habe, der schönen Code oder gar parsetree erzeugt.

3. Je nach dem was du da nun vorhast, ist es alldem aber erstmal eine sehr gute Idee den POC in Python mit nem Parser Generator zu schreiben, da du dein Konzept deiner Sprache(?) auf eine Zeitsparende Art testen kannst Anschließend, wenn du durch bist un dir gefällt was du siehst und dir die Geschwindigkeit ausreicht kannst ja bei der Implementation bleiben. Aber, spätestens wenn du wirklich ernsthaft vor hast eine Sprache(rweiterung) zu entwickeln der Public sein soll, dann würde ich nach dem POC den Parser in C implementieren:
a. Dafür kannst du dann wenn es auf Python aufsetzt, auch die sehr Highlevel Python-C-API nutzen und ne Extension schreiben.
b. Wenn es alerdings eine eigenständige Sprache wird, dann würde ich auf Pyhon gänzlich verzichten und komplett auf C setzen. Denn keiner hat bock auf einen Interpreter im Interpreter. (BTW: Falls du vorhast wirklich eine nue Sprach zu schreiben sage ich mal vorsichtig: Lass es. Es ist sehr Zeitintensiev und ist nicht von heute auf morgen realisiert. Dafür kannst locker mal dein ganzes Leben verplanen, wie man schön an Python und Ruby sehen kann )

Abschließend: Was hast du den Schönes vor?

EDIT: Arghhh!! Hätte mal den kompletten Thread lesen sollen Sehe jetzt erst dein letzten Post und das du dich bereits für PLY entscheiden hast.