Python Parsergeneratoren

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

[Granino]

@ Blackjack,
da hast Du wohl Recht.
Aber das betrifft meines Wissens nur 'formale Sprachen', nicht aber die üblichen Programmiersprachen.
Beispiel: Parameterlisten oder Statementfolgen werden in BNF rekursiv definiert. Programmiert (beim rekursiven Abstieg) werden sie aber iterativ z.B. in einer While-Schleife.

Da aber Leonidas sich gerade für PLY entschieden hat, scheint mir das Thema rekursiver Abstieg damit erledigt. Es ist auch ein wenig off topic.

Gruß Bernd

[BlackJack]

Ich weiss jetzt nicht was Du mit "formale Sprachen" gegenüber Programmiersprachen meinst, aber wenn man das übliche Beispiel mit den Grundrechenoperationen nimmt und da in der Grammatik auch die Operatorvorrangregeln und die Assoziativität steckt, dann hat man schon eine Linksrekursion, die beseitigt werden will. Und die Grundrechenarten sind in den meisten Programmiersprachen vorhanden. Und nicht alles machen es sich so einfach wie Lisp/Scheme.

[Leonidas]

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.

Ja, PLY hat etwas BNF-ähnliches. Das ist mehr oder minder auch der Grund, warum ich nun PLY genommen habe - so kann ich die Vorgegebene Grammatik mehr oder weniger übernehmen, statt pyparsing damit zu füttern. Wird zumindest für den Anfang einfacher sein, eine zweite Version zu machen oder den Parser selbst schreiben ginge natürlich auch, aber erstmal Schritt für Schritt.

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

Da am Schluss geplant ist, einen Compiler zu machen ist die Zeit zum Parsen nicht so besonders wichtig. Auch sonst ist sie nicht wesentlich, denn die Programmiersprache die am Schluss geparst werden soll ist so beschränkt, dass man damit sowieso keine langen Programme schrieben wird.

Den Parser später mit C neu zu schrieben wäre natürlich auch eine Möglichkeit, mit all' den Möglichkeiten die du aufgezeigt hast. Da ist es praktisch, dass ich PLY nutze, welches den Umfang von ``lex`` und ``yacc`` hat - somit wäre eine C-Version durchaus ohne besonders große Verrenkungen auch möglich. Es ist gut, sich eine Tür offen zu halten.

Jedoch muss der erste Ansatz auf jeden Fall in Python sein - ich will zeigen, dass man damit genauso gut wie mit Java einen Compiler hinbekommt.

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

Es ist mehr oder minder schon eine "neue" Sprache und zwar MiniJava. Im Moment bin ich aber dabei meine Tools zu erforschen, daher habe ich im Moment nur einen Straightline-Lexer und einen Straightline-Interpreter (der einen gegebenen AST abarbeitet).

[Granino]

@ Blackjack,

ja da fiel mir die Bezeichnung nicht ein. Ich meine die kleinen oft exotischen Beispielgrammatiken, die in der Literatur für alles mögliche herangezogen werden.

Zu den logischen und arithmetischen Ausdrücken: Da die Semantik, insbesondere die Vorrangregeln bekannt sind, kann man alles in eine einzige Prozedur oder Funktion werfen. Man hat dann eine Folge von Operanden, die durch die einzelnen Operatoren getrennt sind. Drumherum hat man wieder eine While-Schleife.

So hatten wir es jedenfalls vor Jahren implementiert. Als Vorarbeit wandelten wir die Originalsyntax um und entfernten dabei alle unnötigen Rekursionen - Unnötige Rekursionen sind beispielsweise die Statementfolgen; die Rekursion ist ja nur durch die BNF bedingt.

Wir erweiterten die Metasyntax der EBNF um ein weiteres Element: die 'Trennerfolge'. Trennerfolgen sind wie zuvor oben erwähnt Parameterlisten (Trenner ist das Komma), Statementfolgen (Trenner sind in Algol/Pascal das Semikolon; in Python der Zeilenwechsel) und als Sonderform der allgemeine Expression (Trenner sind die diversen Operatoren).

Gruß Granino

Edit (Leonidas): Restliche Diskussion in den Thread Compilerbau in Python abgetrennt.