4 ms·

Or even better, GLL. http://dotat.at/tmp/gll.pdf http://dotat.at/tmp/gll.pdf

• nickpsecurity 11y ago
  Best features of both types of parsers? Hell yeah! Never even heard of this one despite all the research updates I did a few years ago. Thanks for the link.
• sklogic 11y ago
  It's an interesting one, I'll add it to my collection. Although, to be fair, PEG (Packrat) do support left recursion [1], and it can also be combined with Pratt for the binary expressions very efficiently, at O(n). [1] http://www.vpri.org/pdf/tr2007002_packrat.pdf http://www.vpri.org/pdf/tr2007002_packrat.pdf
  • wtetzner 11y ago
    > Although, to be fair, PEG (Packrat) do support left recursion [1] Unfortunately it sometimes generates the wrong parse: http://tratt.net/laurie/research/pubs/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf http://tratt.net/laurie/research/pubs/papers/tratt__direct_l...
    • sklogic 11y ago
      And all the edge cases are related to the binary expressions - and you should be using Pratt for them instead. Left recursive PEG must be reserved for things like method, structure field and array access, which are ok with that algorithm.
      • wtetzner 11y ago
        Ah, gotcha. I struggled with PEG and left recursion for a while before finding GLL. Do you have any resources on how to combine PEG and Pratt?
        • sklogic 11y ago
          There must have been some papers on it, but I lost a track. Will try to dig out something. Meanwhile, you can take a look a my implementation of such a mix: https://github.com/combinatorylogic/mbase/tree/master/src/l/lib/parsing https://github.com/combinatorylogic/mbase/tree/master/src/l/... An example of a grammar built on top of it: https://github.com/combinatorylogic/clike/blob/master/clike/clike-parser.hl https://github.com/combinatorylogic/clike/blob/master/clike/... - see the `binary` nodes there, they're translated into Pratt while all the others are Packrat.