Resources for lexing, tokenising and parsing in py

问题:

Can people point me to resources on lexing, parsing and tokenising with Python?

I'm doing a little hacking on an open source project (hotwire) and wanted to do a few changes to the code that lexes, parses and tokenises the commands entered into it. As it is real working code it is fairly complex and a bit hard to work out.

I haven't worked on code to lex/parse/tokenise before, so I was thinking one approach would be to work through a tutorial or two on this aspect. I would hope to learn enough to navigate around the code I actually want to alter. Is there anything suitable out there? (Ideally it could be done in an afternoon without having to buy and read the dragon book first ...)

Edit: (7 Oct 2008) None of the below answers quite give what I want. With them I could generate parsers from scratch, but I want to learn how to write my own basic parser from scratch, not using lex and yacc or similar tools. Having done that I can then understand the existing code better.

So could someone point me to a tutorial where I can build a basic parser from scratch, using just python?

回答1:

I'm a happy user of PLY. It is a pure-Python implementation of Lex & Yacc, with lots of small niceties that make it quite Pythonic and easy to use. Since Lex & Yacc are the most popular lexing & parsing tools and are used for the most projects, PLY has the advantage of standing on giants' shoulders. A lot of knowledge exists online on Lex & Yacc, and you can freely apply it to PLY.

PLY also has a good documentation page with some simple examples to get you started.

For a listing of lots of Python parsing tools, see this.

回答2:

This question is pretty old, but maybe my answer would help someone who wants to learn the basics. I find this resource to be very good. It is a simple interpreter written in python without the use of any external libraries. So this will help anyone who would like to understand the internal working of parsing, lexing, and tokenising:

"A Simple Intepreter from Scratch in Python:" Part 1, Part 2, Part 3, and Part 4.

回答3:

For medium-complex grammars, PyParsing is brilliant. You can define grammars directly within Python code, no need for code generation:

>>> 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', '!']

(Example taken from the PyParsing home page).

With parse actions (functions that are invoked when a certain grammar rule is triggered), you can convert parses directly into abstract syntax trees, or any other representation.

There are many helper functions that encapsulate recurring patterns, like operator hierarchies, quoted strings, nesting or C-style comments.

回答4:

Have a look at the standard module shlex and modify one copy of it to match the syntax you use for your shell, it is a good starting point

If you want all the power of a complete solution for lexing/parsing, ANTLR can generate python too.

回答5:

pygments is a source code syntax highlighter written in python. It has lexers and formatters, and may be interesting to peek at the source.

回答6:

Here's a few things to get you started (roughly from simplest-to-most-complex, least-to-most-powerful):

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

When I learned this stuff, it was in a semester-long 400-level university course. We did a number of assignments where we did parsing by hand; if you want to really understand what's going on under the hood, I'd recommend the same approach.

This isn't the book I used, but it's pretty good: Principles of Compiler Design.

Hopefully that's enough to get you started :)

回答7:

I suggest http://www.canonware.com/Parsing/, since it is pure python and you don't need to learn a grammar, but it isn't widely used, and has comparatively little documentation. The heavyweight is ANTLR and PyParsing. ANTLR can generate java and C++ parsers too, and AST walkers but you will have to learn what amounts to a new language.

回答8:

Frederico Tomassetti had a good (but short) concise write-up to all things related from BNF to binary deciphering on:

• lexical,
• parser,
• abstract-syntax tree (AST), and
• Construct/code-generator.

He even mentioned the new Parsing Expression Grammar (PEG).

https://tomassetti.me/parsing-in-python/