https://pantsbuild.org/ logo
Join Slack
Powered by
<https://www.python.org/dev/peps/pep-0617/>
# random
h
@aloof-angle-91616 @hundreds-breakfast-49010 I think you both might find this particularly interesting
👍 1
h
I thought guido van rossum retired
h
He did, so that he can spend time on things like this 🙂
h
I spent a bunch of time last night reading guido's blog posts about PEGs 🙂
🐍 1
💯 1
a
PEGs are super cool and exactly the kind of thing parsers should be moving to instead of strict adherence to the chomsky hierarchy imho
i have a massive chip on my shoulder about it because the dude's phd thesis at MIT was PEG parsing (ok) but the thesis was so chock-full of the phrase "this doesn't occur often in practice" without any footnotes that i found it extremely difficult to read and was extremely frustrated because i think people deserve higher quality research
i plan to prove this by showing that it's possible to make a parser that's fast all the time and also is more fun and reliable and requires less boilerplate to use than any other method
(also, btw, for things like parsers that don't have almost any new theory behind them for the last 50 years, knowing "research" is much less important than seeing how people use parsers in the wild, imho)
this issue always breaks my heart to read: https://github.com/rust-lang/rfcs/pull/2544 because if it was easier to implement parsers rust wouldn't have the turbofish syntax at all, but the complexity of implementing the parser alone is making it impossible for rust to make this syntax decision, which i always thought was extremely interesting
hm, didn't read through the whole thread. it seems that parsing implementation is a relevant but secondary concern to the politics:
Some portion of the concerns had to do with the practical impact of making this change: i.e., making it harder for editors and other sorts of tooling to parse Rust. This at least can be evaluated by landing the change on nightly and actively updating the various bits of tooling we have, as well as allowing the change to "sit" for some time in an unstable state so that we accumulate experience.
i also think that ast iteration is almost as interesting as parsing. i love love instagram's libcst in every way -- it allows transforming python code too: https://libcst.readthedocs.io/en/latest/tutorial.html
this is a super super cool PEP!!
❤️ 1
omg this "rejected alternatives" sections is giving me LIFE: https://www.python.org/dev/peps/pep-0617/#rejected-alternatives
Other variants of LR were not considered, nor was LL (e.g. ANTLR). PEG was selected because it was easy to understand given a basic understanding of recursive-descent parsing.
LALR, LL, LR are all cargo-culted because everyone is scared of compilers
and because compiler profs say "parsing is a solved problem"
so i love that this justification is something others will read and maybe consider too
h
I don't really remember what all of LALR, LL, LR, etc. actually mean
a
they are a very very small family of parsers that can be generated, with a constant amount of space for lookahead and extremely limited production rules
h
the practical parsers that I've worked with were either hand-written recursive descent parsers or parsec-style parser combinators, which I think are PEGs
a
they're mainly known for producing shift-reduce conflicts that ruin lives
the current emacs maintainer wrote parsec =]
h
I remember shift-reduce conflicts from my college compilers class, but haven't used any of those types of parsers in practice
but yeah parser combinators strike me as a pretty elegant idea
a
i've used them to understand code written with bison or jison
yes the parser i'm working on is a combinator but also is linear i believe
people have negative ideas about combinators that i believe are mostly wrong since combinators are such a general idea
h
I thought parser combinators were O(n^3) in deliberately-crafted worse cases but were basically linear in practice
a
i don't know that i could tell you a single piece of software i know off the top of my head running a generated parser
that's my annoyance with the PEG paper, lol. it shies away from complexity since complexity i think is part of why people use LL/LR/LALR/whatever but there are still useful investigations to be made there i think
h
I don't think PEGs are complicated
a
i mean asymptotic complexity, i definitely agree
h
they strike me as simple, to be honest, at least if you're used to working with first-class functions
a
yes
h
yeah worst-case asymptotic complexity matters, if someone can craft a O(n^3) worst-case input then you have to worry about that if you expose your parser to the public
I don't understand parser theory well enough to know if there's anything like a PEG but without the degenerate complexity problem
a
i don't know any parser theory but what i've made up and i think i have one but that's the problem with making things up
i would love to share it but i am going to publish first
h
solid, let me know when you have a publishable paper ready, I'd like to read it
a
basically like parsers having exactly one state at a time and then falling back to backtracking as with PEG is i think a ridiculous antipattern
i have very readable rust code too :)
i'm trying to patent it is why i'm being secretive. which i guess is a tacit agreement that i also do not know of an alternative that has the qualities you identified (and i still might be wrong)
3 Views
Open in Slack
PreviousNext
Powered by