We are working with LibreOffice Calc ODS sheets, which are pretty terrible as a format (since the references are not normalized in the formulas, they can't repeat them even when they behave identically, and they duplicate most of the XML namespaces in the attributes).
We parse and normalize the references from A1 to R1C1 form, and then deduplicate the formulas (by text) and extract all of the immediates (and mark some of them as input, so that they can be varied at runtime).
Then we pass the deduplicated formulas through instaparse (which is spectacular) with a relatively simple grammar, and propagate some of the constants.
I then extract the references from the AST, while at the same time replacing SUMIF/MINIFS/MAXIFS/AVERAGEIF and similar with simple addition/min/max of known cells, where the tests are known at compile time. Then those ASTs are complied to functions (ignoring our cross-function optimizations).
Then it's just down to generating a complete DAG of dependencies, and using that to sort the assignments (cells) topologically. The sheet can be evaluated naiively at that point by injecting the references into each subsequent assignment/cell and storing the result in a map (ranges injected as a seq over a range).
There's a lot more to it, and it's getting better all the time, but that's the gist of it. Many real spreadsheets are not well-behaved, and they have dependency patterns which are more difficult to handle (i.e. ranges that refer to the current cell, or future cells, dynamically). The compiled output is getting more and more static, and will probably be reduced to some form of ssa, possibly even well-formed enough to be popped casually into LLVM.
It would be some help if the ODS format were improved, it takes several seconds just to parse the hundreds of megabytes of XML in our amazing spreadsheet, and a lot of it is redundant.
The common pattern in spreadsheets is to have a set of columns of repeated formulas. i.e.
| A | B | C | D |
|-----|-----|----------------|-----|
1 | | | | 0.12|
2 | 42| 42| =A2*B2+C1*$D$1 | |
3 | 69| 69| =A3*B3+C2*$D$1 | |
Where, you'll note, although the function and reference shape in C2 and C3 is identical, the text is not.Whereas, with R1C1-type references.
| 1 | 2 | 3 | 4 |
|-----|-----|----------------------------|-----|
1 | | | | 0.12|
2 | 42| 42| =RC[-2]*RC[-1]+R[-1]C*R1C4 | |
3 | 69| 69| =RC[-2]*RC[-1]+R[-1]C*R1C4 | |
The text of the formula is exactly the same in both copies.This makes it a lot cheaper to deduplicate them, because we don't need to run the whole parser on the 400k+ formula invocations in our sheet, and then compare the ASTs rather than text; since in this form, there are only a few thousand unique expressions rather than a few hundred thousand.
It's really for the best that they don't. ODS is XML, so they'd probably make the AST XML as well, which would outrageously oversized.