Examples/resources for the middle end of a compiler?

There are many ways to approach this. I am going to give you a hint
at three popular ways.


1) If your AST nodes are classes, use the visitor pattern. It takes a
bit to set it up for the first visitor, but after that adding
additional visitors is relatively easy. Note, that the visitor is not
the only relevant design pattern, but it is the one designed to deal
with traversals of the AST. A recent application of the visitor
pattern I saw even dealt with pre-, post-, and inorder traversals. It
wouldn't be hard to do reverse traversals or others either.


2) Use rewriting. In rewriting you write matching rules that match
fragments of the AST and apply some transformation (e.g. compute some
value and attach it to a node or replace one tree with another) to the
matched fragment. There was a recent discussion here about why
pattern matching in ML was popular and it has a lot to do with how
easy it is to write rewrite patterns in ML. Another example of this
is SOURCER, which I believe got folded into recent versions of ANTLR.
It was specifically designed to work with lisp-like ASTs.


3) Use an attribute grammar. In an attribute grammar, you write
equations that compute values by traversing the AST. A recent post
about OX talks about an attribute grammar processor for Bison. Note,
the $variables in Bison or Yacc are a very simplistic form of an
attribute grammar by themselves. They only allow computing
S-attributes (things that can be done in one pass as the grammar is
being built).


One thing worth noting is that these methods are all equally powerful,
in that what you can do with any one of them, you can do with any of
the others, although it may not be quite as "pretty". That is you
can take an attribute grammar and write a set of visitors that
implement the same equations, or compute them in a rewrite rule (and
vice versa for any combination). So,pick your hammer and every
problem will become a nail....


--
******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris

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