7 ms·
PEG Parsers
- chrisseaton 7y agoBryan Ford has the most comprehensive information about PEG and how they're parsed http://bford.info/packrat/ http://bford.info/packrat/. They've become somewhat unfashionable over the last decade - not really sure why.
- yellowapple 7y agoThey're one of Perl 6's killer features (much like how regexes were one of pre-6 Perl's killer features); first-class support for PEGs in the language itself is a godsend for parse-heavy tasks like deserialization and DSLs. If anything I feel like PEGs are getting more popular lately, likely because the memory usage is no longer terrible relative to the amount of memory even on "memory constrained" systems.
- minxomat 7y agoThey're alive and well in lots of DSLs implemented with LPeg. MoonScript (which I use almost daily) parses using LPeg and the general notation inspired some dynamic type validators (e.g. tableshape).
- skunkpocalypse 7y ago> They've become somewhat unfashionable over the last decade not really sure why. Much, much larger memory consumption than LR/LALR or even GLR. They're called packrat parsers for a reason. Although the time complexity is asymptotically the same, LR-family parsers have such a tiny memory footprint that they usually run entirely in cache. Packrat tables never fit for nontrivial grammars+inputs. In practice this makes a big difference in performance.
- jdoege 7y agoPackrat parsing is not an intrinsic aspect of PEG, nor does it increase memory usage. Further, the memory issue is more academic than real. If you are having memory issues, you will add intentional pruning to your parser to purge anything that comes before a point behind which you can not backtrack. Such points tend to exist in most computer languages. Yes, this is not a strict part of PEG but being academically pure when constructing a parser of any complexity leads to a short trip to madness. Perl 6's grammar construct is not pure to the PEG definition but it is a recursive descent grammar engine with all the bells and whistle you could want including functional components such as argument pattern matching which makes generic and reusable grammar expression a cinch. Also, PEG makes having a context sensitive lexer not simply trivial but no effort at all because lexing and parsing are all the same process. It you want to have two different token-types for an INT-looking-thing at two different places in your grammar for, "reasons", you are free to do so. Try that in a discrete lex/parse style grammar.
- rstuart4133 7y agoIt's very easy to write a PEG that will recognise the a target language, but it will probably recognise a few more as well. They are hard to reason about. LR and LL have the reverse problem. It's a challenge to get it to recognise a complex target language, but once you get the thing to work at all it's probably right. Also LL & LR are faster (very close to O(size of input)) and use less memory (almost none). PEG's have get their speed by remembering how they reduced what they've seen so far. There are lots of trade-offs in other words. PEGS win anywhere you would use once of the current crop of NFA based regular expressions recognisers (eg, PCRE), need something better.
- WillDaSilva 7y agoDidn't notice that Guido van Rossum was the author until I got to the end. As someone who has done work with the Python grammar, and watched it grow into the complex mess that the Python 3.8 grammar is, I'm glad to hear that Guido is exploring PEG parsers as an alternative to LL(1).
- thallavajhula 7y agoI'm surprised you missed the fact after reading this in the first paragraph - `...I now think it’s an interesting alternative to the home-grown parser generator that I developed 30 years ago when I started working on Python.`
- strictfp 7y agoI recently used the Rust "Pest" PEG parser, and it took an interesting approach to lookahead. It delegates the problem to the grammar writer. For instance, you are responsible for declaring any possible branches with choice operators. The approach becomes quite similar to manual lookahead in a recursive descent parser, but more declarative. I presume that this makes the runtime characteristics of the parsing a lot more predictable and bounded, and I'm surprised I hadn't thought about the solution before. Seems like a great idea, and worked well for my usecase. https://pest.rs/book/grammars/syntax.html https://pest.rs/book/grammars/syntax.html
- chrisseaton 7y agoThat's just a PEG isn't it - that's what this article is about. It's not a new idea in Pest.
- strictfp 7y agoMy understanding is Pest doesn't use packrat, and thus doesn't have the unbounded lookahead mentioned in the article. I figure that unbounded lookahead comes with a lot of downsides, and my opinion is that Pest solves lookahead in an interesting way. It felt relevant given the focus on lookahead in the article.
- chrisseaton 7y agoPackrat isn't really a parsing algorithm - the PEG is the parsing algorithm. Packrat is instead an optimisation that can be transparently applied to a PEG. It's a common cause of confusion. And to make it more complicated some PEGs aren't really tractable without Packrat, so then that's sort of not an optimisation any more.
- strictfp 7y agoOk, thank you for clarifying. If you don't mind me asking, is the manual approach to lookahead common to most PEG parsers? And if so, why would packrat be associated with infinite lookahead?
- igravious 7y agoIf anybody is thinking about writing a parser in Ruby I can recommend the Parslet (https://github.com/kschiess/parslet https://github.com/kschiess/parslet) PEG parser library. I used it to construct a parser for a Lisp-like grammar and I found it robust and easy to use. (You might not think you'd need a full blown parser library for something with a grammar as simple as Lisp but I found that there are enough grammar rules and the lookahead is deep enough that using a PEG parser was a win.)
- bwidlar 7y agoHow Janet's PEG module works https://bakpakin.com/writing/how-janets-peg-works.html https://bakpakin.com/writing/how-janets-peg-works.html
- vincent-toups 7y agoFor flexibility and ease of understanding, I still prefer nondeterministic monadic parser combinators. Not sure why, but its the only way I can write a decent parser. Too bad they are so slow.
- pacaro 7y agoOne thing that I like about PEG (among many) is that it's fairly easy to create useful error messages from them. My approach has been to introduce a type of cut operator, such that if you backtrack past a cut operator then it's information is stored, then if the parsee can't proceed it can examine the stored errors and produce hopefully sensible error messages. For example, if I have a simple rule for an expression exp = atom (op exp)* And I insert a cut between the op and the atom... exp = atom (op <cut> exp)* Then that cut (which can be appropriately annotated with human readable error information) will be returned if there is a binary exp with no rhs
- colanderman 7y agoI used this exact same technique for the most recent PEG-based parser I wrote too. Works really well, and integrates well with Prolog (which I was using).
- mamcx 7y agoWait... what is a "cut"? A minimal sample that show how it help with the error messages?
- drothlis 7y agoCut means "if you matched this far, don't consider other options even if the current option fails to parse". With this grammar: expr: expr '+' term | term And this input: 5 + It will first consider the first alternative (expr '+' term) but will fail to match that branch because it's missing the "term" after the "+". That's fine because there's another alternative to try (term). That alternative doesn't match either, and you'll get the error message from the last alternative that it tried (probably something like "unexpected +"). But with this grammar: expr: expr '+' <cut> term | term Then with the same input ("5 +") it will consider the first alternative, fail to match, and then fail immediately with the error message from that first alternative (something like "missing term after +").
- mamcx 7y agoyeah, I get the purposed point of a "cut" but how I put one? Exist a basic sample? (ie: Using a peg parser how define what is a "cut"???) expr: expr '+' API_call_here? term | term
- coleifer 7y agoI've made a few half-hearted attempts to use lpeg: http://www.inf.puc-rio.br/~roberto/lpeg/ http://www.inf.puc-rio.br/~roberto/lpeg/ The operator overloads are a lot to reckon with, beyond just the concepts, but it seems like there's something there worthwhile of study and learning. Hope to give it another try. Be interested in any introductory material, if anyone has some good links.
- blitmap 7y agoI keep feeling like I'm following in the steps of giants with lpeg. I loved my introduction to it when I was big on Lua. Some of those operators take functions with such strange signatures - until you try to do something clever later, and your realize you're being passed exactly the arguments you need to make it work.
- pull_my_finger 7y agoI got you covered fellow Lua user http://leafo.net/guides/parsing-expression-grammars.html http://leafo.net/guides/parsing-expression-grammars.html http://www.wra1th.plus.com/lua/lpeg.html http://www.wra1th.plus.com/lua/lpeg.html http://www.wra1th.plus.com/lua/peg/PEG.html http://www.wra1th.plus.com/lua/peg/PEG.html http://lua-users.org/wiki/LpegTutorial http://lua-users.org/wiki/LpegTutorial https://rawgit.com/dlaurie/lua-notes/master/lpeg-brief.html https://rawgit.com/dlaurie/lua-notes/master/lpeg-brief.html http://www.inf.puc-rio.br/~roberto/lpeg/ http://www.inf.puc-rio.br/~roberto/lpeg/ http://lua-users.org/wiki/LpegRecipes http://lua-users.org/wiki/LpegRecipes
- smitty1e 7y agoPEG It will come back to you.
- jchook 7y agoFrom Wikipedia... > Unlike CFGs, PEGs cannot be ambiguous; if a string parses, it has exactly one valid parse tree. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven. Does this mean that PEG grammars are a form of regular grammar?
- curryhoward 7y agoNo. One can come up with a PEG for a language consisting only of strings with balanced parentheses. That language cannot be described by a regular grammar.
- peterkelly 7y agoNon-paywalled version: http://archive.is/E5QtQ http://archive.is/E5QtQ
- trhway 7y agowith an infinite lookahead it seems that the main advantage of LL over LR is gone, and the one might as well go all in for the LR for its more expressive power.
- Zardoz84 7y agoA few years ago, I played with Pegged. Pegged is a PEG parser fro DLang. Beyond about why PEG is good/bad, Pegged shows how powerful is the metaprogramming of DLang. It simply generates the parser from the PEG grammar at compile time, and could execute and parse stuff at runtime and compile time ! https://tour.dlang.org/tour/en/dub/pegged https://tour.dlang.org/tour/en/dub/pegged
- ivoflipse 7y agoFor anyone interested in following this work, these Discourse threads are interesting: - https://discuss.python.org/t/preparing-for-new-python-parsing/1550 https://discuss.python.org/t/preparing-for-new-python-parsin... - https://discuss.python.org/t/switch-pythons-parsing-tech-to-something-more-powerful-than-ll-1/379 https://discuss.python.org/t/switch-pythons-parsing-tech-to-...
- kelven 7y agoSince i lost $1200 to fake hackers been searching for the right one till i met cybergods116@gmail.com. He's totally the word hack.Does from yahoo,Facebook,gmail,Hotmail,aol,twitter,Instagram,snapchat,bank jobs and credit card tops, Paypal acct,blank a.t.m cards,update school grades. I am not here to advertise but tell you my experience...He's kinda picky so make mention of the reference. Santos referred you. don't forget to thank me later
- quotemstr 7y agoI don't like PEGs: the choice operator makes it easy to accidentally create ambiguous grammars. The explicit conflict messages in conventional LR-ish parser generators tell you up front when your language is wonky.