CODEWITHSUNDEEP
parsingrecursion
Kijan
Kijan

Reputation: 286

Bypassing left recursion with right-to-left parser

I'm working on a project for my OOP class. Part of the task is developing a parser for a very simple grammar. As far as I understood, by far the simplest parser to implement by hand is recursive-descent parser.

However all operators for the language that I'm parsing are left-associative by nature. As far as I know best way to deal with left recursion enforced by left associativity is to use LR parser instead.

My idea is to parse tokens right-to-left instead, which I believe should enable me to rewrite left associative rules to right associative ones instead.

Will this work, and if not, why not?

Upvotes: 3

Views: 1290

Answers (2)

Luke Hutchison
Luke Hutchison

Reputation: 9230

Good insight -- it turns out this works really well to solve the left recursion problem, but you also have to parse bottom-up, not just right to left. I published a preprint about this.

Pika parsing: parsing in reverse solves the left recursion and error recovery problems

https://arxiv.org/abs/2005.06444

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372992

You can do this if you'd like, though this won't necessarily solve all your problems. If you're familiar with the LL or LR parsers, there are corresponding versions that work right-to-left called RR and RL parsers that pretty much work like LL or LR parsers scanning in the opposite direction. As a result, they have similar weaknesses to the original LL or LR parsing algorithms, so while this might help you, it might not actually solve anything.

As alternatives, you can try rewriting the grammar to see if you can encode precedence and associativity directly. You could also, depending on the grammar, consider using a precedence parsing algorithm like Dijkstra's shunting-yard algorithm. You could also consider using recursive descent parser with backtracking. Finally, you could use something like an Earley parser, which can handle any grammar and isn't too hard to code up.

Upvotes: 4

Related Questions