Re: Non-sequential compilation. (Piercarlo Grandi)
Tue, 21 Sep 1993 23:13:39 GMT

          From comp.compilers

Related articles
Non-sequential compilation. (1993-09-18)
Re: Non-sequential compilation. (1993-09-21)
Re: Non-sequential compilation. (1993-09-21)
Re: Non-sequential compilation. (1993-09-21)
Re: Non-sequential compilation. (1993-09-22)
Re: Non-sequential compilation. (1993-09-27)
Re: Non-sequential compilation. rbe@yrloc.ipsa.reuter.COM (1993-10-04)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Piercarlo Grandi)
Keywords: design
Organization: Prifysgol Cymru, Aberystwyth
References: 93-09-068
Date: Tue, 21 Sep 1993 23:13:39 GMT 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

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...

Post a followup to this message

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