Re:We Need to Know LR and Recursive Descent Parsing Techniques
by sshine on Tuesday January 17, 2023 @11:57AM
(#34414980)
Thank you for mentioning "precedence climbing".
I never had a need for a fast expression parser, so I never explored this option.
For those curious,
https://eli.thegreenplace.net/2012/08/02/parsing-expressions...
It should be possible to combine this with some parser combinator libraries just the same.
The same inefficiency applies to botton-up table driven parsers generated by parser generators too - in a naive implementation the parser will have to go thru N-steps of reduce actions to elevate any terminal up to a top level expression. A smarter generator may eliminate "unit productions" of type mul-expr := add-expr in order to remove this inefficiency. As you say, the other way to handle precedence using a parser generator is using operator precedence & associativity ambiguity resolution, but this is a pain to develop.