[PRL] syntax-directed translation to basic blocks?

Dave Herman dherman at ccs.neu.edu
Sat Apr 29 20:07:06 EDT 2006


Is there such a thing as a syntax-directed translation of a program into 
basic blocks? Obviously the challenge is the graph structure.

In [Wand 83], Mitch gives a syntax-directed compilation (is that what 
"transduction" means?) of an imperative language with loops into an 
abstract assembly language. That takes care of cycles, but 
interestingly, the translation seems to be unable to preserve sharing; 
specifically, it duplicates the continuation of an `if' test.

A translation into basic blocks should never duplicate a basic block. Is 
there a functional way to express this translation with sharing?

Thanks,
Dave

[Wand 83] Mitchell Wand. Loops in Combinator-Based Compilers. POPL 1983. 
http://doi.acm.org/10.1145/567067.567086



More information about the PRL mailing list