[antlr-interest] wildcard in tree grammar

Terence Parr parrt at cs.usfca.edu
Mon Oct 20 11:36:21 PDT 2008


Actually, tree pattern matching tools and languages typically use '_'  
to mean wildcard subtree (or actually "don't care"). I wonder if this  
is better because it is more readable:

^('+' _ _ )

  looks better than

^('+' ^(.) ^(.))

Then

^('+' . .)

would indicate matching '+'-rooted subtree with two leaf nodes as  
children.  If the children were subtrees, you'd get a syntax error.

Hmm... ^(.) or _ actually is just a rule:

wildcard : ^(. .+) ;

 From Johannes' post:

> I don't see anything wrong with this suggestion, even if it creates  
> some
> work on my side. ;) Looking at the nature of the bug, fixing it this  
> way
> won't change the behaviour of already generated and written  
> grammars, right?

Actually, it might break some things because '.' matches an entire  
subtree right now; I would be changing in to specifically match a  
node. The problem is that we use it for both right now, which is just  
plain wrong. anybody using it has a potential bug in there.   
Fortunately, people are probably not using wildcard entry grammars too  
much.

ugh... sorry about this, I thought I was being clever at some point in  
the past; blech.

Ter

On Oct 20, 2008, at 11:26 AM, Terence Parr wrote:

> Hi gang.  We have a problem in terms of wildcards. bug:
>
> http://www.antlr.org:8888/browse/ANTLR-248
>
> says it all:
>
> wildcard is single node in tree grammar analysis but node or tree at
> runtime
>
> We need both single node wildcard and tree wildcard. DFA analysis sees
> '.' as a single node.
>
> If you say ^('+' . .), that expects two single nodes as children at
> analysis time. The problem is that at runtime we want wildcard to
> match a subtree as well. We need to tell the analysis specifically
> which one we mean. I can see a situation where you want to match
> literally a single node versus a subtree. I don't want to flip
> wildcard mean subtree.
>
> I proposed a syntax to mean wildcard subtree: ^. instead of simple .
> or, perhaps ^(.) as special syntax, which might be a bit more explicit
> right? The new syntax would force the analysis to see ". DOWN .+ UP".
> Ack, the way to do this is actually to make the grammar create the
> appropriate NFA rather than tweaking the analysis.
>
> Anyway, those in favor of ^(.) and . to mean wild-card tree (must be a
> tree) and wildcard (single node)?  those opposed?
>
> I need to fix this for the new book examples. I'm doing this really
> cool filter mode for trees where you can say "for any addition you
> find in the tree, do this".
>
> Ter
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>



More information about the antlr-interest mailing list