Parse Tree API

/**
 * Base interface for all parse tree nodes
 */
public interface ParseTree extends SyntaxTree {
    /** Get parent node */
    ParseTree getParent();
    
    /** Get child node at index */
    ParseTree getChild(int i);
    
    /** Get number of children */
    int getChildCount();
    
    /** Accept visitor for tree traversal */
    <T> T accept(ParseTreeVisitor<? extends T> visitor);
    
    /** Get text representation of subtree */
    String getText();
    
    /** Get text with spaces between tokens */
    String toStringTree();
    
    /** Get source interval for this node */
    Interval getSourceInterval();
}

/**
 * Parse tree node representing parser rule invocation
 */
public interface RuleNode extends ParseTree {
    /** Get rule context for this node */
    RuleContext getRuleContext();
}

/**
 * Parse tree leaf node representing terminal/token
 */
public interface TerminalNode extends ParseTree {
    /** Get token for this terminal node */
    Token getSymbol();
}

/**
 * Parse tree node representing syntax error
 */
public interface ErrorNode extends TerminalNode {
    // Inherits from TerminalNode
}

/**
 * Parse tree node for parser rules with context information
 */
public class ParserRuleContext extends RuleContext implements RuleNode {
    /** Parent context */
    public ParserRuleContext parent;
    
    /** State when rule was invoked */
    public int invokingState;
    
    /** List of child nodes */
    public List<ParseTree> children;
    
    /** Start token for this rule */
    public Token start;
    
    /** Stop token for this rule */
    public Token stop;
    
    /** Exception that caused rule to exit */
    public RecognitionException exception;
    
    /** Add terminal child node */
    public void addChild(TerminalNode t);
    
    /** Add rule child node */
    public void addChild(RuleContext ruleInvocation);
    
    /** Remove last child */
    public void removeLastChild();
    
    /** Add error node child */
    public void addErrorNode(ErrorNode errorNode);
    
    /** Add child at specific index */
    public void addChild(int index, ParseTree child);
    
    /** Get child of specific type */
    public <T extends ParseTree> T getChild(Class<T> ctxType, int i);
    
    /** Get terminal child */
    public TerminalNode getToken(int ttype, int i);
    
    /** Get all terminal children of type */
    public List<TerminalNode> getTokens(int ttype);
    
    /** Get rule child by type */
    public <T extends ParserRuleContext> T getRuleContext(Class<T> ctxType, int i);
    
    /** Get all rule children of type */
    public <T extends ParserRuleContext> List<T> getRuleContexts(Class<T> ctxType);
    
    /** Accept visitor */
    @Override
    public <T> T accept(ParseTreeVisitor<? extends T> visitor);
    
    /** Get text from start to stop token */
    @Override
    public String getText();
    
    /** Convert subtree to string with parser info */
    public String toStringTree(Parser parser);
    
    /** Convert subtree to string with rule names */
    public String toStringTree(List<String> ruleNames);
    
    /** Get source interval */
    @Override
    public Interval getSourceInterval();
}

/**
 * Base class for rule contexts
 */
public class RuleContext {
    /** Parent rule context */
    public RuleContext parent;
    
    /** Invoking state */
    public int invokingState;
    
    /** Calculate depth in parse tree */
    public int depth();
    
    /** Check if context is empty */
    public boolean isEmpty();
    
    /** Get source interval */
    public Interval getSourceInterval();
    
    /** Get rule index */
    public int getRuleIndex();
    
    /** Get invoking state */
    public int getInvokingState();
    
    /** Set invoking state */
    public void setInvokingState(int invokingState);
    
    /** Set parent context */
    public void setParent(RuleContext parent);
    
    /** Get parent context */
    public RuleContext getParent();
    
    /** Get payload (returns this) */
    public RuleContext getPayload();
    
    /** Get text representation */
    public String getText();
    
    /** Convert to string tree */
    public String toStringTree();
}

/**
 * Visitor pattern interface for parse tree traversal
 */
public interface ParseTreeVisitor<T> {
    /** Visit parse tree node and return result */
    T visit(ParseTree tree);
    
    /** Visit all children of rule node */
    T visitChildren(RuleNode node);
    
    /** Visit terminal node */
    T visitTerminal(TerminalNode node);
    
    /** Visit error node */
    T visitErrorNode(ErrorNode node);
}

/**
 * Base implementation of visitor pattern with default behavior
 */
public abstract class AbstractParseTreeVisitor<T> implements ParseTreeVisitor<T> {
    /** Visit tree node, delegating to appropriate method */
    @Override
    public T visit(ParseTree tree) {
        return tree.accept(this);
    }
    
    /** Visit all children and return result of last non-null visit */
    @Override
    public T visitChildren(RuleNode node) {
        T result = defaultResult();
        int n = node.getChildCount();
        for (int i = 0; i < n; i++) {
            if (!shouldVisitNextChild(node, result)) {
                break;
            }
            
            ParseTree c = node.getChild(i);
            T childResult = c.accept(this);
            result = aggregateResult(result, childResult);
        }
        return result;
    }
    
    /** Visit terminal node (default returns defaultResult()) */
    @Override
    public T visitTerminal(TerminalNode node) {
        return defaultResult();
    }
    
    /** Visit error node (default returns defaultResult()) */
    @Override
    public T visitErrorNode(ErrorNode node) {
        return defaultResult();
    }
    
    /** Default result value */
    protected T defaultResult() {
        return null;
    }
    
    /** Aggregate results from multiple children */
    protected T aggregateResult(T aggregate, T nextResult) {
        return nextResult;
    }
    
    /** Determine if should visit next child */
    protected boolean shouldVisitNextChild(RuleNode node, T currentResult) {
        return true;
    }
}

import org.antlr.v4.runtime.tree.*;

// Custom visitor implementation
public class MyVisitor extends MyBaseVisitor<String> {
    @Override
    public String visitExpr(MyParser.ExprContext ctx) {
        if (ctx.getChildCount() == 3) {
            String left = visit(ctx.getChild(0));
            String op = ctx.getChild(1).getText();
            String right = visit(ctx.getChild(2));
            return "(" + left + " " + op + " " + right + ")";
        }
        return visitChildren(ctx);
    }
    
    @Override
    public String visitTerminal(TerminalNode node) {
        return node.getText();
    }
}

// Use visitor
ParseTree tree = parser.expr();
MyVisitor visitor = new MyVisitor();
String result = visitor.visit(tree);

/**
 * Listener pattern interface for parse tree events
 */
public interface ParseTreeListener {
    /** Called when entering any rule */
    void enterEveryRule(ParserRuleContext ctx);
    
    /** Called when exiting any rule */
    void exitEveryRule(ParserRuleContext ctx);
    
    /** Called when visiting terminal node */
    void visitTerminal(TerminalNode node);
    
    /** Called when visiting error node */
    void visitErrorNode(ErrorNode node);
}

/**
 * Tree walker utility for traversing parse trees with listeners
 */
public class ParseTreeWalker {
    /** Default walker instance */
    public static final ParseTreeWalker DEFAULT = new ParseTreeWalker();
    
    /** Walk tree with listener, calling enter/exit methods */
    public void walk(ParseTreeListener listener, ParseTree t) {
        if (t instanceof ErrorNode) {
            listener.visitErrorNode((ErrorNode) t);
            return;
        } else if (t instanceof TerminalNode) {
            listener.visitTerminal((TerminalNode) t);
            return;
        }
        
        RuleNode r = (RuleNode) t;
        ParserRuleContext ctx = (ParserRuleContext) r.getRuleContext();
        
        enterRule(listener, r);
        
        for (int i = 0; i < t.getChildCount(); i++) {
            walk(listener, t.getChild(i));
        }
        
        exitRule(listener, r);
    }
    
    /** Enter rule node */
    protected void enterRule(ParseTreeListener listener, RuleNode r) {
        ParserRuleContext ctx = (ParserRuleContext) r.getRuleContext();
        listener.enterEveryRule(ctx);
        ctx.enterRule(listener);
    }
    
    /** Exit rule node */
    protected void exitRule(ParseTreeListener listener, RuleNode r) {
        ParserRuleContext ctx = (ParserRuleContext) r.getRuleContext();
        ctx.exitRule(listener);
        listener.exitEveryRule(ctx);
    }
}

import org.antlr.v4.runtime.tree.*;

// Custom listener implementation
public class MyListener extends MyBaseListener {
    @Override
    public void enterExpr(MyParser.ExprContext ctx) {
        System.out.println("Entering expression: " + ctx.getText());
    }
    
    @Override
    public void exitExpr(MyParser.ExprContext ctx) {
        System.out.println("Exiting expression: " + ctx.getText());
    }
    
    @Override
    public void visitTerminal(TerminalNode node) {
        System.out.println("Terminal: " + node.getText());
    }
}

// Use listener
ParseTree tree = parser.expr();
ParseTreeWalker walker = new ParseTreeWalker();
MyListener listener = new MyListener();
walker.walk(listener, tree);

/**
 * Static utility methods for parse trees
 */
public class Trees {
    /** Convert tree to string representation */
    public static String toStringTree(ParseTree t);
    
    /** Convert tree to string using parser */
    public static String toStringTree(ParseTree t, Parser parser);
    
    /** Convert tree to string using rule names */
    public static String toStringTree(ParseTree t, List<String> ruleNames);
    
    /** Get all children of a parse tree node */
    public static List<ParseTree> getChildren(ParseTree t);
    
    /** Get all ancestors of a parse tree node */
    public static List<ParseTree> getAncestors(ParseTree t);
    
    /** Find all nodes with specified token type */
    public static Collection<ParseTree> findAllTokenNodes(ParseTree t, int ttype);
    
    /** Find all nodes with specified rule index */
    public static Collection<ParseTree> findAllRuleNodes(ParseTree t, int ruleIndex);
    
    /** Find all descendant nodes with specified rule index */
    public static Collection<ParseTree> descendants(ParseTree t);
    
    /** Get node ancestors up to specified rule type */
    public static ParserRuleContext getAncestorOfType(ParserRuleContext ctx, Class<? extends ParserRuleContext> ruleType);
    
    /** Strip parse tree to text only */
    public static String stripParseTree(ParseTree t);
}

/**
 * Associate arbitrary data with parse tree nodes
 */
public class ParseTreeProperty<V> {
    /** Associate value with parse tree node */
    public V put(ParseTree node, V value);
    
    /** Get value associated with parse tree node */
    public V get(ParseTree node);
    
    /** Remove association for parse tree node */
    public V removeFrom(ParseTree node);
}

import org.antlr.v4.runtime.tree.*;

// Create property map
ParseTreeProperty<String> nodeTypes = new ParseTreeProperty<>();

// Associate data with nodes
nodeTypes.put(exprNode, "arithmetic");
nodeTypes.put(termNode, "operand");

// Retrieve data
String type = nodeTypes.get(exprNode); // "arithmetic"

/**
 * XPath-like querying of parse trees
 */
public class XPath {
    /** Find all nodes matching XPath expression */
    public static Collection<ParseTree> findAll(ParseTree tree, String xpath, Parser parser);
    
    /** Compile XPath expression */
    public static XPathElement[] split(String path);
}

import org.antlr.v4.runtime.tree.xpath.XPath;

// Find all identifier nodes
Collection<ParseTree> ids = XPath.findAll(tree, "//ID", parser);

// Find specific rule contexts
Collection<ParseTree> exprs = XPath.findAll(tree, "//expr", parser);

// Complex path
Collection<ParseTree> nodes = XPath.findAll(tree, "//expr/*/ID", parser);

import org.antlr.v4.runtime.tree.*;

// Parse and get tree
ParseTree tree = parser.startRule();

// Simple visitor
MyVisitor visitor = new MyVisitor();
String result = visitor.visit(tree);

// Simple listener
ParseTreeWalker walker = new ParseTreeWalker();
MyListener listener = new MyListener();
walker.walk(listener, tree);

import org.antlr.v4.runtime.tree.*;

// Analyze tree structure
List<ParseTree> children = Trees.getChildren(tree);
List<ParseTree> ancestors = Trees.getAncestors(someNode);

// Find specific nodes
Collection<ParseTree> identifiers = Trees.findAllTokenNodes(tree, MyLexer.ID);
Collection<ParseTree> expressions = Trees.findAllRuleNodes(tree, MyParser.RULE_expr);

// Convert to string
String treeString = Trees.toStringTree(tree, parser);
System.out.println(treeString);

import org.antlr.v4.runtime.tree.*;

// Associate metadata with nodes
ParseTreeProperty<Integer> depths = new ParseTreeProperty<>();
ParseTreeProperty<String> nodeLabels = new ParseTreeProperty<>();

// Visitor that computes and stores depth
public class DepthVisitor extends MyBaseVisitor<Integer> {
    @Override
    public Integer visitExpr(MyParser.ExprContext ctx) {
        int maxChildDepth = 0;
        for (int i = 0; i < ctx.getChildCount(); i++) {
            Integer childDepth = visit(ctx.getChild(i));
            if (childDepth != null && childDepth > maxChildDepth) {
                maxChildDepth = childDepth;
            }
        }
        int thisDepth = maxChildDepth + 1;
        depths.put(ctx, thisDepth);
        return thisDepth;
    }
    
    @Override
    public Integer visitTerminal(TerminalNode node) {
        depths.put(node, 0);
        return 0;
    }
}

// Use visitor and check results
DepthVisitor depthVisitor = new DepthVisitor();
depthVisitor.visit(tree);

Integer rootDepth = depths.get(tree);
System.out.println("Tree depth: " + rootDepth);