News for hackers. Stuff that matters.
Re:Operator precedence by textual substitution by vkazanov on Monday May 16, 2022 @03:46AM (#31394487)
It's a problem that's been around for quite a while. Like, since the dawn of computers. And it's been solved numerous times in compiler generators, explained in textbooks, etc. Right now most solutions compete on clarity, simplicity and adaptability, not solving the problem itself.

These days the general consensus is to use the Pratt parser, which is somewhat harder to understand, but ends up not too hard to build and integrate into a recursive decent parser, and is supereasy to modify.

Here's one popular explanation:

https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-...

What I find funny is that Pratt's parser was never really a theoretical result and was never properly covered in popular compiler textbook.

Re:Operator precedence by textual substitution by cwzwarich on Monday May 16, 2022 @10:27AM (#31397803)
> What I find funny is that Pratt's parser was never really a theoretical result and was never properly covered in popular compiler textbook.

The theory behind precedence parsing was studied a decade earlier by Floyd (who is cited in Pratt's paper). Pratt's own paper is more about the justification of considering operators to have semantic importance rather than productions of nonterminals.

Re:Operator precedence by textual substitution by vkazanov on Tuesday May 17, 2022 @11:15AM (#31411948)
Yup.

And this idea makes all the difference for language implementers.

Re:Operator precedence by textual substitution by ufo on Monday May 16, 2022 @09:14AM (#31396665)
One recent book that covers it is Crafting Interpreters, by Bob Nystrom. Maybe if we give it some more time it will start counting as a popular compiler textbook ;)

https://craftinginterpreters.com/

Re:Operator precedence by textual substitution by nsajko on Monday May 16, 2022 @08:10AM (#31396006)
> What I find funny is that Pratt's parser was never really a theoretical result

Sorry, what?

Re:Operator precedence by textual substitution by vkazanov on Monday May 16, 2022 @11:31AM (#31398917)
What I wanted to say is that it's a popular practical algorithm. But theoretically speaking it's a variant of the shunting yard algorithm. Books typically describe the latter.