2 ms·
This article does not cite any references (and is from 2010) so I can't tell if the author was aware that packrat parsing can support left recursion (PDF, 2008)
by InAnEmergency 10y ago
This article does not cite any references (and is from 2010) so I can't tell if the author was aware that packrat parsing can support left recursion (PDF, 2008): http://web.cs.ucla.edu/~todd/research/pepm08.pdf http://web.cs.ucla.edu/~todd/research/pepm08.pdf
- wtetzner 10y agoThe algorithm in that paper produces incorrect parses for some PEGs: http://tratt.net/laurie/research/publications/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf http://tratt.net/laurie/research/publications/papers/tratt__...
- stormbrew 10y agoAlso worth noting from this paper is this, which is an underappreciated facet of packrat parsing: > It should be noted that while Packrat parsing obviously adds an extra layer of complexity over ‘pure’ PEGs, contrary to expectations it often slows parsing down when used blindly for every rule. Especially these days, and really definitely in a lot of dynamic languages (cfe Ruby), the kind of allocation rate that packrat parsing produces has a significantly negative effect on performance. Applied blindly you're just trading n^2 performance for n^2 memory use, and that may not work out the way you think it should.
- jules 10y agoActually performance is exponential without memoization, so usually some amount of memoization is essential, but memoizing more rules usually does not help.
- hardmath123 10y agoAlso worth noting that Earley parsers also support left-recursion without any fancy additions. http://reports-archive.adm.cs.cmu.edu/anon/anon/usr/ftp/scan/CMU-CS-68-earley.pdf http://reports-archive.adm.cs.cmu.edu/anon/anon/usr/ftp/scan...