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.
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.
It is worth noting that the author's lrpar tool (linked in the article) doesn't actually require extra compilation steps or code generation. This perhaps comes at the expense of less flexible lexing and parser actions. But lrpar comes with a tool 'nimbleparse', which given a grammar and an input file parses the input file bypassing code generation. This reduces the grammar editing/testing cycle by quite a lot. Inspired by that I have been working on a lsp based version of the tool for a while, to make the whole thing as responsive as possible...
I'd like to add nuance in two places:
> If you're writing a parser for a language which is ambiguous, you might be able to use the conflict resolution offered by YACC and friends. However, in general, I suggest avoiding YACC's conflict resolution if possible, as you have to at least somewhat understand the underlying LR algorithm to understand how conflicts have been resolved.
I'd say: Specifically for binary operator precedence and associativity, definitely use conflict resolution of Yacc and friends instead of rewriting the grammar. An ambiguous grammar for binary operators might look like:
Disambiguating in Yacc and friends involves a few lines like: whereas rewriting the grammar above to be unambiguous is a mess: Disambiguating by resolving shift/reduce conflicts means fewer states, whereas disambiguating by rewriting the grammar means more states. Perhaps, as Laurence points out in this article wrt. LALR and SLR: This probably doesn't matter at all on modern computers.Any other shift/reduce or reduce/reduce conflict caused by some other ambiguity than specifically a binary operator, e.g. when you have multiple if-then-else-if-then-else and you want to know where an else belongs: You need to be quite into LR parser generators to understand what's happening; took quite a lot of guessing, trial-and-error when I worked with them, and I probably forgot again. I'd probably document these as non-trivial choices if I were maintaining a Yacc-like parser, and I'd generally avoid syntax that is ambiguous in this way (although I don't think you can always do that).
> If you need the best possible performance or error recovery, recursive descent parsing is the best choice. If you know you will need this and you're designing a new language, at least create an LL grammar, since from that you can derive a recursive descent parser. [Bear in mind that LL grammars are more annoying to write than LR grammars which is why I suggest avoiding LL unless you have this very specific use case.]
I would say: If you get used to parser combinator libraries, you can get a fast LL parser that is also fast to write and does not require extra compilation steps like practically every LR parser generator. I.e. you can skip the part where you convert your grammar file into a native-$YOUR_LANG parser, because parser combinators are embedded DSLs, some of which are just as fast as their hand-written recursive-descent parser. Parser combinator libraries usually have excellent error reporting capability. (The best example I know is Haskell's diagnose package. [2]) And some of them have backtracking capability, so that for those few parts where your grammar isn't LL, you can go back and try something else.
Modern parser combinator libraries like Haskell's Parsec / Megaparsec has helper functions for generating a parser that effectively translates an operator associativity/precedence table into an LL parser; so you get the nicely readable description, and the transformed LL parser that goes with it; see Megaparsec's makeExprParser [3]:
[1]: https://stackoverflow.com/questions/898489/what-programming-... [2]: https://github.com/mesabloo/diagnose#error-reporting-made-ea... [3]: https://hackage.haskell.org/package/parser-combinators-1.3.0...