This is a short bonus post in the Mixfix Operator series. Part 1 was an introduction to mixfix operators and in part 2 we looked at them more closely in the context of a grammar for a boolean algebra and arithmetic language. The implementation of a parser for the language is coming next, but before that I thought it would be interesting to see what the grammar would look like if we removed the mixfix abstraction and mechanically converted the precedence graph to BNF notation.
It turns out this is not that hard if we turn each operator group (graph node) into a separate production and leave out the irrelevant productions for the types of operators we don’t have in those groups. This is especially easy in our case since we only have the same types of operators in each group. I’ll use shorthand names here for brevity.
expr ::= or | and | not | eq | cmp
| add | mul | exp | neg | tightest
or ::= (or | or↑) "|" or↑
or↑ ::= and | not | eq | cmp | tightest
and ::= (and | and↑) "&" and↑
and↑ ::= not | eq | cmp | tightest
not ::= "!" (not | not↑)
not↑ ::= eq | cmp | tightest
eq ::= (eq | eq↑) ("=" | "≠") eq↑
eq↑ ::= cmp | add | mul | exp | neg | tightest
cmp ::= (cmp | cmp↑) ("<" | ">") cmp↑
cmp↑ ::= add | mul | exp | neg | tightest
add ::= (add | add↑) ("+" | "-") add↑
add↑ ::= mul | exp | neg | tightest
mul ::= (mul | mul↑) ("*" | "/" | "mod") mul↑
mul↑ ::= exp | neg | tightest
exp ::= (exp | exp↑) "^" exp↑
exp↑ ::= neg | tightest
neg ::= "-" (neg | neg↑)
neg↑ ::= tightest
tightest := ("(" expr ")") | value
To be honest, encoding the whole graph as BNF is a lot simpler than I initially thought, and so is translating this into a combinator parser. It makes me think whether the mixfix grammar abstraction could be overkill. Of course, this is so easy only because we have relatively few different operators: only left-associative infix, prefix and closed. If we had more operators, with more holes in them, and different types of operators in one group (which is probably not usual, though), perhaps we wouldn’t find the conversion to be that simple any more.
Plainly this simplified scheme won’t help much with user-defined operators and precedence, so I think the mixfix parser abstraction is still useful. However, in cases where there are only a few operators/operator groups, maybe the straightforward translation of this BNF form into parser combinators is preferable. If there’s room left in the next post, I’ll include an alternative implementation based on this scheme.