4 ms·

PEG (Packrat) is hot now.

• nly 11y ago
  Interesting paper on left-recursion in recursive descent parsers like PEGs and Packrats http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08 http://web.cs.ucla.edu/~todd/research/pub.php?id=pepm08
  • sklogic 11y ago
    Yes, I implemented exactly this approach. But for the binary expressions I am using Pratt, it is faster and easier to construct left-associative nodes.
  • ltratt 11y ago
    If you're interested in left-recursion in PEGS then, at the risk of gross immodesty, you may be interested in http://tratt.net/laurie/research/pubs/html/tratt__direct_left_recursive_parsing_expression_grammars/ http://tratt.net/laurie/research/pubs/html/tratt__direct_lef... With less risk of immodesty you may also find http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web http://arxiv.org/pdf/1207.0443.pdf?ref=driverlayer.com/web interesting. There's probably more recent work than these two papers, but I'm a little out of date when it comes to the PEG world.
    • nly 11y ago
      Thanks, looks like you've put a lot of work in to it and I'll enjoy reading it.
• fanf2 11y ago
  It is important to distinguish between PEG and packrat. PEG is a model for recognizers, distinct from traditional grammers whose theoretical model is usually based on generating strings rather than recognising them. (Yes this is a bit backwards.) The most distinctive feature of PEGs is the ordered choice operator - traditional context-free grammars and regexes use unordered choice, but ordered choice is a closer model of how recursive descent parsers work in practice. Ordered choice naturally leads to implementations that have less backtracking than common regex matchers, e.g. Lpeg. Packrat parsers are based on a clever non-backtracking PEG matching algorithm. They spend O(n) memory to get O(n) parsing time, so they are reliably fast but not good for long inputs. They are also effective in a pure, lazy setting like Haskell. Lpeg is a PEG parser but not a packrat parser.