Bypassing left recursion with right-to-left parser

3
votes

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?

2
parsingrecursion
By far the easiest parsers to write are the ones where you just specify the (context-free) grammar, and the parser generator tool handles all the problems. I've had tremendously good experience with GLR parsers. (Earley parsers based are also good but generally not suitable for production due to speed issues). – Ira Baxter
I agree. Although I have some experience with parser generators (YACC/Bison) for this project I'd prefer using a hand-written parser instead. First of all, I don't even think I'm allowed to use external libraries, and using Bison or something similar would probably require that. Second, I'd like to learn more about parsing and compiler design in general, so i want to take this opportunity to do so, especially since the grammar I need to parse is very simple, so it's a perfect situation to learn something new. Anyway I believe in this context recursive-descent parser is the simplest solution. – Kijan
OK. Then check out my SO answer on how to write recursive descent parsers. These handle left recursion easily. See stackoverflow.com/questions/2245962/… – Ira Baxter

2 Answers

3
votes

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.

1
votes

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