Unary operators and the Shunting Yard algorithm

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.

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: https://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

https://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.