ASTs and Type Check Analysis

I am presently involved in a compiler project in C++ that is mirroring
the BASIC grammar extensively.


The early stages of this project is more of a proof of concept more
than diving too deeply into many extremities that will certainly prove
very challenging as this project moves forward. So far I've
developed a Lexer object that returns tokens to my Parser class. The
parser class currently reads these tokens and creates a very
simplistic AST tree.


For this proof of concept, I am using a very basic source file that
contains the following:


PRINT 2+3*6


As I indicated above, we're using BASIC like grammar. The above
example would simply print to the screen the value of "20" and end if
it were to be compiled and executed.


We've taken the Parser to the point where it is creating a very
simplistic AST tree which would look something much like the following
for our example:


CASTFunctionCall
    +- CASTSimpleName
            +- Name: PRINT
    +- CASTExprList
            +- List Size: 1
            +- CASTBinaryExpr
                    +- Operation: '+'
                    +- CASTIntegerLiteral
                            +- Number: 2
                    +- CASTBinaryExpr
                            +- Operation: *
                            +- CASTIntegerLiteral
                                    +- Number: 3
                            +- CASTIntegerLiteral
                                    +- Number: 6


Naturally once the AST tree is created above, I need to use visitor
patterns to do a number of passes. Since my example is extremely
simple, I can see three passes required:


- Pass #1 : Type Analysis
- Pass #2 : Constant Folding
- Pass #3 : Code Generation


Am I off base here ?


Where I am currently getting caught is in the first two phases. What
is the ideal way to layer type information into the AST tree, followed
by constant folding, followed by any other checks prior to compile
time?


Keep in mind of course the next step will be to include variable
declarations and how to assign values to those variables and even
working with very simple function/procedure calls (both code specific
and external library calls to things like DLL functions).


Chris

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