4 ms·
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 Prat
by 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 agoAnd 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 agoAh, 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 agoThere 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.