Re:LR Parsing: More Elegant Than You Think
by repsilat on Monday June 04, 2018 @09:33PM
(#17234270)
> expressions handled by precedence climbing
I fixed up operator precedence in a hobby project a few weeks ago, and found a really fun way to do it that turned out to require almost no code (but half a page of comments :-).
Basically I just parsed left to right, ignoring precedence (making everything right-associative and equal precedence) and then fixed up the precedence in a simple term rewriting pass after the fact.
The worst-case asymptotic complexity isn't super (quadratic for chains of multiplications, I think) but the code was so satisfying to write and the parser code itself is unbelievably simple.
Oh man I love to abuse term rewriting, I get so much mileage out that one little function...
I fixed up operator precedence in a hobby project a few weeks ago, and found a really fun way to do it that turned out to require almost no code (but half a page of comments :-).
Basically I just parsed left to right, ignoring precedence (making everything right-associative and equal precedence) and then fixed up the precedence in a simple term rewriting pass after the fact.
The worst-case asymptotic complexity isn't super (quadratic for chains of multiplications, I think) but the code was so satisfying to write and the parser code itself is unbelievably simple.
Oh man I love to abuse term rewriting, I get so much mileage out that one little function...