TatSu takes grammars in variation of EBNF, outputs memoizing Python PEG parsers | Hacker News Reader

TatSu takes grammars in variation of EBNF, outputs memoizing Python PEG parsers

github.com

I used TatSu back when it was named Grako, I really loved it.

But now, I discovered LALRPOP[0] and Logos[1] in Rust which is just so much more powerful, I'm using PyO3 to bring it to Python because I find it easier to walk the AST and do code generation from here.

[0] - http://lalrpop.github.io/lalrpop/

[1] - https://docs.rs/logos/latest/logos/

What's the state of parser generators in Python today? This "TaSu" looks very powerful (not talking about the language class but about tooling and feature set). Is this getting enough traction to becoming a go-to option?

In Java (and maybe C++) ANTLR is a go-to option. Some languages have their own goto options, and others are lacking. When I did a quick research, Python seemed to be on the "lacking" side (multiple not-very-well-maintained-options but no clear winner). Is that changing (or was I missing something)?

When I surveyed what was out there last year I wrote down these 3 as the most interesting:

https://github.com/lark-parser/lark

https://github.com/neogeny/TatSu

https://github.com/dabeaz/sly

Lark seems to be the one with traction.

The 3.0 release of pyparsing includes some nice extensions over its older 2.x code base, including LR parsing support and railroad diagram generation. Also, PEP-8 API naming has been added (but with pre-PEP-8 synonyms defined for legacy compatibility). https://github.com/pyparsing/pyparsing (Disclosure: I am the author of pyparsing.)

I played around with the Earley parser that used to be used as part of the CPython build process (who’s name I can’t remember off the top of my head) a bunch and with a lot of hacking I got it into a pretty usable state. It isn’t really that easy to hack on because they do a lot of optimization which is probably one of the major reasons they kicked it out of the python repo.

ANTLR does have python as one of the output languages IIRC.

There’s also a flex/bison clone written in python whose name I also can’t remember.

My current favorite parser generator library, Coco/R, has a python 2 implementation which I’ll maybe get around to porting to py3k one of these days, who knows?

But to answer your question I don’t think there’s a go to library on the python side, I’ve played around with a bunch of them and usually just go for re2c/lemon or Coco/R from C(++) since I mainly just poke at these things probably more than I should.

The next time I get a few days with nothing to do I plan to see if I can’t whip up a working lpeg (lua’s peg parser VM library thing) in python. Someone did a port a while ago but it is abandoned and, honestly, not all that good. No offense to the person who did it but you can do some pretty nifty things with the python C-api with some practice.

To add to your list I just found this project https://github.com/ChrisHixon/chpeg it has good performance and it's relatively simple compared to others.

The Earley parser was written by John Aycock.

The flex/bison clone you're perhaps thinking of is PLY from David Beazley.

Also to add to your list is https://github.com/KuramitsuLab/pegpy it's an intriguing peg parser with origin from a Japanese group https://github.com/nez-peg/nez .

Parsimonious is quite nice.

I use SPARK (Scanning, Parsing, and Rewriting Kit) it makes Earley parsers.

> The original version of this was written by John Aycock for his Ph.d thesis and was described in his 1998 paper: “Compiling Little Languages in Python” at the 7th International Python

http://pages.cpsc.ucalgary.ca/~aycock/spark/ (Older)

https://pypi.org/project/spark-parser/ (More recent)

My biggest beef is the lack of AST output generator after defining the TOKEN input parser for a lot of Open Source parsers.

It pertains to counting duplicate nested blocks as well as enforcing 1+, 1:M and N:M combinatorial of syntax block.

I once did the entire ISC Bind9 named.conf parser into PyParsing (named is a handrolled parser, not a Bison/Flex).

But it cannot do N:M nor enforcing 1:M.

So, can TatSu help with that AST-output part?

You want the parser generator library to automagically produce an AST and fill it in from the grammar description?

Tree Sitter (I think) does that but (I believe) its output is a parse tree.

For the N:M stuff, if I understand you correctly, sounds like global value numbering could do that as, if I understand it correctly, it gives you subexpression deduplication for free. I think this is a tree transformation step though — haven’t really thought about it before but it could probably be implemented as the parser output but would be destructive as you’d lose line number information and whatnot.

Personally, for my playing around, I use asdl to generate the AST nodes because its a super-simple ‘language’ so I can easily test out new things. I’ve reimplemented it probably five or six times now but that definitely qualifies as yak shaving.

Precisely on all counts that you’ve said.

Yak shaving. Sigh. It is still a thing at the frontier of leading-edge technology.

Will look at TreeSitter (again) and adsl.

That reminds me, I’ve been relooking at things from time to time and need to do a summary recap on paper. Blog it, perhaps.

> The use of Python’s context managers considerably reduces the size of the generated parsers for code clarity, and enhanced CPU-cache hits.

I would love to hear more about how it affects cache hits.

It's just stack based memory that automatically cleans up. Given their storage on the stack (rather than heap), they have better cache properties.

https://docs.python.org/3/library/contextlib.html

I couldn't find in the link any mention of heap or stack-based storage. Where can I find more info about it?

Eh python’s stack variables are on the C heap, so I don't think that interpretation makes any sense.

If you are trying out parsing in python, I would recommend giving [Lark](https://github.com/lark-parser/lark) a try. I have used it for smallish projects are its really easy to use especially with the Earley parser.

There's mention here of the Python output option in ANTLR. It has serious performance problems (which the other output languages don't have). Please be aware of this, and test to see it's fast enough before committing to it. As said, other languages don't suffer this problem and ANTLR is a very good option with them.

Yeah can confirm. I switched to Lark and am a lot happier. But a caveat w/ Lark is that a generated standalone parser behaves differently--I gave up doing this and just read the grammar on the fly now (sorry erezsh!).

> a generated standalone parser behaves differently

Please submit an issue demonstrating it if you can! I'll do my best to fix it.

I will! I've just been busy and what-not :) Got some free time coming up

Huh, it would be really cool if you could simply add type hint annotations to the Python code, and then use mypyc to compile the Python down to C..

Numba does much of what you’re looking for, albeit with its own type hint system.

https://numba.pydata.org/

http://numba.pydata.org/numba-doc/0.17.0/user/jit.html

Reply on news.ycombinator.com