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

Neal Harder (nealh@dinigroup.com) wrote:
: 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]


The new RDP release contains about 350 pages of documentation
including a case study manual that looks at the design of two small
compilers for the same small language. One compiler is a single pass
spit-it-out-as-you-go job and the other generates the same code from a
tree intermediate form. The case study also describes several
interpreters for the same language along with a simulator and an
assembler for the byte-code based machine that acts as a compiler
target. We've put an awful lot of effort into producing something that
we think is approachable by neophytes whilst being useful to experts
and we'd very much like to have feedback, especially from people in
the position you're in: needing to get a job done and finding the
library literature wanting.


Caveat: RDP offers a lot of support for the automatic construction of
trees which won't carry over to your lex/yacc environment but it might
give you some pointers on the general approach to tree walkers.


Second caveat: one day we'll extend the tree based compiler to do some
basic optimisations, but we haven't done that yet.


Have a look at


                        http://www.dcs.rhbnc.ac.uk/research/languages/rdp.shtml


                                          Adrian Johnstone and Elizabeth Scott


--
Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email a.johnstone@rhbnc.ac.uk Tel:+44(0)1784 443425 Fax:+44(0)1784 439786
--

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