Re: Back End Generators

>There are lots of very interesting CG techniques. One of my favorites
>is CG via _parsing_, which uses an inherently ambiguous grammar to
>recognize a parse tree, and then uses dynamic programming to pick the
>winning parses based on their execution-time costs. The code
>generation itself is via a standard Knuth attributed grammar. Very
>elegant.


This was the Graham-Glanville algorithm; it was Glanville's PhD thesis.
I seem to have lost the original paper. The idea was to use an LR parser
to recognize substrings in a prefix representation of the IR tree, and
associate code generation actions with the parse. There have been several
follow-up papers on this. The only commercial compiler I have heard of
that used this was an old Intel cross-compiler for x86 development.


My favorite was Davidson & Fraser's "Code Selection through Object Code
Optimization". The idea was to generate simple instructions, then
optimize them into more complex instructions/addressing modes by
examining logically adjacent instructions and doing symbolic substitution
on their algebraic definitions, looking for a new instruction whose
algebraic definition has the combined effect. This approach is used in
the gcc compiler; it generates incredibly good code for CISC machines
like the 680x0.


But I've strayed too far from the original topic...


-- John
--

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