3 ms·
For a counterpoint: * you can get "EBNF"-style operators using traditional LL parsers like ANTLR. * Likewise, top-down parsers can have integrated lexing also
by haberman 15y ago
For a counterpoint:
* you can get "EBNF"-style operators using traditional LL parsers like ANTLR.
* Likewise, top-down parsers can have integrated lexing also.
* The downside of prioritized choice is that you don't get any insight into what inherent ambiguities your grammar has. The dangling-else ambiguity in C (for example) is a real ambiguity that you have to tell your users about. Prioritized choice hides ambiguities and gives you no hint when you develop your grammars where the ambiguities are.
* PEG-based parsers are less efficient than LL parsers. LL parsers are O(n) in time and O(d) in space (where n is the length of the input and d is the depth of the nesting). To parse a PEG in O(n) time the space complexity becomes O(n) (this is a packrat parser). To parse with O(d) space, time complexity becomes O(n^d) (as with lpeg). And the constant factor for LL parsing is much lower than with packrat parsing.
I think the future is LL. When the tooling gets good enough with LL, I think that the primary motivation for PEGs (that they are easy to use) will evaporate.
- tptacek 15y agoI knew someone would call me on this and chose my words carefully --- "LALR parsers modeled on Yacc" --- but am glad for the response. ANTLR is a pain in the ass to integrate; you can get a totally respectable PEG parser in 2k lines of C. What would you use for LL parsing?
- haberman 15y agoI'm working on making my ideal tool: http://www.reverberate.org/gazelle/ http://www.reverberate.org/gazelle/ It's been a long time coming, but I believe very strongly in it. "pain in the ass to integrate" -- I can sympathize. I'm working tirelessly to make this as easy to integrate as regexes are in Perl, Python, Ruby, etc.
- vorg 15y agoThe name of the pdf linked to on the language.js page is "Packrat Parsers Can Handle Practical Grammars in Mostly Constant Space" (www.ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste513-mizushima.pdf). They achieve this by adding a Prolog-style Cut operator to the PEG language.