Re: HELP: Using an abstract syntax tree for semantic checking

Neal Harder <nealh@dinigroup.com> writes:


> My problem
> is that I am having trouble effectively traversing the parse tree to
> perform semantic checking (in a second pass).


Several respondents have already given you several pieces of good
advice in this regard. I would just like to add a couple of notes
specific to how I view your problem.


First, I recommend reading the last two issues of the C++ Report, in
particular the articles about the "indirect visitor pattern". This is
a variation on the normal visitor pattern that I believe it is an
attempt to resolve exactly the problems you face. To summarize the
key point of the article, when doing a tree traversal of your AST,
inheritance can be your friend. Group your AST types into hierarchies
such that common operations can be factored up the class tree. It is
painful and error-prone to repeat the same functions in each low level
AST class, so don't. (The technique presented in the article for
doing so has some good points.)


For example, most AST classes in most languages have to do with
expression operators and similar things (plus, minus, times,
array-subscript, pointer-dereference, . . .). It is useful to define
a few routines which generalize the questions you will need to ask of
expression operators and share them for all the expression operator
AST nodes. (Every commercial compiler I can remember working on has
done this. As you have already learned, the job is pretty intractable
if you don't.)


class expression_operator_ast : public ast {
    boolean is_binary();
    boolean is_commutative(); // a typical question
    ast *left_child();
    ast *right_child(); // returns null for unary operators
    }


class plus_ast : public expression_operator_ast;


By the way, much of this will be easier if you AST's are particularly
abstract -- or as other writers have pointed out, aren't real closely
aligned with your parsing process, but instead designed for your
convenience in traversal. (Again, from all the commercial compilers I
have worked on, I have never worked on one which kept anything even
remotely related to a parse tree (at least once the parse was
completed). Of course, most of them were heavily optimizing (and
mostly included Fortran as a legal front-end) where the tendancy is to
use flow-graphs + expressions.)


By the way, several of the tools mentioned in this newsgroup aid you
in doing just that (keeping the AST abstract) each with their own slant:


- Antlr/PCCTS builds lisp-like trees to represent AST's.
- Cocktail has the concept of an abstract grammar and uses that
for inheritance.
- Yacc++ has a "construct" declaration which associates AST nodes
with productions and uses a separate inheritance tree for AST nodes
so that you can factor them as mentioned above.


As one of the Yacc++ authors, you can imagine which model I prefer.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
--

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