Python Parsergeneratoren

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