Using Tree Walker with Boolean checks + capturing the whole expression

Question

I have actually two questions that I hope can be answered as they are semi-dependent on my work. Below is the grammar + tree grammar + Java test file.

What I am actually trying to achieve is the following:

Question 1:

I have a grammar that parses my language correctly. I would like to do some semantic checks on variable declarations. So I created a tree walker and so far it semi works. My problem is it's not capturing the whole string of expression. For example,

float x = 10 + 10;

It is only capturing the first part, i.e. 10. I am not sure what I am doing wrong. If I did it in one pass, it works. Somehow, if I split the work into a grammar and tree grammar, it is not capturing the whole string.

Question 2:

I would like to do a check on a rule such that if my conditions returns true, I would like to remove that subtree. For example,

float x = 10;
float x; // <================ I would like this to be removed.

I have tried using rewrite rules but I think it is more complex than that.

Test.g:

grammar Test;
options {
  language = Java;
  output = AST;
}

parse : varDeclare+
      ;

varDeclare : type id equalExp? ';'
           ;

equalExp : ('=' (expression | '...'))
         ;

expression : binaryExpression
           ;

binaryExpression : addingExpression (('=='|'!='|'<='|'>='|'>'|'<') addingExpression)*
                 ;

addingExpression : multiplyingExpression (('+'|'-') multiplyingExpression)*
                 ;

multiplyingExpression : unaryExpression 
                        (('*'|'/') unaryExpression)*
                      ;

unaryExpression: ('!'|'-')* primitiveElement;   

primitiveElement : literalExpression
                 | id
                 | '(' expression ')'
                 ;  

literalExpression : INT
                  ;              

id : IDENTIFIER
   ;

type : 'int'    
     | 'float'
     ; 

// L E X I C A L   R U L E S      

INT : DIGITS ;   

IDENTIFIER : LETTER (LETTER | DIGIT)*;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) {$channel=HIDDEN;}
    ;

fragment LETTER : ('a'..'z' | 'A'..'Z' | '_') ;
fragment DIGITS: DIGIT+;
fragment DIGIT : '0'..'9';

TestTree.g:

tree grammar TestTree;

options {
  language = Java;
  tokenVocab = Test;
  ASTLabelType = CommonTree;
}

@members {
    SemanticCheck s;

    public TestTree(TreeNodeStream input, SemanticCheck s) {
        this(input);
        this.s = s;
    }

}

parse[SemanticCheck s]
      : varDeclare+
      ;

varDeclare : type id equalExp? ';'
           {s.check($type.name, $id.text, $equalExp.expr);}
           ;

equalExp returns [String expr]
         : ('=' (expression {$expr = $expression.e;} | '...' {$expr = "...";}))
         ;

expression returns [String e]
@after {$e = $expression.text;}
           : binaryExpression
           ;

binaryExpression : addingExpression (('=='|'!='|'<='|'>='|'>'|'<') addingExpression)*
                 ;

addingExpression : multiplyingExpression (('+'|'-') multiplyingExpression)*
                 ;

multiplyingExpression : unaryExpression 
                        (('*'|'/') unaryExpression)*
                      ;

unaryExpression: ('!'|'-')* primitiveElement;   

primitiveElement : literalExpression
                 | id
                 | '(' expression ')'
                 ;  

literalExpression : INT
                  ;              

id : IDENTIFIER
   ;

type returns [String name]
@after { $name = $type.text; }
     : 'int'    
     | 'float'
     ;

Java test file, Test.java:

import java.util.ArrayList;
import java.util.List;

import org.antlr.runtime.ANTLRStringStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.RuleReturnScope;
import org.antlr.runtime.tree.CommonTree;
import org.antlr.runtime.tree.CommonTreeNodeStream;

public class Test {
    public static void main(String[] args) throws Exception {
        SemanticCheck s = new SemanticCheck();

        String src = 
                "float x = 10+y; \n" + 
                "float x; \n";
        TestLexer lexer = new TestLexer(new ANTLRStringStream(src));
        //TestLexer lexer = new TestLexer(new ANTLRFileStream("input.txt"));
        CommonTokenStream tokenStream = new CommonTokenStream(lexer);
        TestParser parser = new TestParser(tokenStream);
        RuleReturnScope r = parser.parse();

        System.out.println("Parse Tree:\n" + tokenStream.toString());

        CommonTree t = (CommonTree)r.getTree();
        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        nodes.setTokenStream(tokenStream);

        TestTree walker = new TestTree(nodes, s);
        walker.parse(s);

    }
}

class SemanticCheck {
    List<String> names;

    public SemanticCheck() {
        this.names = new ArrayList<String>();

    }

    public boolean check(String type, String variableName, String exp) {
        System.out.println("Type: " + type + "  variableName: " + variableName + "  exp: " + exp);
        if(names.contains(variableName)) {
            System.out.println("Remove statement! Already defined!");
            return true;
        }

        names.add(variableName);
        return false;
    }
}

Thanks in advance!

I seem to understand where I went wrong and that I need to build a valid AST first before I do any tree grammar traversal. I will post an answer later on. In the meantime, How can one edit the "first" Tree that was created with the grammar with tree grammars? I don't want to pass an AST from tree grammar to the next. I hope that makes sense. — Andy M, Mar 28 '13 at 08:09
Figured the above comment as well. rewrite=true; in options will do what I want. — Andy M, Mar 28 '13 at 19:31

score 0 · Accepted Answer · edited May 23 '17 at 12:14

I figured out my problem and it turns out I needed to build an AST first before I can do anything. This would help in understanding what is a flat tree look like vs building an AST.

How to output the AST built using ANTLR?

Thanks to Bart's endless examples here in StackOverFlow, I was able to do semantic predicates to do what I needed in the example above.

Below is the updated code:

Test.g

 grammar Test;
    options {
      language = Java;
      output = AST;
    }
    tokens {
    VARDECL;
    Assign = '=';
    EqT    = '==';  
    NEq    = '!=';
    LT     = '<';
    LTEq   = '<=';
    GT     = '>';
    GTEq   = '>=';
    NOT    = '!';
    PLUS   = '+';
    MINUS  = '-';
    MULT   = '*';
    DIV    = '/';
    }

    parse : varDeclare+
          ;

    varDeclare : type id equalExp ';' -> ^(VARDECL type id equalExp)
               ;

    equalExp : (Assign^ (expression | '...' )) 
             ;

    expression : binaryExpression
               ;

    binaryExpression : addingExpression ((EqT|NEq|LTEq|GTEq|LT|GT)^ addingExpression)*
                     ;

    addingExpression : multiplyingExpression ((PLUS|MINUS)^ multiplyingExpression)*
                     ;

    multiplyingExpression : unaryExpression 
                            ((MULT|DIV)^ unaryExpression)*
                          ;

    unaryExpression: ((NOT|MINUS))^ primitiveElement
                   | primitiveElement
                   ;   

    primitiveElement : literalExpression
                     | id
                     | '(' expression ')' -> expression
                     ;  

    literalExpression : INT
                      ;              

    id : IDENTIFIER
       ;

    type : 'int'    
         | 'float'
         ; 

    // L E X I C A L   R U L E S      

    INT : DIGITS ;   

    IDENTIFIER : LETTER (LETTER | DIGIT)*;

    WS  :   ( ' '
            | '\t'
            | '\r'
            | '\n'
            ) {$channel=HIDDEN;}
        ;

    fragment LETTER : ('a'..'z' | 'A'..'Z' | '_') ;
    fragment DIGITS: DIGIT+;
    fragment DIGIT : '0'..'9';

This should automatically build an AST whenever you have varDeclare. Now on to the tree grammar/walker.

TestTree.g

tree grammar TestTree;

options {
  language = Java;
  tokenVocab = Test;
  ASTLabelType = CommonTree;
  output = AST;
}

tokens {
    REMOVED;
}

@members {
    SemanticCheck s;

    public TestTree(TreeNodeStream input, SemanticCheck s) {
        this(input);
        this.s = s;
    }

}

start[SemanticCheck s] : varDeclare+
      ;

varDeclare : ^(VARDECL type id equalExp)
            -> {s.check($type.text, $id.text, $equalExp.text)}? REMOVED
            -> ^(VARDECL type id equalExp)  
           ;

equalExp : ^(Assign expression)
         | ^(Assign '...')
         ;

expression : ^(('!') expression)
        | ^(('+'|'-'|'*'|'/') expression expression*)
        | ^(('=='|'<='|'<'|'>='|'>'|'!=') expression expression*)
        | literalExpression
       ;                                  

literalExpression : INT
                  | id
                  ;  

id : IDENTIFIER
   ;

type : 'int'    
     | 'float'
     ;

Now on to test it:

Test.java

import java.util.ArrayList;
import java.util.List;

import org.antlr.runtime.ANTLRStringStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.tree.*;

public class Test {
    public static void main(String[] args) throws Exception {
        SemanticCheck s = new SemanticCheck();

        String src = 
                "float x = 10; \n" + 
                "int x = 1; \n";
        TestLexer lexer = new TestLexer(new ANTLRStringStream(src));
        CommonTokenStream tokenStream = new CommonTokenStream(lexer);
        TestParser parser = new TestParser(tokenStream);
        TestParser.parse_return r = parser.parse();
        System.out.println("Tree:" + ((Tree)r.tree).toStringTree() + "\n");

        CommonTreeNodeStream nodes = new CommonTreeNodeStream((Tree)r.tree);
        nodes.setTokenStream(tokenStream);
        TestTree walker = new TestTree(nodes, s);
        TestTree.start_return r2 = walker.start(s);
        System.out.println("\nTree Walker: "+((Tree)r2.tree).toStringTree());

    }
}

class SemanticCheck {
    List<String> names;

    public SemanticCheck() {
        this.names = new ArrayList<String>();

    }

    public boolean check(String type, String variableName, String exp) {
        System.out.println("Type: " + type + "  variableName: " + variableName + "  exp: " + exp);
        if(names.contains(variableName)) {
            return true;
        }

        names.add(variableName);
        return false;
    }
}

Output:

Tree:(VARDECL float x (= 10)) (VARDECL int x (= 1))

Type: float  variableName: x  exp: = 10
Type: int  variableName: x  exp: = 1

Tree Walker: (VARDECL float x (= 10)) REMOVED

Hope this helps! Please feel free to point any errors if I did something wrong.

Using Tree Walker with Boolean checks + capturing the whole expression

1 Answers1