[antlr-interest] Tree Rewrite Caveats

Robin Hamilton-Pennell robin at pozytron.com
Fri Jun 6 16:40:36 PDT 2008


Terence,

Not sure what you mean by "first one," but if you are referring to the
"every (sub)rule that you are rewriting must match a tree node" thing,
here's a little more info.

I've been using the tree rewriting stuff for a bit now, so I
understand it a little better. For my explanation, here's a section of
my grammar that works fine (I've simplified it a lot, only the
relevant portions included):

statement
	: ^(EXPR_STATEMENT expr)					-> ^(EXPR_STATEMENT expr)
	| ^(BLOCK_STATEMENT basicBlock)				-> ^(BLOCK_STATEMENT basicBlock)
	| /*  more statement rules... */
	;
expr	: ^(TYPE expr typeParams)					-> ^(TYPE expr typeParams)
	| /*   more tree rewrite rules... */
	| literal						
	| basicBlock
	| /*   more rule references... */
	;
literal
	: IntLiteral							-> IntLiteral
	| FloatLiteral						-> FloatLiteral
	| BoolLiteral						-> BoolLiteral
	| StringLiteral						-> StringLiteral
	| 'null'								-> 'null'
	| /*   more token references... */
	;

This grammar works fine. Note that it's fine for me to rewrite lexer
(token) references, and tree references, but I don't rewrite rule
references.

If, however, I change expr to rewrite a rule reference:

expr	: ^(TYPE expr typeParams)					-> ^(TYPE expr typeParams)
	| /*   more tree rewrite rules... */
	| literal									-> literal
	| basicBlock
	| /*   more rule references... */
	;

... parsing will always fail with errors like the following:
Exception in thread "main" java.lang.NullPointerException
	at org.antlr.runtime.tree.CommonTreeAdaptor.getChildIndex(CommonTreeAdaptor.java:173)
	at CogTreeRewriter.expr(CogTreeRewriter.java:1469)
	at CogTreeRewriter.expr(CogTreeRewriter.java:1294)
	at CogTreeRewriter.statement(CogTreeRewriter.java:382)
	at CogTreeRewriter.basicBlock(CogTreeRewriter.java:2398)
	at CogTreeRewriter.statement(CogTreeRewriter.java:745)
	at CogTreeRewriter.program(CogTreeRewriter.java:210)

The generated code from around line 1469 looks like this:
                    // AST REWRITE
                    // elements: literal
                    // token labels:
                    // rule labels: retval
                    // token list labels:
                    // rule list labels:
                    retval.tree = root_0;
                    RewriteRuleSubtreeStream stream_retval=new
RewriteRuleSubtreeStream(adaptor,"token
retval",retval!=null?retval.tree:null);

                    root_0 = (CogTree)adaptor.nil();
                    // 91:17: -> literal
                    {
                        adaptor.addChild(root_0, stream_literal.nextTree());

                    }

                    retval.tree = (CogTree)adaptor.rulePostProcessing(root_0);
                    input.replaceChildren(adaptor.getParent(retval.start),
                                          adaptor.getChildIndex(retval.start),
                                          adaptor.getChildIndex(_last),
                                          retval.tree);
                    }
                    break;

If you need any other information, please let me know. I'm happy to help out!

Thanks,
Robin

On Fri, Jun 6, 2008 at 3:27 PM, Terence Parr <parrt at cs.usfca.edu> wrote:
>
> On May 23, 2008, at 8:21 PM, Robin Hamilton-Pennell wrote:
>
>> Hi all,
>>
>> Been playing around with the tree rewriting stuff in 3.1b1. It's much
>> better than the previous test build was. I'm not through with my
>> experimentation and likely will find more things, but I thought I'd
>> make some notes on a few troubles I ran into, in case it helps anyone
>> else.
>>
>> Firstly (this is probably true of tree parsers in general), if you use
>> a custom class as your AST node and the Java target, you will probably
>> need to add the method errorNode() in your TreeAdaptor class. This
>> will also entail either adding error node utility methods to your AST
>> node, or creating a custom subclass of CommonErrorNode. I could be
>> completely misguided on this; please say so.
>>
>> Second, every (sub)rule that you are rewriting must match a tree node,
>> I think. This seems obvious in retrospect, but it took me a while to
>> figure out. That means that you can't do this:
>>
>> stmt:
>>   expr   ->   expr
>>   ;
>
> Really?  Why not?
>
>> However, you can do either of the following (or change your AST
>> generation code):
>>
>> stmt:
>>   expr  // omit rewrite rule
>>   ;
>>
>> stmt:
>>   // (after changing your AST generation)
>>   ^(EXPR expr)   ->   ^(EXPR expr)
>>   ;
>>
>> I should mention that both of these issues involves the rewrite=true
>> option. I haven't tested the effects of turning that off, actually.
>
> Can you tell me what goes wrong with the first one?
> Ter
>>
>>
>> Again, I could simply be completely misguided on this, in which case,
>> please enlighten me.
>>
>> Thanks,
>> Robin
>
>


More information about the antlr-interest mailing list