[antlr-interest] Re: High level semantic analysis

[lgcraymer]

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 
"output 
> > template" approach for this final pass--details are still being 
> > worked out.  I think that their "rule based semantic analysis" 
could 
> > be effected through one or more transformation passes, one or more 
> > linking passes (tree walks which build links connecting AST 
nodes), 
> > 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 
they existed).

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

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

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.

--Loring

> --
> Mike


 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/