A way to find all subtrees of a particular type?

Expand Messages
• Hi, Is there a way to find all subtrees of a particular type? For example, let s say I d like to find all subtrees related to multiplication operation (*)
Message 1 of 9 , May 21, 2003
Hi,

Is there a way to find all subtrees of a particular type? For example,
let's say I'd like to find all subtrees related to multiplication
operation (*) regardless of what is being multiplied.

I was looking at findAllPartial() but it appears that it will not do that.

Any ideas? Thanks
• ... Won t that find all single nodes? Ter -- Co-founder, http://www.jguru.com Creator, ANTLR Parser Generator: http://www.antlr.org Co-founder,
Message 2 of 9 , May 21, 2003
On Wednesday, May 21, 2003, at 08:50 AM, rustydstone wrote:

> Hi,
>
> Is there a way to find all subtrees of a particular type? For example,
> let's say I'd like to find all subtrees related to multiplication
> operation (*) regardless of what is being multiplied.
>
> I was looking at findAllPartial() but it appears that it will not do
> that.

Won't that find all single nodes?

Ter
--
Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org
Lecturer in Comp. Sci., University of San Francisco
• ... Not sure I understand. Let me rephrase the question: I have a somewhat complex tree, some nodes of that tree are multiplication nodes (e.g. 4 * 5). I d
Message 3 of 9 , May 21, 2003
--- In antlr-interest@yahoogroups.com, Terence Parr <parrt@j...> wrote:
> Won't that find all single nodes?

Not sure I understand.

Let me rephrase the question: I have a somewhat complex tree, some
nodes of that tree are multiplication nodes (e.g. 4 * 5). I'd like to
be able to find ALL multiplication nodes of the tree. I can obviously
manually walk the tree and look for the nodes of certain type but I
was hoping there would be a simpler way.

Thanks
• If you find all single MULT nodes have you not found precisely what you re looking for? Ter ... -- Co-founder, http://www.jguru.com Creator, ANTLR Parser
Message 4 of 9 , May 21, 2003
If you find all single MULT nodes have you not found precisely what
you're looking for?

Ter

On Wednesday, May 21, 2003, at 10:55 AM, rustydstone wrote:

> --- In antlr-interest@yahoogroups.com, Terence Parr <parrt@j...> wrote:
>> Won't that find all single nodes?
>
> Not sure I understand.
>
> Let me rephrase the question: I have a somewhat complex tree, some
> nodes of that tree are multiplication nodes (e.g. 4 * 5). I'd like to
> be able to find ALL multiplication nodes of the tree. I can obviously
> manually walk the tree and look for the nodes of certain type but I
> was hoping there would be a simpler way.
>
> Thanks
>
>
>
>
>
> Your use of Yahoo! Groups is subject to
> http://docs.yahoo.com/info/terms/
>
>
>
--
Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org
Lecturer in Comp. Sci., University of San Francisco
• ... You are absolutely right. Thanks
Message 5 of 9 , May 21, 2003
--- In antlr-interest@yahoogroups.com, Terence Parr <parrt@j...> wrote:

> If you find all single MULT nodes have you not found precisely what
> you're looking for?
>
> Ter

You are absolutely right. Thanks
• ... There s one small problem though. When creating a target AST, one must know both target s type and text, otherwise findAllPartial() won t work. In case of
Message 6 of 9 , May 21, 2003
> --- In antlr-interest@yahoogroups.com, Terence Parr <parrt@j...> wrote:
>
> > If you find all single MULT nodes have you not found precisely what
> > you're looking for?
> >
> > Ter
>
> You are absolutely right. Thanks

There's one small problem though. When creating a target AST, one must
know both target's type and text, otherwise findAllPartial() won't
work. In case of MULT I know both. In other cases, I do know the
target's type but not text.

Any ideas? Thanks
• There is a quick fix. Redefine equals in your base AST class so that some text string--say --matches anything. That way, equals has the default
Message 7 of 9 , May 21, 2003
There is a quick fix. Redefine "equals" in your base AST class so
that some text string--say ""--matches anything. That way, "equals"
has the default behavior in all but the one special case and you get
the match behavior that you want by using the special string when
building an AST for the findAllPartial().

--Loring

--- In antlr-interest@yahoogroups.com, "rustydstone"
<rustydstone@y...> wrote:
> > --- In antlr-interest@yahoogroups.com, Terence Parr <parrt@j...>
wrote:
> >
> > > If you find all single MULT nodes have you not found precisely
what
> > > you're looking for?
> > >
> > > Ter
> >
> > You are absolutely right. Thanks
>
> There's one small problem though. When creating a target AST, one
must
> know both target's type and text, otherwise findAllPartial() won't
> work. In case of MULT I know both. In other cases, I do know the
> target's type but not text.
>
> Any ideas? Thanks
• ... Sorry for hijacking this thread but this reminded of one of the items on my ANTLR to-do list (no, seriously): Moan about ANTLR s use of equals() in
Message 8 of 9 , May 21, 2003
> There is a quick fix. Redefine "equals" in your base AST class so
> that some text string--say ""--matches anything.

<SNIP>

Sorry for hijacking this thread but this reminded of one of the items
on my ANTLR to-do list (no, seriously):

"Moan about ANTLR's use of equals() in Java/C++ (and Equals() in C#)."

We recently had a situation where we wished to consider Tokens/AST-
Nodes equal only if they had the same type, text and came from the
same file. Simply re-defining equals/Equals for our Token/AST
subclass would have been the natural approach however, that broke
many other little bits since ANTLR generated code sometimes depends
on it's (re-)definition of equality.

Can we move ANTLR's notion of equality to some other method - perhaps
hasSameTypeAndText()/HasSameTypeAndText()- so that equals()/Equals()
can once again assume their intended meanings please?

Cheers,

Micheal
• In other words, you wanted a context-dependent equality for ASTs. That strikes me as a really bad idea--AST nodes represent elements in context-free grammars
Message 9 of 9 , May 21, 2003
In other words, you wanted a context-dependent equality for ASTs.
That strikes me as a really bad idea--AST nodes represent elements
in context-free grammars and ANTLR manipulates these as context-free
entities unless the programmer specifies the context dependency via
semantic predicates. The "text and type" approach is much more
natural for the problem domain.

--Loring

--- In antlr-interest@yahoogroups.com, "micheal_jor"
<open.zone@v...> wrote:
> > There is a quick fix. Redefine "equals" in your base AST class
so
> > that some text string--say ""--matches anything.
>
> <SNIP>
>
> Sorry for hijacking this thread but this reminded of one of the
items
> on my ANTLR to-do list (no, seriously):
>
> "Moan about ANTLR's use of equals() in Java/C++ (and Equals() in
C#)."
>
> We recently had a situation where we wished to consider Tokens/AST-
> Nodes equal only if they had the same type, text and came from the
> same file. Simply re-defining equals/Equals for our Token/AST
> subclass would have been the natural approach however, that broke
> many other little bits since ANTLR generated code sometimes
depends
> on it's (re-)definition of equality.
>
> Can we move ANTLR's notion of equality to some other method -
perhaps
> hasSameTypeAndText()/HasSameTypeAndText()- so that equals()/Equals
()
> can once again assume their intended meanings please?
>
> Cheers,
>
> Micheal
Your message has been successfully submitted and would be delivered to recipients shortly.