Make it easy on yourself.
With that said, Factor is really cool.
FORTH doesn't have one to speak of. No dynamic memory management, no garbage collection. It's about as bare-bones as you can get.
PostScript, the JVM, the CLR and so forth are all backed by runtimes with powerful functionality.
LLVM SSA, modulo phi nodes, encodes expressions as DAGs in a completely straightforward sense: every operation names its arguments, and those names serve as unique references to a sub-DAG, since they cannot be reassigned. So given the final operation, you can follow the arguments recursively all the way through, completely transparently. Stack machines like the CLR and JVM encode expressions as trees serialized in a post-order - and to the extent that they use 'dup', they also encode expressions as DAGs.
A symbolic interpretation of a CLR or JVM instruction flow, or LLVM SSA instruction flow, can reconstruct the source expression DAG/tree; at which point you can re-encode it using the other approach.
And producing output targeting LLVM is even easier than it appears, because you don't need to worry about SSA yourself; just allocate stack locals (with alloca) and use the mem2reg pass to turn it into valid SSA.