4 ms·
TatSu takes grammars in variation of EBNF, outputs memoizing Python PEG parsers
- flakiness 5y agoWhat'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)?
- frou_dh 5y agoWhen 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/lark-parser/lark https://github.com/neogeny/TatSu https://github.com/neogeny/TatSu https://github.com/dabeaz/sly https://github.com/dabeaz/sly Lark seems to be the one with traction.
- ptmcg 5y agoThe 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 https://github.com/pyparsing/pyparsing (Disclosure: I am the author of pyparsing.)
- UncleEntity 5y agoI 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.
- mingodad 5y agoTo add to your list I just found this project https://github.com/ChrisHixon/chpeg https://github.com/ChrisHixon/chpeg it has good performance and it's relatively simple compared to others.
- eesmith 5y agoThe Earley parser was written by John Aycock. The flex/bison clone you're perhaps thinking of is PLY from David Beazley.
- mingodad 5y agoAlso to add to your list is https://github.com/KuramitsuLab/pegpy https://github.com/KuramitsuLab/pegpy it's an intriguing peg parser with origin from a Japanese group https://github.com/nez-peg/nez https://github.com/nez-peg/nez .
- jdowner 5y agoParsimonious is quite nice.
- carapace 5y agoI 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/ http://pages.cpsc.ucalgary.ca/~aycock/spark/ (Older) https://pypi.org/project/spark-parser/ https://pypi.org/project/spark-parser/ (More recent)
- egberts1 5y agoMy 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?
- UncleEntity 5y agoYou 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.
- egberts1 5y agoPrecisely 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.
- erezsh 5y ago> 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.
- goldenkey 5y agoIt'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 https://docs.python.org/3/library/contextlib.html
- linkdd 5y agoI 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/ http://lalrpop.github.io/lalrpop/ [1] - https://docs.rs/logos/latest/logos/ https://docs.rs/logos/latest/logos/
- zasdffaa 5y agoThere'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.
- camgunz 5y agoYeah 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!).
- ashish01 5y agoIf you are trying out parsing in python, I would recommend giving [Lark](https://github.com/lark-parser/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.
- pizza 5y agoHuh, 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..
- btown 5y agoNumba does much of what you’re looking for, albeit with its own type hint system. https://numba.pydata.org/ https://numba.pydata.org/ http://numba.pydata.org/numba-doc/0.17.0/user/jit.html http://numba.pydata.org/numba-doc/0.17.0/user/jit.html