Re: Two-pass C compilers

One of the problems with the definitions of "pass" that people seem to
have in mind from historical referents is that they are too
technology-specific. In the old days, a "pass" required you to start the
paper tape over or take the deck of cards out of the output stacker and
feed them back into the input stacker. To this day, people think in terms
of file I/O. Suppose I used a memory-mapping call to map the entire
source code into memory. Would I then have a 0-pass compiler?


I'd like to suggest a different style of definition. Divide the compiler
into blocks, each of which has the property that once exited, the block
will never be re-entered. A "strong pass" is a block whose running time
is (at least) linear in the size of the input. A "pass" is a block whose
running time is (at least) linear in the size of the "meaningful" input -
that is, the input less comments, for most languages. A "weak pass" is a
block whose running time is (at least) linear in the size of the tokenized
input.


A strong pass captures the old notion of actually reading the input file
again. Very few, if any, few modern compilers have more than one strong
pass (the entire compiler). Passes, however, are common - in stand-alone
C pre-processors, for example. (Actually, C pre-processors are much more
complex, since their output, after macro expansion and #include
processing, can be much longer than their input, even leaving out
comments. For the purposes of these definitions, the "input" used must
include all source text that will ever be seen, so the #include's don't
matter. For typical uses, the macro expansions won't make much
difference.) Modern compilers that allow arbitrary definition after use
would probably use an extra weak pass. A simple-minded linker fixup
(which scanned the entire executable) would, in some sense, be a weak
pass. (Actually, of course, every linker is already a "weak pass" in this
sense - the issue is whether the linker has more than one of them.)


Note that a pass (of any kind) is not intended to tell you anything about
running time. A "one pass" compiler may re-examine the entire text of
individual functions, say, many times. Passes have to do with the
possible need of the compiler to go back arbitrarily far in the input.


-- Jerry
--

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