4 ms·
I had to do some digging for myself to verify that, yes, PEGs are a recent concept distinct from the kind of grammars I'm already familiar with. See Bryan Ford'
by scott_s 17y ago
I had to do some digging for myself to verify that, yes, PEGs are a recent concept distinct from the kind of grammars I'm already familiar with. See Bryan Ford's paper, Parsing Expression Grammars: A Recognition-Based Syntactic Foundation from PoPL 2004: http://portal.acm.org/citation.cfm?id=964001.964011 http://portal.acm.org/citation.cfm?id=964001.964011
- barrkel 17y agoMemoization to get linear performance out of backtracking, which is exponential without it, is certainly a nice sleight of hand, but I wouldn't be under any illusions that the constant factor is competitive with say an LALR recognizer. Also, with a scheme that maps so closely to recursive descent, it's easy to miss what amount to grammar ambiguities, where nested productions preferentially eat tokens that may be in the follow set (i.e. the if/else problem).
- cynicalkane 17y agoPEGs don't have grammar ambiguities. Every PEG is deterministic. Grammar ambiguities are resolved by ordered choice. If there are two ways to parse something, the first way will be tried first. If it succeeds, the ordered choice short-circuits and the second way is ignored. So you can resolve, say, the classic dangling else problem by ordering your choices correctly.
- silentbicycle 17y agoRight, and PEGs only have one level of backtracking, so you don't have potentially massive slowdown due to backtracking several levels and re-trying everything along the way. While the backtracking behavior is different, choice order affects PEG rules similarly to Prolog.
- barrkel 17y agoI know all of that. My point is that the if/else problem really is an ambiguity (i.e. it is a language bug, not just a problem you have to get around in parsing), and problems similar to it crop up when your tool doesn't alert you to first/follow conflicts, in LL(1) parlance. That PEGs encode the implementation strategy inside the declarative grammar is a flaw, in my opinion, not a benefit.
- cynicalkane 17y agoIn programming, ambiguity is bad! Explicitly encoding disambiguation rules in the grammar is a good thing, just like it's a good thing in functional pattern matching, in Prolog... I'd be interested to hear any reason why you would want to not disambiguate a grammar in any language designed to be computer-recognizable.
- barrkel 17y agoHere, read this: http://compilers.iecc.com/comparch/article/05-09-114 http://compilers.iecc.com/comparch/article/05-09-114 In particular: "Yes, this is "the" problem with PEG's. / implies ordering of the search (parsing) space. You need to order your / operators so that special cases (e.g. longer matches), so that they appear first. Unfortunately, if you don't do this, nothing will tell you you have a problem with your grammar, it will simply not parse some inputs. To me this implies that if one wants to use a PEG to parse some input, then one must exhaustively test the parser." Hopefully the thread therein will describe my issue better than I have thus far.
- scott_s 17y agoIndeed it does, and Chris Clark very nicely summarizes the advantages and disadvantages of PEG vs other parsers. Nice find.
- silentbicycle 17y agoThere's a really good VM-based PEG parsing system called LPEG (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html). Paper: http://www.inf.puc-rio.br/~roberto/docs/peg.pdf http://www.inf.puc-rio.br/~roberto/docs/peg.pdf It's for Lua, but there isn't anything in the VM design that requires Lua per se - porting it to another language's C API wouldn't be difficult. In my experience, LPEG has been quite easy to use for the sort of tasks one would normally apply regular expressions to (and then some, as it handles recursive structures far better), it's quite fast, and it's easy to tune incrementally. In my (not yet ready for release) Lua/LPEG webserver, I'm handling 1000+ requests per second in about 2MB ram total* , so LPEG's design has tamed the usual space issues caused by PEG memoization. * Only a tiny amount of that time is due to request parsing, it's mostly because I'm still working the kinks out of the event loop. One strike against it is that there isn't a whole lot of casual documentation, though the documentation that does exist (the research paper and a library reference) is quite thorough. Also, it takes advantage of Lua's operator overloading to make the grammars concise, which takes getting used to. Still, having it so thoroughly integrated into the language is extremely convenient, and it's quite a bit more expressive than regular expressions. Also, here's a link to the PEG paper on the author's site, rather than behind the ACM's paywall: http://www.bford.info/pub/lang/peg.pdf http://www.bford.info/pub/lang/peg.pdf . Gotta love the ACM.