Re: Non-sequential compilation.

KODIS@delphi.com said:
> A great deal of compiler theory has a very stream-oriented flavor
> -- left-to-right scans, single vs. multi-pass translators, and so on.


There has even been a an alternating left-right/right-left prototype
compiler for Algol 68 by Bohm of the dutch MC, now CWI (this is described
in a MC TR). A very powerful technique: when doing the right-left phase
you know all the context *after* the current parse point.


> It seems that at least one of the reasons for this is a
> historical desire to be able to translate an arbitrarily large
> source file by reading a chunk, emitting code, and repeating.


Well, also because source that is easy to parse sequentially for a
compiler is easy to parse for a human. Algol 68 required heavvy parsing
technology from the compilers, and also from humans, that could well be
puzzled more than the compiler.


> My question is, has any research been conducted into an
> "all-at-once" translation scheme, where a source file is
> completly read or mapped into memory before translation begins?


Well, this often happens now; but the scanning/parsing is still
sequential.


However some bit of *very* interesting research was done by Pierre Banatre
when he was at Poitiers (if I remember well). His Algol 68 compiler was
multithreaded, with a multiple, large and varying number of rather greedy
threads: a new thread was spawned for each new construct, and would block
on something like a semaphore whenever it found a forward reference. When
some other thread resolved the forward reference, it would raise the
semaphore, and thus the blocked thread could proceed with the now
available info.


A very powerful technique for heavily context dependent syntaxes; also one
that can perhaps exploits some microparallelism, even if I don't know how
many threads he found active on average doing a "typical" compilation.


>From memory, I seem to remember it was published in CACM, between twenty
and fifteen years ago. Tomorrow I will look up my photocopy and of the
paper and extract the full reference...
--

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