Repository navigation
Solve left-recursion and improve error recovery using pika parsing #460
Description
This recent paper (https://arxiv.org/abs/2005.06444) describes an alternative technique for parsing PEG grammars: instead of top-down, left-to-right, they propose a bottom-up, right-to-left approach, that correctly handles left-recursion and apparently has also better errors.
It's essentially packrat parsing but with a different approach to dynamic programming, so the semantics are identical.
I know the pest team doesn't currently have a lot of resources but I thought this was a cool idea if someone else is interested. I think it would be possible to make a generic external parsing library that pest can then use instead of its own packrat parser.
Reacted by Eyal Kalderon, Victor Sergienko, Clément Renault, WJH, Lorenz Leutgeb, Maximilian and Zireael07
Activity
Abdillah commentedon Jul 31, 2021
How about this one (https://www.sciencedirect.com/science/article/pii/S0167642314000288)?
I think this one more suitable for top-down by specially handling a recursive pattern.
It uses a memoization just like the packrat parser to store the matching of minimum recursive bound (zero recurse). Then the algorithm incrementally increases the bound to make it greedy enough while still utilizing the stored value to make it faster. When it fails it stops.
The Pest PEG can be augmented with a recursive marker to tell an intentional recursive pattern. Then everything can start from there, while unmarked one still produces error.
Abdillah commentedon Aug 21, 2021
I'm trying to implement the paper (or as close as I understand), here #533.