3 ms·

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

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-expression-parsing-made-easy/ 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.

nsajko 4y ago
> What I find funny is that Pratt's parser was never really a theoretical result Sorry, what?
- vkazanov 4y ago
  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.
ufo 4y ago
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/ https://craftinginterpreters.com/
cwzwarich 4y ago
> 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.
- vkazanov 4y ago
  Yup. And this idea makes all the difference for language implementers.

nsajko 4y ago

> What I find funny is that Pratt's parser was never really a theoretical result Sorry, what?

vkazanov 4y ago
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.

ufo 4y ago

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/ https://craftinginterpreters.com/

cwzwarich 4y ago

> 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.

vkazanov 4y ago
Yup. And this idea makes all the difference for language implementers.