[antlr-interest] Re: High level semantic analysis
lgc at mail1.jpl.nasa.gov
Tue May 20 11:47:46 PDT 2003
Yahoo did weird things with my first attempted response. Assuming
that went into the bit bucket, I'll try again.
--- In antlr-interest at yahoogroups.com, "Tiller, Michael (M.M.)"
<mtiller at f...> wrote:
> > From: lgcraymer [mailto:lgc at m...]
> > Subject: [antlr-interest] Re: High level semantic analysis
> > ANTLR's approach to the general problem is syntax tree
> > transformation (possibly multiple passes) followed by an "output"
> > pass which might generate an internal form that might not be tree
> > structured or might produce code. Ter is working towards an
> > template" approach for this final pass--details are still being
> > worked out. I think that their "rule based semantic analysis"
> > be effected through one or more transformation passes, one or more
> > linking passes (tree walks which build links connecting AST
> > and a resolution pass to "decorate the tree" (attribute grammar
> > terminology).
> Is there any built-in support for the "linking" and "decorating" you
talk about. Being relatively inexperienced in this aspect, I found
this to be one of the more confusing parts. It was easy for me to see
how the lexer, the parser and even the tree walker worked (and why
Yes and no. The support is through user-developed AST classes;
"decorating" is simply the assignment of attributes, and linking is
the setting of reference pointers. Ter and I have talked about adding
some target-language-independent attribute syntax to ANTLR so that AST
classes would be automatically defined. Right now, all of this has to
be done in action code.
> ANTLR was great for getting to the point where all the information
was nicely arranged in a tree. What I struggle with is "Now what?".
For example, one of the first passes I could imagine doing on my AST
would be type/name lookup. Once I've done that, I'd like to keep that
information around. I'm assuming that is what you mean by linking.
... (example deleted)
Type/name information is usually kept in a symbol table as a routine
optimization. For Java, look at java.util.Hashtable; for C++, check
out the "map" template in the standard library.
By linking, I mean setting pointers to link one AST node to another in
a separate part of the tree. The idea is to generate a graph which
can be navigated efficiently for the analysis and output generation
> Assuming I am right (which is a big assumption), I didn't see
anything in ANTLR that supports these kinds of associations. Am I
missing something? I know I can define my own AST node types and I
could add some data structures to support linking but there were two
reasons I didn't do this:
> 1) I figured if this is what I'm supposed to do then everybody would
have to do it and ANTLR would support it somehow. The fact that I
didn't see this functionality in ANTLR led me to think perhaps I
wasn't going about this the correct way.
ANTLR started out with the lex/yacc view that access to target
language actions was essential to the specification process. ANTLR is
still evolving from there. For many things, ANTLR does provide
support, but that support is through target language action code.
ANTLR 3 will get a little further away from that than ANTLR2.
> 2) I was quite concerned about how all this linking and associating
would impact the garbage collection system for AST nodes. To be
honest, I find the whole process of defining a new AST type pretty
complicated. There seem to be so many different AST types and I never
know when to use one or the other (e.g when do I use my AST type and
when do I use RefAST, etc).
Performance cost is not high; you can either choose to use
reference-counted pointers for the linking or bypass this if dangling
pointers are not going to be a problem.
> Now I'm not really blaming ANTLR for either of these issues. I'm
just saying that for me this was somewhat intimidating and so I was
hesitant to get all tangled up in implementing these details.
> These are just some things to consider in the development of ANTLR 3
that might make the tool easier and more approachable to people like
Part of this is that ANTLR documentation, while excellent for a public
domain package, is not quite what one would get with a mature
commercial product. The documentation will improve: Ter is actively
teaching, and students are very useful for debugging documentation.
We are envisioning a "language translator's workbench" for ANTLR
3--that may help as well. Mostly, I think that your difficulties are
just learning curve-related--problems look different from a language
processing perspective, and it takes a while to adjust to the new
perspective. That said, I still wish that I could figure out
some generic insight from the paper you referenced and how it could be
applied to ANTLR.
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
More information about the antlr-interest