Thursday, August 06, 2026
Unary operators and the Shunting Yard algorithm
I use the Shunting Yard algorithm to handle precedence when parsing expressions in my assembler. It's great because not only is it simple to implement, but it simplifies the code in a hand-written recursive descent parser. The BNF is effectively:
; BNF per RFC-5234
expr = factor *(op factor)
op = '*' ; just the basic ops for now
/ '/' ; adding more is just adding
/ '+' ; them to this definition
/ '-'
factor = literal
/ var
/ '(' expr ')'
literal = DIGIT+
var = (ALPHA / '_') (ALPHA / DIGIT / '_')*
When expressing this BNF via a recursive descent parser,
the function handling expr is where the Shunting Yard algorithm is used,
providing precedence handling.
In my implementation,
the function handling op returns the precedence and associativity from a table:
static struct optable const cops[] =
{
[OP_EXP] = { OP_EXP , AS_RIGHT , 1000 } ,
[OP_MUL] = { OP_MUL , AS_LEFT , 900 } ,
[OP_DIV] = { OP_DIV , AS_LEFT , 900 } ,
[OP_MOD] = { OP_MOD , AS_LEFT , 900 } ,
[OP_ADD] = { OP_ADD , AS_LEFT , 800 } ,
[OP_SUB] = { OP_SUB , AS_LEFT , 800 } ,
[OP_SHL] = { OP_SHL , AS_LEFT , 700 } ,
[OP_SHR] = { OP_SHR , AS_LEFT , 700 } ,
[OP_BAND] = { OP_BAND , AS_LEFT , 600 } ,
[OP_BEOR] = { OP_BEOR , AS_LEFT , 500 } ,
[OP_BOR] = { OP_BOR , AS_LEFT , 400 } ,
[OP_WORD] = { OP_WORD , AS_LEFT , 350 } ,
[OP_NE] = { OP_NE , AS_LEFT , 300 } ,
[OP_LT] = { OP_LT , AS_LEFT , 300 } ,
[OP_LE] = { OP_LE , AS_LEFT , 300 } ,
[OP_EQ] = { OP_EQ , AS_LEFT , 300 } ,
[OP_GE] = { OP_GE , AS_LEFT , 300 } ,
[OP_GT] = { OP_GT , AS_LEFT , 300 } ,
[OP_LAND] = { OP_LAND , AS_LEFT , 200 } ,
[OP_LOR] = { OP_LOR , AS_LEFT , 100 } ,
};
Adding a new operator is pretty easy.
I was able to add the :: operator
(OP_WORD)
and slot it in
(the expression a :: b is the same as a * 256 + b and is used extensively in my 6809 ANS Forth implementation).
The downside,
the Shunting Yard algorithm doesn't handle unary operators very well.
From what research I've done and a proof-of-concept I did,
it can be done.
Unary operators need to be right associative,
but that's the easy part.
It gets ugly with parsing—how to determine if “-” is a subtraction binary operator or a unary negation operator,
and where to place that code,
and it has to go somewhere.
I got it working.
but it involved smearing the Shunting Yard algorithm into the op and factor functions in my case.
And honesty,
I don't think it's worth it just to get -3**2 to return -9 versus 9.
![[Self-portrait with a Christmas Tree] Oh Chrismtas Tree! My Christmas Tree! Rise up and hear the bells!](https://www.conman.org/people/spc/about/2025/1203.t.jpg "Oh Chrismtas Tree! My Christmas Tree! Rise up and hear the bells!")