Tree transformation question (Antlr3)

[Chuck Fry]

The Antlr 3 tree grammar fragment below is a piece of an AST optimizer that I am building:

aReduction: 
        ^(op1=associativeOp ^(op2=associativeOp (rest+=.)+) arg3=. {$op1.start.getType() == $op2.start.getType()}? )
      -> ^($op2 $rest $arg3)

associativeOp:
        OR_KYWD
    |   AND_KYWD
    |   PLUS
    |   MINUS
    |   ASTERISK
    |   MAX_KYWD
    |   MIN_KYWD
    ;

But it doesn't work, apparently because variables op1 and op2 are bound to tokens and not subtrees, and so constructing the transformed AST fails. More details available upon request.

Replacing the variables with literals (e.g. AND_KYWD) and getting rid of the predicate generates the desired result, but only for AND_KYWD. I'd like to do this without having to specify every operator in an N-way 'or' rule.

Is there a straightforward way to do this? I searched the Antlr 3 docs and sample code, but didn't find any examples like this, where the variable is at the root of a subtree. Thanks.
-- Chuck

[Jim Idle]

First thing I see is that the rewrite should be:

->^($op2 $rest+ $arg3)

Your rest variable will be a list so needs a '+', not a token. $op1 and $op2 are tokens, and that's what you want according to your grammar.

If you want trees at associativeOp, then in the parser grammar that produces that part of the tree you would need to give them a node token:

associativeOp:

   t=OR_KYWD ->^(ASOP $t)

...

Then your tree grammar would look for that node. However, I can think of no good reason for you to do that ;)

Usually, an operator, whether unary, binary, teriary or whatever would be the node, specified in the parser grammar something like this:

expr: e1=expr1 op=associativeOP e2=expr1 -> ^(associativeOP $e1 $e2) ;

Then your tree parser woudl be:

expr: ^(associativeOp expr expr);

And the associativeOp is a token of course. So I wonder if your statement about being tokens is the wrong way around and all you are missing is the '+' from $rest?

Hope that helps,

Jim

--
You received this message because you are subscribed to the Google Groups "antlr-discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to antlr-discussi...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Chuck Fry]

On Nov 26, 2014, at 5:58 PM, Jim Idle <ji...@temporal-wave.com> wrote:

First thing I see is that the rewrite should be:

->^($op2 $rest+ $arg3)

Your rest variable will be a list so needs a '+', not a token. $op1 and $op2 are tokens, and that's what you want according to your grammar.

Thanks for catching that, Jim.

However, just fixing that still yields the same result. Here's the output from jdb:

Pass 1 output:

(PLEXIL (ACTION maxTest (Concurrence (VARIABLE_DECLARATIONS (VARIABLE_DECLARATION Integer l) (VARIABLE_DECLARATION Integer m) (VARIABLE_DECLARATION Integer n)) (VARIABLE_DECLARATIONS (VARIABLE_DECLARATION Real x) (VARIABLE_DECLARATION Real y)) (PostCondition (&& (&& (&& (&& (! (isKnown l)) (== m 1)) (== n 2)) (== x 2.0)) (== y 7.1))) (ACTION unknownInts (ASSIGNMENT l (max l 0))) (ACTION equalInts (ASSIGNMENT m (max 1 1))) (ACTION unequalInts (ASSIGNMENT n (max 1 2))) (ACTION equalReals (ASSIGNMENT x (max 2.0 2.0))) (ACTION unequal (ASSIGNMENT y (max 7.0 7.1))))))

Semantic checks succeeded

Set deferred all org.antlr.runtime.tree.RewriteEmptyStreamException

Exception occurred: org.antlr.runtime.tree.RewriteEmptyStreamException (to be caught at: plexil.PlexilTreeTransforms.associativeReduction(), line=785 bci=1,198)"thread=main", org.antlr.runtime.tree.RewriteRuleElementStream._next(), line=158 bci=20

main[1] where

  [1] org.antlr.runtime.tree.RewriteRuleElementStream._next (RewriteRuleElementStream.java:158)

  [2] org.antlr.runtime.tree.RewriteRuleSubtreeStream.nextNode (RewriteRuleSubtreeStream.java:77)

  [3] plexil.PlexilTreeTransforms.associativeReduction (PlexilTreeTransforms.java:755)

  [4] plexil.PlexilTreeTransforms.bottomup (PlexilTreeTransforms.java:443)

  [5] plexil.PlexilTreeTransforms.bottomup (PlexilTreeTransforms.java:17)

  [6] org.antlr.runtime.tree.TreeRewriter$3.rule (TreeRewriter.java:116)

  [7] org.antlr.runtime.tree.TreeRewriter.applyOnce (TreeRewriter.java:61)

  [8] org.antlr.runtime.tree.TreeRewriter.applyRepeatedly (TreeRewriter.java:79)

  [9] org.antlr.runtime.tree.TreeRewriter$1.post (TreeRewriter.java:95)

  [10] org.antlr.runtime.tree.TreeVisitor.visit (TreeVisitor.java:66)

  [11] org.antlr.runtime.tree.TreeVisitor.visit (TreeVisitor.java:60)

  [12] org.antlr.runtime.tree.TreeVisitor.visit (TreeVisitor.java:60)

  [13] org.antlr.runtime.tree.TreeVisitor.visit (TreeVisitor.java:60)

  [14] org.antlr.runtime.tree.TreeVisitor.visit (TreeVisitor.java:60)

  [15] org.antlr.runtime.tree.TreeVisitor.visit (TreeVisitor.java:60)

  [16] org.antlr.runtime.tree.TreeVisitor.visit (TreeVisitor.java:60)

  [17] org.antlr.runtime.tree.TreeRewriter.downup (TreeRewriter.java:97)

  [18] plexil.Compiler.pass3 (Compiler.java:139)

  [19] plexil.Compiler.main (Compiler.java:76)

main[1] up 2

main[3] dump stream_op2

 stream_op2 = {

    org.antlr.runtime.tree.RewriteRuleElementStream.cursor: 0

    org.antlr.runtime.tree.RewriteRuleElementStream.singleElement: null

    org.antlr.runtime.tree.RewriteRuleElementStream.elements: null

    org.antlr.runtime.tree.RewriteRuleElementStream.dirty: false

    org.antlr.runtime.tree.RewriteRuleElementStream.elementDescription: "rule op2"

    org.antlr.runtime.tree.RewriteRuleElementStream.adaptor: instance of plexil.PlexilTreeAdaptor(id=588)

}

main[3] dump op2

 op2 = {

    tree: null

    org.antlr.runtime.tree.TreeRuleReturnScope.start: instance of plexil.LogicalOperatorNode(id=590)

}

main[3] 

Here's the ANTLR generated code in question. The throw happens in the line:

root_1 = (PlexilTreeNode)adaptor.becomeRoot(stream_op2.nextNode(), root_1);

As you can see in the jdb output above, op2 has no tree associated with it, so its associated RewriteRuleElementStream stream_op2 throws an exception when it tries to get the next node of the tree.

-- Chuck

// $ANTLR start "associativeReduction"

// antlr/PlexilTreeTransforms.g:112:1: associativeReduction : ^(op1= associativeOp ^(op2= associativeOp (rest+= . )+ ) arg3= . {...}?) -> ^( $op2 ( $rest)+ $arg3) ;

public final PlexilTreeTransforms.associativeReduction_return associativeReduction() throws RecognitionException {

PlexilTreeTransforms.associativeReduction_return retval = new PlexilTreeTransforms.associativeReduction_return();

retval.start = input.LT(1);

PlexilTreeNode root_0 = null;

PlexilTreeNode _first_0 = null;

PlexilTreeNode _last = null;

PlexilTreeNode arg3=null;

PlexilTreeNode rest=null;

List<Object> list_rest=null;

TreeRuleReturnScope op1 =null;

TreeRuleReturnScope op2 =null;

PlexilTreeNode arg3_tree=null;

PlexilTreeNode rest_tree=null;

RewriteRuleSubtreeStream stream_associativeOp=new RewriteRuleSubtreeStream(adaptor,"rule associativeOp");

try {

// antlr/PlexilTreeTransforms.g:112:21: ( ^(op1= associativeOp ^(op2= associativeOp (rest+= . )+ ) arg3= . {...}?) -> ^( $op2 ( $rest)+ $arg3) )

// antlr/PlexilTreeTransforms.g:122:8: ^(op1= associativeOp ^(op2= associativeOp (rest+= . )+ ) arg3= . {...}?)

{

_last = (PlexilTreeNode)input.LT(1);

{

PlexilTreeNode _save_last_1 = _last;

PlexilTreeNode _first_1 = null;

_last = (PlexilTreeNode)input.LT(1);

pushFollow(FOLLOW_associativeOp_in_associativeReduction302);

op1=associativeOp();

state._fsp--;

if (state.failed) return retval;

if ( state.backtracking==1 ) stream_associativeOp.add(op1.getTree());

if ( state.backtracking==1 )

if ( _first_0==null ) _first_0 = (PlexilTreeNode)op1.getTree();

match(input, Token.DOWN, null); if (state.failed) return retval;

_last = (PlexilTreeNode)input.LT(1);

{

PlexilTreeNode _save_last_2 = _last;

PlexilTreeNode _first_2 = null;

_last = (PlexilTreeNode)input.LT(1);

pushFollow(FOLLOW_associativeOp_in_associativeReduction307);

op2=associativeOp();

state._fsp--;

if (state.failed) return retval;

if ( state.backtracking==1 ) stream_associativeOp.add(op2.getTree());

if ( state.backtracking==1 )

if ( _first_1==null ) _first_1 = (PlexilTreeNode)op2.getTree();

match(input, Token.DOWN, null); if (state.failed) return retval;

// antlr/PlexilTreeTransforms.g:122:48: (rest+= . )+

int cnt2=0;

loop2:

while (true) {

int alt2=2;

int LA2_0 = input.LA(1);

if ( ((LA2_0 >= ABS_KYWD && LA2_0 <= XOR_KYWD)) ) {

alt2=1;

}

switch (alt2) {

case 1 :

// antlr/PlexilTreeTransforms.g:122:49: rest+= .

{

_last = (PlexilTreeNode)input.LT(1);

rest=(PlexilTreeNode)input.LT(1);

matchAny(input); if (state.failed) return retval;

 

if ( state.backtracking==1 )

if ( _first_2==null ) _first_2 = rest;

if (list_rest==null) list_rest=new ArrayList<Object>();

list_rest.add(rest);

if ( state.backtracking==1 ) {

retval.tree = _first_0;

if ( adaptor.getParent(retval.tree)!=null && adaptor.isNil( adaptor.getParent(retval.tree) ) )

retval.tree = (PlexilTreeNode)adaptor.getParent(retval.tree);

}

}

break;

default :

if ( cnt2 >= 1 ) break loop2;

if (state.backtracking>0) {state.failed=true; return retval;}

EarlyExitException eee = new EarlyExitException(2, input);

throw eee;

}

cnt2++;

}

match(input, Token.UP, null); if (state.failed) return retval;

_last = _save_last_2;

}

_last = (PlexilTreeNode)input.LT(1);

arg3=(PlexilTreeNode)input.LT(1);

matchAny(input); if (state.failed) return retval;

 

if ( state.backtracking==1 )

if ( _first_1==null ) _first_1 = arg3;

if ( !(((op1!=null?((PlexilTreeNode)op1.start):null).getType() == (op2!=null?((PlexilTreeNode)op2.start):null).getType())) ) {

if (state.backtracking>0) {state.failed=true; return retval;}

throw new FailedPredicateException(input, "associativeReduction", "$op1.start.getType() == $op2.start.getType()");

}

match(input, Token.UP, null); if (state.failed) return retval;

_last = _save_last_1;

}

// AST REWRITE

// elements: rest, op2, arg3

// token labels: 

// rule labels: op2, retval

// token list labels: 

// rule list labels: 

// wildcard labels: arg3, rest

if ( state.backtracking==1 ) {

retval.tree = root_0;

RewriteRuleSubtreeStream stream_arg3=new RewriteRuleSubtreeStream(adaptor,"wildcard arg3",arg3);

RewriteRuleSubtreeStream stream_rest=new RewriteRuleSubtreeStream(adaptor,"wildcard rest",list_rest);

RewriteRuleSubtreeStream stream_op2=new RewriteRuleSubtreeStream(adaptor,"rule op2",op2!=null?op2.getTree():null);

RewriteRuleSubtreeStream stream_retval=new RewriteRuleSubtreeStream(adaptor,"rule retval",retval!=null?retval.getTree():null);

root_0 = (PlexilTreeNode)adaptor.nil();

// 123:4: -> ^( $op2 ( $rest)+ $arg3)

{

// antlr/PlexilTreeTransforms.g:123:7: ^( $op2 ( $rest)+ $arg3)

{

PlexilTreeNode root_1 = (PlexilTreeNode)adaptor.nil();

root_1 = (PlexilTreeNode)adaptor.becomeRoot(stream_op2.nextNode(), root_1);

if ( !(stream_rest.hasNext()) ) {

throw new RewriteEarlyExitException();

}

while ( stream_rest.hasNext() ) {

adaptor.addChild(root_1, stream_rest.nextTree());

}

stream_rest.reset();

adaptor.addChild(root_1, stream_arg3.nextTree());

adaptor.addChild(root_0, root_1);

}

}

retval.tree = (PlexilTreeNode)adaptor.rulePostProcessing(root_0);

input.replaceChildren(adaptor.getParent(retval.start),

 adaptor.getChildIndex(retval.start),

 adaptor.getChildIndex(_last),

 retval.tree);

}

}

}

catch (RecognitionException re) {

reportError(re);

recover(input,re);

}

finally {

// do for sure before leaving

}

return retval;

}

// $ANTLR end "associativeReduction"

You received this message because you are subscribed to a topic in the Google Groups "antlr-discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/antlr-discussion/mb-cN77tgnM/unsubscribe.
To unsubscribe from this group and all its topics, send an email to antlr-discussi...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

Chuck Fry - chu...@chucko.com

Sent from my work laptop. Don't tell my boss!

[Chuck Fry]

This appears to me to be a bug in the code generation for the associativeOp rule. The rule and the Java code generated from it follow.

retval.tree is set from temporary variable _first_0. Unfortunately _first_0 is initialized to null and never set again.

retval.start is set to the token in question, but I have no way to get to it from an ANTLR rewrite rule.

-- Chuck

associativeOp:

        OR_KYWD

    |   AND_KYWD

    |   PLUS

    |   MINUS

    |   ASTERISK

    |   MAX_KYWD

    |   MIN_KYWD

    ;

public static class associativeOp_return extends TreeRuleReturnScope {

PlexilTreeNode tree;

@Override

public PlexilTreeNode getTree() { return tree; }

};

// $ANTLR start "associativeOp"

// antlr/PlexilTreeTransforms.g:149:1: associativeOp : ( OR_KYWD | AND_KYWD | PLUS | MINUS | ASTERISK | MAX_KYWD | MIN_KYWD );

public final PlexilTreeTransforms.associativeOp_return associativeOp() throws RecognitionException {

PlexilTreeTransforms.associativeOp_return retval = new PlexilTreeTransforms.associativeOp_return();

retval.start = input.LT(1);

PlexilTreeNode root_0 = null;

PlexilTreeNode _first_0 = null;

PlexilTreeNode _last = null;

PlexilTreeNode set15=null;

PlexilTreeNode set15_tree=null;

try {

// antlr/PlexilTreeTransforms.g:149:14: ( OR_KYWD | AND_KYWD | PLUS | MINUS | ASTERISK | MAX_KYWD | MIN_KYWD )

// antlr/PlexilTreeTransforms.g:

{

_last = (PlexilTreeNode)input.LT(1);

set15=(PlexilTreeNode)input.LT(1);

if ( input.LA(1)==AND_KYWD||input.LA(1)==ASTERISK||input.LA(1)==MAX_KYWD||(input.LA(1) >= MINUS && input.LA(1) <= MIN_KYWD)||input.LA(1)==OR_KYWD||input.LA(1)==PLUS ) {

input.consume();

state.errorRecovery=false;

state.failed=false;

}

else {

if (state.backtracking>0) {state.failed=true; return retval;}

MismatchedSetException mse = new MismatchedSetException(null,input);

throw mse;

}

if ( state.backtracking==1 ) {

retval.tree = _first_0;

if ( adaptor.getParent(retval.tree)!=null && adaptor.isNil( adaptor.getParent(retval.tree) ) )

retval.tree = (PlexilTreeNode)adaptor.getParent(retval.tree);

}

 

}

}

catch (RecognitionException re) {

reportError(re);

recover(input,re);

}

finally {

// do for sure before leaving

}

        // *** TEMP DEBUG ***

        System.out.println("associativeOp: result.tree class is " + retval.tree.getClass().getName());

return retval;

}

// $ANTLR end "associativeOp"