All C-style programming languages have too many levels of operator precedence. This confuses their programmers, who have to remember not just the basic PEMDAS stuff but the really arcane precedences, too:

• x & y == z doesn’t mean (x & y) == z but rather x & (y == z). That is, it generally Does The Wrong Thing.

• x == y == z and x < y < z have the “correct” natural precedence, but if you see one of these in code, it’s almost certainly a bug, because it’s not asking whether x, y, and z have the same value; it’s asking whether (x == y) has the same value as z!

• Some expressions are simply bizarre. I’d bet you have no intuition for the meaning of x < y | z, do you? Of course you can reason that < has roughly the precedence of ==, and | has roughly the precedence of &, so this should parse roughly the same as x == y & z. But that’s not intuition, it’s reasoning: a conscious process that requires active engagement.

• !x && y is another expression that’s easy to reason about, once you’re on the lookout for it; but at a glance it’s easy to mistake for !(x && y).

• Even limiting ourselves to simple arithmetic, it’s easy to misinterpret an expression like x / y * z.

Jonathan Müller wrote on this subject in “Operator precedence is broken” (July 2017); it may be worth your time to go read his post before tackling the rest of this one.

All five of the problems above are solvable within the operator-precedence subsystem! The key observation is that all of these ways of “making an expression problematic” boil down to that the expression contains two adjoining operators whose resolution is non-obvious: & next to ==, say, or / next to * (but not the reverse).

By “next to,” of course I don’t mean that the operators must appear lexically consecutive in the source code: we also want to diagnose x / a->b * z, despite the -> operator’s coming lexically between / and *. It turns out that the meaning of “next to” is exactly captured by this definition:

Two operators @ and $ within the same expression are said to be “next to” each other if parsing the expression with an operator-precedence parser requires at some point comparing the relative precedences of @ and $.

In this post I construct a simple operator-precedence parser using Dijkstra’s shunting-yard algorithm to parse an expression grammar almost, but not quite, entirely unlike C’s; and then modify it to diagnose all five of the issues above (and many more).

Lexer

Here’s a simple lexer for a C-style expression grammar. A convenient thing about C’s lexer is that every operator token is either a single byte, or else a string where every prefix of that string is also a valid operator. For example, <<= is a valid token; and so are its prefixes << and <. Therefore our lexer never needs to “look ahead” more than a single character.

Since this lexer is merely an uninteresting prerequisite for the fun parsing part, we’ll impose no structure on our non-operator tokens: alphanumeric tokens like 42, 0x7, foo, if, 5g are all treated uniformly. In fact, since we use Python’s built-in isalnum, we’ll consider underscore to be an (unrecognized) operator, not an identifier.

OPERATORS = [ '+', '-', '*', '/', '%', '<', '<=', '>', '>=', '==', # etc. ] class Lexer: def tokenize(self, chars): self.token = '' for ch in chars: if ch.isspace(): yield from self.emit_if(True) elif ch.isalnum(): yield from self.emit_if(not self.token.isalnum()) self.token += ch else: yield from self.emit_if(self.token.isalnum()) yield from self.emit_if((self.token + ch) not in OPERATORS) self.token += ch yield from self.emit_if(True) def emit_if(self, b): if b and self.token: yield self.token self.token = '' 

Test with:

while True: line = input() tokens = Lexer().tokenize(line) print(' '.join(tokens)) 

For example, entering “abc*d<=-ef/g” should print “abc * d <= - ef / g.”

Parser (without diagnostics)

Let’s make a simple shunting-yard parser. It will consume a stream of tokens in infix order (such as the stream generated by our previous step’s lexer) and produces a stream of the same tokens rearranged in postfix (RPN) order. In the input stream unary and binary - are represented identically; but in the output stream we’ll distinguish unary operators by the prefix U. Thus the output “a b U- -” will correspond to the input “a - -b,” while the output “a b - U-” will correspond to the input “-(a-b).”

The parser needs to know the precedence of each operator. We encapsulate that comparison in a helper function. Notice that unary operators are given to has_higher_precedence already encoded with the U prefix.

PREC = { k: v for v, ks in enumerate([ ['||'], ['&&'], ['|'], ['^'], ['&'], ['==', '!='], ['<', '<=', '>', '>='], ['<=>'], ['<<', '>>'], ['+', '-'], ['*', '/', '%'], ['.*', '->*'], ['U'+t for t in ['+', '-', '!', '~', '*', '&']], ['.', '->'], ]) for k in ks } PREC['('] = -float('inf') def has_higher_precedence(a, b): return PREC[a] >= PREC[b] 

This code assumes every operator is left-associative. Supporting right-associative operators such as = or ** or => simply requires inspecting the associativity of a:

def has_higher_precedence(a, b): if a in ['=', '**', '=>']: return PREC[a] > PREC[b] else: return PREC[a] >= PREC[b] 

Now the parser itself goes like this:

def infix_to_postfix(tokens): stack = [] expect_primary = True for token in tokens: if token.isalnum(): if not expect_primary: raise ValueError('got "%s" when a binary operator was expected' % token) expect_primary = False yield token elif token == '(': if not expect_primary: raise ValueError('got "(" when a binary operator was expected') stack.append(token) elif token == ')': if expect_primary: raise ValueError('got ")" when a primary-expression was expected') while stack and stack[-1] != '(': yield stack.pop() if not stack: raise ValueError('right parenthesis with no preceding left parenthesis') stack.pop() elif expect_primary: if ('U' + token) not in PREC: raise ValueError('unknown unary operator "%s"' % token) stack.append('U' + token) else: if token not in PREC: raise ValueError('unknown binary operator "%s"' % token) while stack and has_higher_precedence(stack[-1], token): yield stack.pop() stack.append(token) expect_primary = True while stack: if stack[-1] == '(': raise ValueError('left parenthesis with no matching right parenthesis') yield stack.pop() 

Test with:

while True: line = input() tokens = Lexer().tokenize((ch for ch in line)) try: print(' '.join(infix_to_postfix(tokens))) except ValueError as e: print('error:', e) 

For example, entering “abc*d<=-ef/g” should print “abc d * ef U- g / <=.”

Adding diagnostics

Since every pair of “adjoining” operators passes through has_higher_precedence, it’s simple to diagnose all the problems I listed at the top of this post. At first we might think to do it via a blacklist of known-problematic pairs:

def has_higher_precedence(a, b): if a in ['U!'] and b in ['&&', '||']: print("warning: (%sx %s y) is ambiguous" % (a, b)) elif a in ['/', '%'] and b in ['*']: print("warning: (x %s y %s z) is ambiguous" % (a, b)) elif a in ['&', '^', '|'] and b in ['==', '!=', '<', '<=', '>', '>=']: print("warning: (x %s y %s z) is ambiguous" % (a, b)) elif a in ['<', '<='] and b in ['<', '<=']: print("warning: (x %s y %s z) doesn't mean what you think" % (a, b)) return PREC[a] >= PREC[b] 

However, this leaves you vulnerable to failures of imagination. For example, it seems to me that we should also warn about x & y << z (which means x & (y << z), not (x & y) << z). Where in the maze of ifs above should that case be inserted?

A better approach is to diagnose anything that’s not on a whitelist of uncontroversially non-problematic pairs! Out of the roughly 667 operator-pairs that our has_higher_precedence might ever see, only about half of them are non-problematic in my book.

Some pairs are nonsensical. For example, as Jonathan noted, !p->*x has the “wrong” precedence, so that it will not type-check; therefore we can omit the pair (U!, ->*) from our whitelist. Other pairs, such as (+, &&), seem nonsensical at first glance but in fact we must whitelist them anyway. Consider the expression:

a < b + 1 && c < d 

In parsing this expression we call has_higher_precedence with the following pairs: (<, +); (+, &&); (<, &&); (&&, <). If (+, &&) weren’t on our whitelist, we’d get a warning — which we don’t want! We certainly should try to diagnose “unusually typed” expressions such as b + 1 && c; but we can’t do it with this operator-precedence technique alone.

However, it seems to me that we can safely omit the pair (<<, &&) from our whitelist: those two operators really should never appear next to one another. In fact I think << should always be parenthesized; I can’t think of any operator (between the extremes of . and =) where x << y @ z is both clear and useful. The useful expressions, such as x << y + 1, are not clear; and the clear expressions, such as x << y && z, are not useful.

My suggested whitelist ends up looking like this:

UNPROBLEMATIC = sum([ [('||',r) for r in ['||', '==', '!=', '<', '<=', '>', '>=', '+', '-', '*', '/', '%']], [('&&',r) for r in ['&&', '==', '!=', '<', '<=', '>', '>=', '+', '-', '*', '/', '%']], [(x,x) for x in '|^&'], [(l,r) for l in ['==', '!=', '<', '<=', '>', '>='] for r in ['||', '&&', '+', '-', '*', '/', '%']], [(l,r) for l in ['+', '-', '*'] for r in ['||', '&&', '==', '!=', '<', '<=', '>', '>=', '+', '-', '*', '/', '%']], [('/',r) for r in ['||', '&&', '==', '!=', '<', '<=', '>', '>=', '+', '-']], [('%',r) for r in ['||', '&&', '==', '!=', '<', '<=', '>', '>=']], [(l,r) for l in ['U+', 'U-', 'U~', 'U*', 'U&'] for r in ['||', '&&', '|', '^', '&', '==', '!=', '<', '<=', '>', '>=', '<=>', '<<', '>>', '+', '-', '*', '/', '%']], ], []) def has_higher_precedence(a, b): if a in ['==', '!='] and (a == b): print('warning: (x %s y %s z) doesn\'t mean what you think' % (a, b)) elif a in ['<', '<='] and b in ['<', '<=']: print('warning: (x %s y %s z) doesn\'t mean what you think' % (a, b)) elif a in ['>', '>='] and b in ['>', '>=']: print('warning: (x %s y %s z) doesn\'t mean what you think' % (a, b)) elif a[0] == 'U' and b in ['.*', '->*']: print('warning: (%sx%sy) means (%sx)%sy' % (a[1:], b, a[1:], b)) elif a in ['(', '.', '->', '.*', '->*'] or b in ['.', '->', '.*', '->*']: pass # not problematic elif (a,b) in UNPROBLEMATIC: pass # not problematic elif a[0] == 'U': print('warning: (%sx %s y) is ambiguous; consider adding parentheses' % (a[1:], b)) else: print('warning: (x %s y %s z) is ambiguous; consider adding parentheses' % (a, b)) return PREC[a] >= PREC[b] 

Test it against some of Jonathan’s exotic expressions and it spews warnings — but I don’t think any of these warnings are “wrong”!

a & b + c * d && e ^ f == 7 warning: (x & y + z) is ambiguous; consider adding parentheses warning: (x & y && z) is ambiguous; consider adding parentheses warning: (x && y ^ z) is ambiguous; consider adding parentheses warning: (x ^ y == z) is ambiguous; consider adding parentheses a b c d * + & e f 7 == ^ && arr + 32 < ~a | b warning: (x < y | z) is ambiguous; consider adding parentheses arr 32 + a U~ < b | !x && y warning: (!x && y) is ambiguous; consider adding parentheses x U! y && 

Get the full Python code here.

See also:

• “Two musings on the design of compiler warnings” (2020-09-02)