[antlr-interest] Re: High level semantic analysis
antlrlist
antlrlist at yahoo.com
Fri May 23 05:40:44 PDT 2003
I had a problem similar to lgcraymer's while implementing my
languaje, but I did not found any already-made AST class suitable for
my needs: I needed a lookup table most of the time, but I'm modeling
simple inheritance and polymorphism, so I could not use it for
managing methods. This is, hashtables are not enought for modelling
something like this:
class A {...}
class B
{
method m(A a) // what to insert in the hashTable? "m(A)"?
{ ... }
}
class C extends A {...}
main()
{
create B b;
create C c;
b.m(c); // could not find "m(C)"
}
So what I have done is abstract a little more and have a "Scope"
class. A Scope can deal correctly with simple names and method calls,
once the inheritance structure is present.
This classes, and many others (like an AST with lexical information,
or utilities for parsing the command line) are structured in a
package that I called antlraux. I'll release it when it is ready.
Cya,
Enrique
--- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> See the GCC grammar www.codetransform.com/gcc.html for some ideas
which
> aren't completely hooked up:
>
> CSymbolTable.java--Parser add entries and pushes/pops scope. It
currently
> only looks up entries to resolve whether something is a typedef
name or not.
> But the symbol table is complete and could be used to do other
things.
>
> TNode.java--has support for double linking (so a node can find its
parent)
> which is currently unused. To use it you would first build the
complete
> tree and then call doubleLink(). TNode Also has a slot for the
defNode, the
> idea being to have a tree pass which annotates every use of a
variable with
> the definition to make it easy to find the definition without
having to keep
> track of the current scope. It also has a Hashtable of attributes
so you
> could put anything you want in for the node. That is how you
decorate trees
> in ANTLR.
>
> Note that the above stuff is best for analysis but for
transformation you
> might have extra bookkeeping to do, particularly if you are
deleting or
> changing definitions.
>
> In answer to question 1) ANTLR isn't in the business of
bookkeeping, it just
> does lexing/parsing/tree parsing/tree building. Everything else is
up to
> you. Want more information in your Tokens or ASTs? Just subclass
and put
> it there. Need a symbol table? Make one.
>
> 2) AST is just an interface, right? In java that's easy, I subclass
> CommonToken.java because that has most of the functionality I
need. For C++
> I'll defer to other experts such as Ric or
> http://www.imada.sdu.dk/%7Emorling/.
>
> It seems ANTLR needs more examples/articles/tutorials of proper use
of
> symbol tables and use/def information. I'll put on my list to
write up some
> like this for the GCC grammar.
>
> More on symbol tables
http://www.bearcave.com/software/java/java_symtab.html
> and articles from
> http://developer.java.sun.com/developer/technicalArticles/Parser/ --
> specifically
>
http://developer.java.sun.com/developer/technicalArticles/Parser/Serie
sPt4/
>
> Monty
>
>
> -----Original Message-----
> From: Tiller, Michael (M.M.) [mailto:mtiller at f...]
> Sent: Tuesday, May 20, 2003 5:52 AM
> To: 'antlr-interest at yahoogroups.com'
> Subject: RE: [antlr-interest] Re: High level semantic analysis
>
>
> > 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).
>
> 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.
>
> Let me give you a quick example. A simple Modelica package might
look like
> this:
>
> package Ford
> package Types
> type Torque = Real(quantity="Torque", units="N.m");
> type Pressure = Real(quantity="Pressure", units="N/m^2");
> end Types;
>
> model Test1
> Ford.Types.Torque tau;
> Types.Pressure P;
> end Test1;
> end Ford;
>
>
> In order to elaborate the model Test1, I need to find the
information
> associated with the variables "tau" and "P". Note that while the
definition
> of "Torque" and "Pressure" are in the same place (Ford.Types.*), I
can
> reference them in different ways (Ford.Types.Torque vs.
Types.Torque) but
> the semantics are the same in either case.
>
> So, I have an AST node for my declaration that probably looks
something like
> this:
>
> #(DECL #(TYPENAME "Ford" "Types" "Torque") #(COMPONENT "tau"))
>
> Somewhere else in my AST I have something like:
>
> #(PACKAGE "Ford" ... #(PACKAGE "Types" #(TYPE "Torque" ...) #(TYPE
> "Pressure")))
>
> What I'd like to be able to do is walk the tree and find every
TYPENAME and
> then somehow link, as you say, that #(TYPENAME ...) node back to
the #(TYPE
> "Torque") node.
>
> BUT, what I don't want is this:
>
> #(DECL #(TYPENAME "Ford" "Types" "Torque" #(TYPE "Torque" ...)) #
(COMPONENT
> "tau"))
>
> right? This would change my tree grammar. I want links, but I
don't want
> ANTLR to pay attention to those links for the purposes of tree
walking.
>
> Does this sound right or is my mental model of all this wrong?
>
> 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.
>
> 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).
>
> 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.
>
> --
> Mike
>
>
>
> Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list