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

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
--

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