Thought I'd share a fun Prop project I'm working on for the Elev8-FC.
A little background: the Elev8-FC does all the IMU math on the Prop, in floating point. In order to keep it small and fast, I'm using a modified F32 driver to do the computation. I added a stream processor to it so I can feed it a list of instructions to execute - it processes the whole sequence and sets a flag when it's done, leaving the main cog free to do other tasks. The "instructions" are just 4 byte values: opcode, input1, input2, and output. The input/output values are byte indices into an array of 32 bit variables, mostly floats, but some ints.
All of this works well, but I've been coding it by hand. That was fine initially, but as the project has grown in scope it's become a bit of a pain point - changing the code isn't trivial, so typically I write in C on the PC until I get the math right, then manually translate to the FPU instructions, and I often make mistakes when translating.
Nothing makes mistakes faster than a computer, so I figured I'd try my hand at automating the process, and it works!
I looked into using Yacc/Lex (Bison/Flex) to generate the parser stage, but the documentation for those tools is terrible, and everything I found online was either "calculator" or "C", with nothing in between. Since I was really only interested in parsing a finite subset of C, with no control statements, I decided to write my own. There's still a bunch of work to do, but it's checked in to GitHub in the Flight-Controller project if you're curious.
First up is converting the code into an expression tree - This is done in two stages, tokenizing and parsing. The tokenizing stage is mostly a pre-filter that reads the source and passes along tokens, like "comment", "label", "operator", "function", "parenthesis", "constant", and so on, along with the relevant token content. For a label it would be the variable name.
The parser takes the token stream and makes sure that the tokens make sense. For example:
This code: rx = gx * const_GyroRate;
Becomes: label, assignment, label, operator*, label, end
From the parser, I use a technique called "Recursive Descent" to generate an expression tree. This handles converting an infix expression with operators into a tree that represents the expression, and the order of operations derived from operator precedence. You end up with something like this:
From the expression tree I generate the actual operators, along with a blob of which variables and constants were used, and any const initialization I need. I got it working last night, and actually replaced one of the core math routines in my Elev8 with the generated code, and it works exactly as expected. Even cooler, since the code is just C, I can run the exact same code on the PC in a previewer, feeding it data from the Elev8, and show both results overlaid on each other, like this:
The 3D "X' on the right is actually two models - one computed on the PC, and one computed on the Elev8, showing that they match (this is good). This frees me up to code new math functions in C on the PC, and when I'm happy with the results, have the F32 stream generated automatically from the source.
I've written a code generator before, but never the front-end of a compiler, so this was a fun diversion and I learned a bunch. It might also be useful for others, so if you have a project that needs to run a long sequence of floating point math in a hurry, this might help you.
I've attached an example of a cpp source function and the generated F32 instruction stream.