Re: Number of compiler passes

George Neuner wrote:


>>* Flex + Bison to create AST
>>* 1 Over AST to find declarations (and re-declarations)
>>* 2 Over AST to detect which variables are used in which functions
>>* 3 Over AST to find undeclared references
>>* 4 Over AST to find the type of each expression and note type mismatches
>>* 5 Over AST to find the access-type (read/write/both) of each expression
>>* 6 Over AST to perform optimizations
>>* 7 Over AST to translate to target language
>
> You don't give much detail of your language, but I don't see how
> "readability or provability" would be harmed by combining passes 1 & 2
> ...
> Assuming variables must be declared, processing declarations gives you
> all you need - the symbol table(s) you construct will provide scoping
> for non-local variables and functions. I don't see a need for two
> passes.


In the source language, a function can use variables from outside its
scope. More importantly, these variables could be declared after the
function is. This is okay as long as this function is not called
before the declaration of these variables.


> and passes 3 & 4. [I numbered them above for convenience]
> ...
> Similarly, undeclared references will not be represented in your
> symbol table. They will be caught when you look them up to determine
> their type. You can assign them a special nil type so going forward
> any expressions using them fail to type properly.


You're right about these, though. They could be merged and I will
certainly consider it. The only reason for me to keep them separate is
because they are conceptually different operations.


> I don't know what you mean by "access-type" of an expression - unless
> you're talking about I/O in which case I still don't know what you
> mean. We could be having a terminology disconnect - to my mind an
> "expression" always computes or side effects, so it always reads
> operands and sometimes writes a result.


Yes, I suppose I am stretching the definition a bit. An expression has a
type (bool, int, etc.). But to me it also has an access type. This is
either readonly, writeonly or readwrite. It basically specifies whether it
is an r-value, an l-value or both.


> I would think that your optimization phase itself would consist of
> multiple passes as a number of optimizations are possible even on an
> AST form.


Yep, probably. I haven't actually started on this stage yet.


> And since you are targeting C from a language that has nested
> functions, you might actually need more than one pass to affect the
> translation. Simple function nesting as in Pascal can be handled
> easily, but full closures as in Lisp requires constructing runtime
> data structures and a lot more analysis.


For now, functions in the source language cannot be passed, assigned or
returned yet. But in the future I hope to include functional aspects into
the language. I'm already planning for it in the design.


Thanks for your reply,


--
Michiel Helvensteijn

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