Precedence levels are dead; long live precedence sets
It was recently pointed out on lobste.rs that Zig has overhauled how its parser does operator precedence. The related documentation contains this cute little flowchart of the new operator precedence rules:
``` ┏━━━━━━━━━━━━━━━━━━━┓ ┃(expr) ┃ ┃x() x[] x.y x.* x.?┃ ┃E!T ┃ ┃x{} ┃ ┃!x -x -%x ~x &x ?x ┃ ┗━━━━━━━━━▲━━━━━━━━━┛ ┌─────────────┬──────┴───────┬───────┬──┬──┬─┐ │ │ │ │ │ │ │ ┏━━━━━━┷━━━━━┓╭Non╌Chaining╮ ╭Non╌Chaining╮┏┷┓┏┷┓┏┷┓│ ┃* *% *| / ||┃╎ % ╎ ╎ << <<| >> ╎┃&┃┃^┃┃|┃│ ┗━━━━━━▲━━━━━┛╰╌╌╌╌╌╌▲╌╌╌╌╌╯ ╰╌╌╌╌╌╌▲╌╌╌╌╌╯┗▲┛┗▲┛┗▲┛│ ┏━━┷━━━━━━━━━━━━━┷━┓ ┌────┴───────┴──┴──┘ │ ┃+ - +% -% +| -| ++┃ │ │ ┗━━━━━━━━━━━▲━━━━━━┛ │ │ ╭┴╌Non-Chaining╌┴╮ │ ╎== != < <= >= >╎ │ ╰╌╌╌▲╌╌╌╌▲╌╌╌╌╌╌╌╯ ┌──────┬─────┘ ┏━┷━┓┏━┷━┓ ┏━━━┷━━┓┏━━┷━━┓ ┃and┃┃or ┃ ┃orelse┃┃catch┃ ┗━▲━┛┗━▲━┛ ┗━━━▲━━┛┗━━▲━━┛ ╭╌╌┴╌╌╌╌┴╌╌╌╌╌╌╌╌╌╌╌╌╌╌┴╌╌╌╌╌╌┴╌╮ ╎ Any expression location ╎ ╰╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╯ ```
If you're not familiar with Zig, some of these operators might be foreign to you. By removing some of the more exotic operators, and doing a few other tidy-ups, we get this flowchart:
``` ┏━━━━━━━━━━━━━━━┓ ┃(e) ident const┃ ┗━━━━━━━▲━━━━━━━┛ ┏━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━┓ ┃x(e,…,e) x[e] x.ident x.* x.?┃ ┗━━━━━━━━━━━━━━▲━━━━━━━━━━━━━━┛ ┏━━━━━━━┷━━━━━━━┓ ┃!x -x ~x &x ?x ┃ ┗━━━━━━━▲━━━━━━━┛ ┌─────┬─────────────┴──┬────────┬────┬────┬──┐ │ │ │ │ │ │ │ ┏━━━━━━┷┓╭Non┴Chaining╮╭Non╌Chaining╮┏━┷━┓┏━┷━┓┏━┷━┓│ ┃x*y x/y┃╎ x%y ╎╎ x<<y x>>y ╎┃x&y┃┃x^y┃┃x|y┃│ ┗━━━━━━▲┛╰╌╌╌▲╌╌╌╌╌╌╌╌╯╰╌╌╌╌╌╌▲╌╌╌╌╌╯┗━▲━┛┗━▲━┛┗━▲━┛│ ┏┷━━━━━┷┓ ┌┴────────┴────┴────┘ │ ┃x+y x-y┃ │ │ ┗━━━▲━━━┛ │ │ ╭╌╌╌╌╌╌┴╌╌╌Non-Chaining╌╌╌┴╌╮ │ ╎x==y x!=y x<y x<=y x>=y x>y╎ │ ╰╌╌╌╌╌╌╌╌╌╌╌╌▲╌╌╌╌╌╌╌▲╌╌╌╌╌╌╯ ┌────────────┘ ┏━━━┷━━━┓┏━━┷━━━┓ ┏━━━━┷━━━━━┓ ┃x and y┃┃x or y┃ ┃x orelse y┃ ┗━━━▲━━━┛┗━━▲━━━┛ ┗━━━━▲━━━━━┛ ╭╌╌╌┴╌╌╌╌╌╌╌┴╌╌╌╌╌╌╌╌╌╌╌╌╌╌┴╌╌╌╌╌╮ ╎ Any expression location ╎ ╰╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╯ ```
I vastly prefer this presentation format over a table of operators which lists facts such as "addition has precedence level 5, exclusive-or has precedence level 7", but just in case it isn't clear, the meaning of this flowchart is:
- In general, an expression can consist of anything reachable from the "_Any expression location_" box.
- Within a thick-bordered box, `x` and `y` represent expressions, which can come from the same box or from any box reachable from it (if being pedantic about associativity, say that `x` can come from the same box but `y` cannot).
- Thin-bordered "_Non-Chaining_" boxes are similar, except that neither `x` nor `y` can come from the same box.
- Within any box, `e` represents a general expression (i.e. restart from the "_Any expression location_" box).
If implementing a language, the question arises of how to translate this chart into a parser. There is plently of literature on how to translate precedence _levels_ into a parser; see for example Pratt Parsing Index and Updates. If following the concrete exposition in Crafting Interpreters, we'd give each box in the flowchart a unique small integer, and end up with something like:
``` prec_primary = 14 # (e) ident const prec_call = 13 # x(e,…,e) x[e] x.ident x.* x.? prec_unary = 12 # !x -x ~x &x ?x prec_factor = 11 # x*y x/y prec_mod = 10 # x%y prec_shift = 9 # x<<y x>>y prec_bit_and = 8 # x&y prec_bit_xor = 7 # x^y prec_bit_or = 6 # x|y prec_term = 5 # x+y x-y prec_comparison = 4 # x==y x!=y x<y x<=y x>=y x>y prec_and = 3 # x and y prec_or = 2 # x or y prec_orelse = 1 # x orelse y prec_none = 0 # Any expression location ```
This approach works great for precedence levels, but the flowchart fundamentally cannot be represented using precedence levels. Instead, we need precedence _sets_:
``` prec_primary = 0b100000000000000 # (e) ident const prec_call = 0b110000000000000 # x(e,…,e) x[e] x.ident x.* x.? prec_unary = 0b111000000000000 # !x -x ~x &x ?x prec_factor = 0b111100000000000 # x*y x/y prec_mod = 0b111010000000000 # x%y prec_shift = 0b111001000000000 # x<<y x>>y prec_bit_and = 0b111000100000000 # x&y prec_bit_xor = 0b111000010000000 # x^y prec_bit_or = 0b111000001000000 # x|y prec_term = 0b111110000100000 # x+y x-y prec_comparison = 0b111111111110000 # x==y x!=y x<y x<=y x>=y x>y prec_and = 0b111111111111000 # x and y prec_or = 0b111111111110100 # x or y prec_orelse = 0b111000000000010 # x orelse y prec_none = 0b111111111111111 # Any expression location ```
> If this looks to you like the reachability matrix of the flowchart, well done: it is exactly the reachability matrix of the flowchart.
Precedence _levels_ can be manipulated in a parser using arithmetic operators: Crafting Interpreters contains `precedence + 1` and `precedence <=` in key places. Precedence _sets_ instead require bitwise tricks: isolate lowest set bit, clear lowest set bit, and bitwise and. Any level-based parser can be converted to a set-based parser by suitable replacement of arithmetic with these bitwise tricks, and I hope more languages follow Zig's lead here, freeing themselves from the tyranny of precedence levels and instead adopting precedence sets.