News for hackers. Stuff that matters.
Re:Operator precedence by textual substitution by w4rh4wk5 on Monday May 16, 2022 @03:28AM (#31394406)
Implementing operator precedence isn't that hard actually.

Essentially you take note of the first operator's precedence and keep consuming input until you reach an operator with lower precedence than you currently have. The precedence you use for comparison is updated each step.

Here's some code that does that: https://github.com/uibk-dps-teaching/ps_cc_2021/blob/0ad022c...

Only thing you have to watch here: with a recursive descent parser you might need an extra step to fix the associativity (right-to-left vs. left-to-right) if that's important for your application.

Here's that: https://github.com/uibk-dps-teaching/ps_cc_2021/blob/0ad022c...

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.
Re:Operator precedence by textual substitution by choeger on Monday May 16, 2022 @03:38AM (#31394453)
It's only not hard if you have a parser that allows you to carry that kind of context. Admittedly, operator precedence is so important that most parser (generators) have some canonical way to handle it. But try to implement a language with user-defined binary operators and consider the mess at your hands.
Re:Operator precedence by textual substitution by kryptiskt on Monday May 16, 2022 @04:29AM (#31394679)
Pratt parsing (as described in https://matklad.github.io//2020/04/13/simple-but-powerful-pr...), handles operator precedence and different operator types (prefix, infix, postfix and mixfix) in a very neat manner, and it's easy enough to stuff user-defined operators in there.
Re:Operator precedence by textual substitution by w4rh4wk5 on Monday May 16, 2022 @03:51AM (#31394505)
What complexity?! The precedence is a simple integer value. Even when you include associativity, there are only two options: right-to-left, left-to-right.

Doesn't matter whether that information is language defined or user defined.

For instance in Haskell, that's all the information you provide. You'd use either `infixl` or `infixr` (depending on which associativity you want) followed by an integer defining the precedence for the given operator.

The parser just needs a table to look up the precedence (and associativity) for a given operator. But a parser already needs a bunch of different tables in order to work, so that's certainly not a problem.

Re:Operator precedence by textual substitution by choeger on Thursday May 19, 2022 @04:37AM (#31432154)
> The parser just needs a table to look up the precedence (and associativity) for a given operator. But a parser already needs a bunch of different tables in order to work, so that's certainly not a problem.

Think about how you'd implement an independent parser for such a language, say for the sake of pretty printing it to html. Module A uses a user-defined operator that has been defined in Module B. You effectively cannot parse A correctly before you parse and load B, but the fact that you need to parse and load B is "hidden" in some import declaration that in turn needs to be parsed first. That's what I call a mess.

Re:Operator precedence by textual substitution by ghusbands on Monday May 16, 2022 @10:09AM (#31397458)
What alternatives do you believe offer easier support for user-defined binary operators? Almost all parsing technologies are more rigid and more complicated that numerical precedence offers.
Re:Operator precedence by textual substitution by choeger on Thursday May 19, 2022 @04:38AM (#31432158)
I have no idea, really. If I would, I would try to submit a paper to POPL or so.
Re:Operator precedence by textual substitution by danhau on Monday May 16, 2022 @04:07AM (#31394580)
I also find operator precedence quite easy to implement.

In my parser, when it encounters two binary expressions `a * b + c`, it always initially parses them as `a * (b + c)` into temporary AST nodes. Then it compares the precedence of the operators and, if needed, rewrites the nodes to form the correct expression.

Re:Operator precedence by textual substitution by mamcx on Monday May 16, 2022 @11:28AM (#31398877)
> Implementing operator precedence isn't that hard actually.

Like all the claims about making languages: Truth until is a big fat lie.

Try to do the full precedence for more complex languages than formula evaluators could become harder than expected (you think you nailed, then a edge-case happens).