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

"Rodney M. Bates" <rod.bates@wichita.boeing.com>
7 May 1998 16:54:17 -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)
Re: HELP: Using an abstract syntax tree for semantic checking adrian@dcs.rhbnc.ac.uk (1998-05-07)
Re: HELP: Using an abstract syntax tree for semantic checking danwang+news@CS.Princeton.EDU (Daniel C. Wang) (1998-05-12)
Re: HELP: Using an abstract syntax tree for semantic checking cfc@world.std.com (Chris F Clark) (1998-05-12)
| List of all articles for this month |

From: "Rodney M. Bates" <rod.bates@wichita.boeing.com>
Newsgroups: comp.compilers
Date: 7 May 1998 16:54:17 -0400
Organization: The Boeing Company
References: 98-05-004
Keywords: parse, analysis

Neal Harder wrote:


> .. 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 my experience, emphatically yes, it is worth the time to build an
AST.


We built an Ada front end with a parser generator but were pressured
to avoid spending the time to write the rules for AST
construction. (The generator built a parse tree automatically, since
it has the concrete grammar.) This is like borrowing development time
from a loan shark. We have paid and paid on that debt many times, as
we need to write more tree traversers.


Also, tree representations are inherently space hogs, and all the
excess single-production and delimiter leaf nodes of a parse tree make
this much worse than an AST. After years, we finally added
construction of an AST, but of course this only helps with new
traversers, as we would have to do a lot of rewriting of those already
in existence to use the AST.


If you can use something like the Cocktail generator package, it makes
implementing subsequent passes over a tree a lot less tedious than the
hand coded recursive-traverse-with-giant-case-statement approach you
are reluctant about. It has additional generators (besides lex & yacc
equivalents) which make writing the traversers more like attaching
semantic actions during parsing.


Rodney Bates
rod.bates@wichita.boeing.com
--


Post a followup to this message

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