HELP: Using an abstract syntax tree for semantic checking

Neal Harder <nealh@dinigroup.com>
4 May 1998 22:54:49 -0400

          From comp.compilers

Related articles
HELP: Using an abstract syntax tree for semantic checking nealh@dinigroup.com (Neal Harder) (1998-05-04)
Re: HELP: Using an abstract syntax tree for semantic checking chase@naturalbridge.com (David Chase) (1998-05-07)
Re: HELP: Using an abstract syntax tree for semantic checking dwight@pentasoft.com (1998-05-07)
Re: HELP: Using an abstract syntax tree for semantic checking rod.bates@wichita.boeing.com (Rodney M. Bates) (1998-05-07)
Re: HELP: Using an abstract syntax tree for semantic checking thetick@magelang.com (1998-05-07)
Re: HELP: Using an abstract syntax tree for semantic checking donham@linex.com (Jake Donham) (1998-05-07)
Re: HELP: Using an abstract syntax tree for semantic checking ndc@alum.mit.edu (N. D. Culver) (1998-05-07)
[3 later articles]
| List of all articles for this month |

From: Neal Harder <nealh@dinigroup.com>
Newsgroups: comp.compilers
Date: 4 May 1998 22:54:49 -0400
Organization: Compilers Central
Keywords: parse, question, semantics

          I am working on the front end of a compiler using yacc and C/C++
(The generated parser is in C, my supporting code is in C++). In the
first pass, yacc actions are used to construct a parse tree. My problem
is that I am having trouble effectively traversing the parse tree to
perform semantic checking (in a second pass). I would like to be able
to associate certain actions with the appearance of certain rules in the
grammar- for instance, each time the 'if' ... 'then' rule is reduced a
function is called. But I don't want to load up the yacc grammar with
semantic checking code (hence the parse tree). I realize that this
could be accomplished simply by traversing the parse tree and calling
functions based on a gigantic switch statement (In which the token value
of the node in the parse tree is used to decide which function(s) should
be called) - but with hundreds of rules, this is rather ugly and
inefficient.
          My current approach is to write a function for each rule in the
grammar. At the beginning of the second pass, the top level function is
called. This function calls lower level functions which perform
semantic checking tasks and call lower level functions to collect
information and do additional semantic checking, and so on and so on.
This approach is very tedious and is very inefficient compared to simply
placing function calls in the yacc grammar. I feel that I am not
expoiting the parse tree in this approach.
          None of the textbooks I have read describe how a parse tree can
effectively be used in a multiple pass compiler. Any insight into what
is usually done? Is it worth my time to construct a true abstract
syntax tree rather than a parse tree (The parse tree contains nodes for
every rule in the grammar- an abstract syntax tree contains nodes only
for terminal symbols in the grammar). In either case, how is semantic
checking implemented efficiently? How should the tree be traversed, and
how are actions initiated? Any recommended texts or online resources?
[My impression is that it's more common to turn this structure inside out
and have a relatively small set of functions each of which traverses the
whole tree to check and verify some semantic contraint. -John]




--


Post a followup to this message

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