Ressourcen zum Lexing, Tokening und Parsing in Python

Question

Können mich Leute auf Ressourcen zum Lexing, Parsing und Tokening mit Python verweisen?

Ich mache ein wenig Hacking auf einem Open-Source-Projekt (hotwire) und wollte ein paar Änderungen an dem Code zu tun, dass lexes, parses and tokenises die Befehle in sie eingetragen. Da es wirklich funktionierender Code ist, ist es ziemlich komplex und ein bisschen schwierig zu trainieren.

Ich habe noch nicht an Code zu lex/parse/tokenise gearbeitet, also dachte ich, ein Ansatz wäre, ein oder zwei Tutorials zu diesem Aspekt durchzuarbeiten. Ich würde hoffentlich genug lernen, um den Code zu navigieren, den ich eigentlich ändern möchte. Gibt es da draußen etwas Passendes? (Im Idealfall könnte es an einem Nachmittag durchgeführt werden, ohne den Drachen Buch zuerst zu kaufen und lesen ...)

Edit: (7. Oktober 2008) Keiner der folgenden Antworten recht geben, was ich will. Mit ihnen konnte ich Parser von Grund auf neu erstellen, aber ich möchte lernen, wie ich meinen eigenen Parser von Grund auf neu schreiben kann, ohne lex und yacc oder ähnliche Tools zu verwenden. Danach kann ich den vorhandenen Code besser verstehen.

Also könnte mich jemand auf ein Tutorial verweisen, wo ich einen grundlegenden Parser von Grund auf neu erstellen kann, nur mit Python?

Answer 1

einen Blick auf das Standard-Modul haben shlex und eine Kopie davon ändern Sie die Syntax, die Sie für Ihre Shell verwenden, um übereinstimmen, ist es ein guter Ausgangspunkt

Wenn Sie die ganze Kraft einer Komplettlösung für lexing wollen/parsing, ANTLR kann auch Python generieren.

Answer 2

Ich schlage vor http://www.canonware.com/Parsing/, da es reine Python ist und Sie keine Grammatik lernen müssen, aber es ist nicht weit verbreitet und hat vergleichsweise wenig Dokumentation. Das Schwergewicht ist ANTLR und PyParsing. ANTLR kann auch Java- und C++ - Parser und AST-Walker generieren, aber Sie müssen lernen, was einer neuen Sprache entspricht.

Answer 3

Ich bin ein glücklicher Benutzer von PLY. Es ist eine reine Python-Implementierung von Lex & Yacc, mit vielen kleinen Feinheiten, die es ziemlich Pythonic und einfach zu bedienen machen. Da Lex & Yacc die beliebtesten lexing & Parsing-Tools sind und für die meisten Projekte verwendet werden, hat PLY den Vorteil, auf den Schultern von Riesen zu stehen. Eine Menge Wissen existiert online auf Lex & Yacc, und Sie können es frei auf PLY anwenden.

PLY hat auch eine gute documentation page mit ein paar einfachen Beispielen, um loszulegen.

Eine Liste vieler Python-Parsingtools finden Sie unter this.

Answer 4

pygments ist ein Quellcode-Syntax Highlighter in Python geschrieben. Es hat Lexer und Formatierer und kann interessant sein, um die Quelle zu sehen.

Answer 5

Für mittelkomplexe Grammatiken ist PyParsing brillant. Sie können Grammatiken direkt in Python-Code, keine Notwendigkeit für die Codegenerierung definieren:

>>> from pyparsing import Word, alphas 
>>> greet = Word(alphas) + "," + Word(alphas) + "!" # <-- grammar defined here 
>>> hello = "Hello, World!" 
>>>> print hello, "->", greet.parseString(hello) 
Hello, World! -> ['Hello', ',', 'World', '!'] 

(Beispiel aus der PyParsing Homepage genommen).

Mit Parse-Aktionen (Funktionen, die aufgerufen werden, wenn eine bestimmte Grammatikregel ausgelöst wird) können Sie Parses direkt in abstrakte Syntaxbäume oder eine andere Darstellung konvertieren.

Es gibt viele Hilfsfunktionen, die wiederkehrende Muster kapseln, wie Operatorhierarchien, Strings in Anführungszeichen, Verschachtelung oder Kommentare im C-Stil.

Answer 6

Hier ein paar Dinge zu Ihnen (etwa aus einfachsten zu den meisten Komplex, am wenigsten zu den meisten mächtigen) loszulegen:

http://en.wikipedia.org/wiki/Recursive_descent_parser

http://en.wikipedia.org/wiki/Top-down_parsing

http://en.wikipedia.org/wiki/LL_parser

http://effbot.org/zone/simple-top-down-parsing.htm

http://en.wikipedia.org/wiki/Bottom-up_parsing

http://en.wikipedia.org/wiki/LR_parser

http://en.wikipedia.org/wiki/GLR_parser

Als ich diese Sachen gelernt, war es in einem Semester lang 400-Level-Studium. Wir haben eine Reihe von Aufgaben erledigt, bei denen wir mit der Hand geparst haben; Wenn Sie wirklich verstehen wollen, was unter der Haube passiert, würde ich den gleichen Ansatz empfehlen.

Dies ist nicht das Buch, das ich verwendet habe, aber es ist ziemlich gut: Principles of Compiler Design.

Hoffentlich ist das genug, um Sie zu bekommen :) begann

Answer 7

Diese Frage ist ziemlich alt, aber vielleicht wäre meine Antwort jemandem helfen, die Grundlagen lernen will. Ich finde diese Ressource sehr gut. Es ist ein einfacher Interpreter, der in Python ohne die Verwendung von externen Bibliotheken geschrieben wurde. So wird dies jemand helfen, der die internen Arbeits von Parsing verstehen möchte, lexing und tokenising:

"A Simple Interpreter von Grund auf neu in Python:" Part 1, Part 2, Part 3 und Part 4.