[HN Gopher] TatSu takes grammars in variation of EBNF, outputs m...
___________________________________________________________________
TatSu takes grammars in variation of EBNF, outputs memoizing Python
PEG parsers
Author : bryanrasmussen
Score : 48 points
Date : 2022-05-07 11:32 UTC (11 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| pizza wrote:
| 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..
| btown wrote:
| 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
| erezsh wrote:
| > 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 wrote:
| 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
| erezsh wrote:
| I couldn't find in the link any mention of heap or stack-
| based storage. Where can I find more info about it?
| chubot wrote:
| Eh python's stack variables are on the C heap, so I don't
| think that interpretation makes any sense.
| ashish01 wrote:
| 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.
| linkdd wrote:
| 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/
| zasdffaa wrote:
| 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.
| camgunz wrote:
| 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!).
| erezsh wrote:
| > a generated standalone parser behaves differently
|
| Please submit an issue demonstrating it if you can! I'll do
| my best to fix it.
| camgunz wrote:
| I will! I've just been busy and what-not :) Got some free
| time coming up
| flakiness wrote:
| 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)?
| frou_dh wrote:
| 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.
| UncleEntity wrote:
| 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.
| mingodad wrote:
| 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.
| eesmith wrote:
| The Earley parser was written by John Aycock.
|
| The flex/bison clone you're perhaps thinking of is PLY from
| David Beazley.
| mingodad wrote:
| 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 .
| carapace wrote:
| 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)
| jdowner wrote:
| Parsimonious is quite nice.
| egberts1 wrote:
| 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?
| UncleEntity wrote:
| 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.
___________________________________________________________________
(page generated 2022-05-07 23:02 UTC)