Puzzle: operator precedence
-
One common method is to have a grammar with a hierarchy of nonterminals to express precedence and associativity, e.g. something like this:
Nobody in his right mind would build a parser by hand-built recursive descent, though.
By the way, an equally interesting problem is the dual problem of how to pretty-print ASTs with a minimal number of parentheses (considering operator precedence and associativity).
One can even go so far and have only one grammar from which both a parser and a pretty-printer with that property can be derived, but only insane people would ever do that.
-
@Klaus said in Puzzle: operator precedence:
Nobody in his right mind would build a parser by hand-built recursive descent, though.
Why not?
@Horace said in Puzzle: operator precedence:
Why not?
Because look-ahead is too difficult to implement, and grammar refactorings like left-factoring suck. If parsing speed isn't super-important, use a parser combinator library. Otherwise, use a parser generator such as ANTLR. I'm a big fan of SGLR parsing - it allows you to express your grammar in the most direct way possible and avoids the complications of a separate scanner.
-
It's just a simple language to do calculations and logical operations on literals or input variables. No functions and the only flow control is if...else. Structure is limited to parentheses and blocks (to group the if...else). I know there are libraries available for this sort of thing, but my hand coded implementation is less than 1000 lines of code and has everything I need. Or at least, so far so good. I solved the problem of this thread by calling a precedence imposer method on binary operations after the recursive tree builder returns the right hand side. If the right hand side of the operation is itself a binary operation, like so:
a <op1> (b <op2> c)
then the precedence imposer compares precedence of op1 and op2 and if op1 precedence is >= op2, the operation is re-organized as
(a <op1> b) <op2> c
Seems to be working so far. This has been a fun little project, as evidenced that I'm working on it on a weekend.
-
According to the google calculator (math expressions typed into the search box), the exponent operator has different associativity than minus.
4-3-2 is calculated as (4-3)-2
4^3^2 is calculated as 4^(3^2)Python appears to share this. That throws a wrench into my rules that all equal precedence operators are computed left to right.
