8 Enforestation Algorithm🔗

The Rhombus parsing algorithm is similar to figure 1 of the Honu paper, but with some key differences:

The implementation represents pending operators during enforestation through the Racket continuation, instead of using an explicit stack; that is, instead of pushing on the stack, a recursive call is made to the enforestation function. A transformer can call back into the enforestation function, and in that case, it provides a current operator for precedence purposes, and the enforestation function will stop when it encounters either the end of the input or an operator at lower precedence. When enforestation stops at an operator with lower precedence, the enforestation function returns both the parsed form and the remaining terms.

An identifier/operator is connected to a transformer using Racket’s mapping machinery (define-syntax, etc.). The enforestation algorithm is parameterized over the space (in the sense of (provide (for-space ....))) it should consult and accessor–predicate functions that extract infix and prefix transformers from compile-time bindings.

When a context includes only prefix macro operators that are constrained to consume all available terms, then enforestation is not really relevant. In that case, the context just needs a way to find and invoke operator transformers. The Rhombus expander provides a shortcut that skips the full enforestation algorithm for that simpler kind of context.