Pyrr.ltk und ptk - Lexer/Parser Toolkit für Python

[modelnine]

Mich hats schon seit einiger Zeit genervt dass Python nativ (oder auch in einem vernünftigen Erweiterungsmodul) keine Unterstützung und Implementierung für Lexer- oder Parser-Generatoren mitbringt. Alle Projekte die es im Netz zu finden gibt sind entweder uralt, schlecht dokumentiert, buggy, haben ein bescheidenes Interface, oder sind einfach nie fertig gestellt worden. Dazu dass sich diese Situation verbessert hat auch nicht wirklich beigetragen dass die Python-SIG zu Parsern schon vor einigen Jahren erfolglos eingestellt wurde.

Auf jeden Fall: Pyrr.ltk (lexer toolkit) und ptk (parser toolkit) probieren diese Lücke im Python-Textverarbeitungsbereich ein bißchen zu füllen, indem sie eine Art flex (ltk) und bison (ptk) zur Verfügung stellen.

ltk ist mittlerweilen schon ziemlich fertig und vom Funktionsumfang mächtiger als flex, da der Lexer zustandsbehaftet ist (bis auf die Tatsache dass es aufgrund der Beschränkung der Python-eigenen re-Bibliothek kein Feed-Lexer sein kann, und auch sonst davon profitieren würde wenn hier ein bisschen C-Code davorgeschaltet wird um einen eigenen DEA-Simulator zu implementieren, da im Normalfall bei einem Lexer der Code nur sehr selten kompiliert wird (wenn sich der Lexer nämlich ändert), und es sich hier massiv lohnt einen DEA aus dem NEA der regulären Ausdrücke zu machen, was sre nicht macht aufgrund von Geschwindigkeitsfragen beim kompilieren). Wer wegen dem Zustandsbehafteten vermutet dass der Lexer dadurch nicht mehr ein reiner Lexer ist: weit gefehlt. Ein "zustandsbehafteter" Lexer ist immer noch ein EA, da die Zahl der Zustände (nach denen die Regeln ausgesucht werden) logischerweise auch endlich ist.

ptk ist bisher noch nicht so ganz fertig, aber ich bin kontinuierlich dabei (seit heute abend kann ptk aus einer LR(1)-Grammatik einen Parser erzeugen, löst aber bisher SHIFT/REDUCE-Konflikte noch nicht sinnvoll auf, und auch der Parser-Algorithmus selbst hat noch kein vernünftiges Interface zum Lexer, das ist aber trivial zu implementieren).

Wer sich mal angucken will wie Lexer und Parser in ptk/ltk in Python geschrieben werden können (mit zwei Beispiellexern und der typischen Beispielgrammatik für numerische Berechnungen), der kann auf:

http://svn.modelnine.org/svn/Pyrr/trunk

die Dateien auschecken. Die Lexer sind alle voll funktionsfähig (lesen also einen Eingabestrom aus Dateien), der Parser erwartet eine Eingabe per Tastatur (und zwar die Terminal-Namen!).

Viel Spaß damit!

[modelnine]

So. Pyrr nähert sich endlich einer stabilen Distribution, und kann Operator/Regel-Präzedenz, und mittlerweilen auch für Grammatiken eine erweiterte BNF-Syntax (ala re-Ausdrücke). Über's Wochenende werd ich die Dokumentation fertig machen, und wer Interesse an dem Projekt hat, sollte spätestens am Sonntag nachmittag noch mal gucken, und mir dann auch gerne weitere Anregungen zumailen.