3 ms·
Encoding expression operator precedence into a grammar (via add-expr, mul-expr, etc, etc) and then directly implementing is very inefficient. For an N-level dee
by HarHarVeryFunny 4y ago
Encoding expression operator precedence into a grammar (via add-expr, mul-expr, etc, etc) and then directly implementing is very inefficient. For an N-level deep expression grammar a recursive descent parser will end up making N-deep recursive calls for every terminal (variable, constant)! In a recursive descent parser it's more efficient just to have a single ParseExpression() function that uses the simple "precedence climbing" technique to handle operator precedence, which will result in at most one recursive call per operator (vs N per terminal). You could even eliminate the recursion completely by using an explicit stack instead.
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 1:1 "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.
- sshine 4y agoThank 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-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions... It should be possible to combine this with some parser combinator libraries just the same.