RPN as intermediate code?

I am struggling trying to convert my C interpreter from a tree-based
design to an intermediate-code design. I have, up until now simply
used YACC to produce my parse tree, and then just stepped through the
tree executing the code. This has worked fine for most things,
including if/else, compound statements, and for/while loops.


I now want to move to storing (and executing) some form of intermediate
code. I really like the idea of encoding into an 'execution string', like
bc does, and reverse polish works great for this, as long as I stick to
encoding expressions. But this model falls apart when I get into things
like conditionals and loops, and I am completely baffled how to do
short-circuit logic like this. For instance, I can compile the following
code into the RPN strings shown (which execute easily):


        x = a*(b+c) -> "a b c + * x ="
        y = sqrt(b*b-4*a*c) -> "b b * 4 a * c * - 1 sqrt callfunc y ="
        z = foo(a,bar(b),c) -> "a b 1 bar callfunc c 3 foo callfunc z ="


        (actually, all the identifiers and constants go into a dictionary
        and are replaced by a lookup index, but you get the idea...)


However, when I get into conditionals and loops, I have absolutely no idea
how to proceed. Do I really have to get all the way down to the level of
computing jump offsets and implement these as conditional gotos? Or is
there a more elegant way that I just haven't found yet?


And why can't I find any literature about this sort of thing? All the
compiler books I can find say 'Here is reverse polish. Its a good
intermediate representation because its stack-like', but then they go off
and do something completely different.


Anyways, I'll take any help I can get here.


-- Noel (gorelick@esther.la.asu.edu)
[I've used conditional jumps with ofsets. They're ugly, but they're not hard
to do. The alternative is to have tokens like WHILE ENDWHILE, IF THEN
ELSE ENDIF and have the interpreter scan over parts you're skipping and keep
a stack of places to retur tom but that's a lot of scanning and skipping.
-John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.