Utilities

/**
 * 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 for rule names */
    public static String toStringTree(ParseTree t, Parser parser);
    
    /** Convert tree to string using rule names list */
    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 up to root */
    public static List<ParseTree> getAncestors(ParseTree t);
    
    /** Find all descendant nodes with specified token type */
    public static Collection<ParseTree> findAllTokenNodes(ParseTree t, int ttype);
    
    /** Find all descendant nodes with specified rule index */
    public static Collection<ParseTree> findAllRuleNodes(ParseTree t, int ruleIndex);
    
    /** Get all descendant nodes */
    public static List<ParseTree> descendants(ParseTree t);
    
    /** Get ancestor of specified rule type */
    public static ParserRuleContext getAncestorOfType(ParserRuleContext ctx, 
                                                     Class<? extends ParserRuleContext> ruleType);
    
    /** Strip parse tree to text content only */
    public static String stripParseTree(ParseTree t);
    
    /** Get node depth in tree */
    public static int getNodeDepth(ParseTree tree, ParseTree node);
    
    /** Check if one node is ancestor of another */
    public static boolean isAncestorOf(ParseTree ancestor, ParseTree node);
}

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

// Parse tree to string
ParseTree tree = parser.expr();
String treeString = Trees.toStringTree(tree);
System.out.println("Parse tree: " + treeString);

// With parser for better formatting
String formattedTree = Trees.toStringTree(tree, parser);
System.out.println("Formatted: " + formattedTree);

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

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

// Text extraction
String textOnly = Trees.stripParseTree(tree);

/**
 * Associate arbitrary data with parse tree nodes
 */
public class ParseTreeProperty<V> {
    /** Internal map for storing associations */
    protected Map<ParseTree, V> annotations = new IdentityHashMap<>();
    
    /** Associate value with parse tree node */
    public V put(ParseTree node, V value) {
        return annotations.put(node, value);
    }
    
    /** Get value associated with parse tree node */
    public V get(ParseTree node) {
        return annotations.get(node);
    }
    
    /** Remove association for parse tree node */
    public V removeFrom(ParseTree node) {
        return annotations.remove(node);
    }
    
    /** Clear all associations */
    public void clear() {
        annotations.clear();
    }
    
    /** Check if node has associated value */
    public boolean containsKey(ParseTree node) {
        return annotations.containsKey(node);
    }
    
    /** Get all nodes with associations */
    public Set<ParseTree> keySet() {
        return annotations.keySet();
    }
    
    /** Get all associated values */
    public Collection<V> values() {
        return annotations.values();
    }
}

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

// Create property maps
ParseTreeProperty<String> nodeTypes = new ParseTreeProperty<>();
ParseTreeProperty<Integer> nodeDepths = new ParseTreeProperty<>();
ParseTreeProperty<List<String>> nodeAttributes = new ParseTreeProperty<>();

// Associate data during tree walk
ParseTreeWalker walker = new ParseTreeWalker();
walker.walk(new MyBaseListener() {
    @Override
    public void enterExpr(MyParser.ExprContext ctx) {
        nodeTypes.put(ctx, "expression");
        nodeDepths.put(ctx, getDepth(ctx));
        
        List<String> attrs = new ArrayList<>();
        attrs.add("evaluated");
        nodeAttributes.put(ctx, attrs);
    }
}, tree);

// Use associations later
String type = nodeTypes.get(exprNode);
Integer depth = nodeDepths.get(exprNode);
List<String> attrs = nodeAttributes.get(exprNode);

/**
 * Set of integer intervals for efficient range operations
 */
public class IntervalSet implements IntSet {
    /** Create empty interval set */
    public IntervalSet();
    
    /** Create interval set from single interval */
    public IntervalSet(int a, int b);
    
    /** Create interval set from list of intervals */
    public IntervalSet(List<Interval> intervals);
    
    /** Add single integer to set */
    public void add(int el);
    
    /** Add range of integers to set */
    public void add(int a, int b);
    
    /** Add interval to set */
    public IntervalSet addAll(IntSet set);
    
    /** Get complement of this set */
    public IntervalSet complement(IntSet vocabulary);
    
    /** Subtract set from this set */
    public IntervalSet subtract(IntSet a);
    
    /** Get intersection with another set */
    public IntervalSet and(IntSet other);
    
    /** Get union with another set */
    public IntervalSet or(IntSet a);
    
    /** Check if contains element */
    public boolean contains(int el);
    
    /** Check if set is empty */
    public boolean isNil();
    
    /** Get size of set */
    public int size();
    
    /** Get minimum element */
    public int getMinElement();
    
    /** Get maximum element */
    public int getMaxElement();
    
    /** Convert to integer list */
    public List<Integer> toList();
    
    /** Convert to string with vocabulary */
    public String toString(Vocabulary vocabulary);
}

/**
 * Integer interval [a,b] 
 */
public class Interval {
    /** Start of interval (inclusive) */
    public int a;
    
    /** End of interval (inclusive) */
    public int b;
    
    /** Create interval */
    public Interval(int a, int b);
    
    /** Check if contains value */
    public boolean contains(int item);
    
    /** Get length of interval */
    public int length();
    
    /** Check if intervals overlap */
    public boolean intersects(Interval other);
    
    /** Get intersection with another interval */
    public Interval intersection(Interval other);
    
    /** Get union with another interval */
    public Interval union(Interval other);
}

/**
 * Resizable integer array with efficient operations
 */
public class IntegerList {
    /** Create empty list */
    public IntegerList();
    
    /** Create list with initial capacity */
    public IntegerList(int capacity);
    
    /** Create list from array */
    public IntegerList(int[] list);
    
    /** Add integer to end */
    public void add(int value);
    
    /** Add all integers from another list */
    public void addAll(int[] array);
    
    /** Get integer at index */
    public int get(int index);
    
    /** Check if contains value */
    public boolean contains(int value);
    
    /** Set value at index */
    public int set(int index, int value);
    
    /** Remove value at index */
    public int removeAt(int index);
    
    /** Remove first occurrence of value */
    public boolean removeValue(int value);
    
    /** Get size */
    public int size();
    
    /** Check if empty */
    public boolean isEmpty();
    
    /** Clear all elements */
    public void clear();
    
    /** Convert to array */
    public int[] toArray();
    
    /** Sort elements */
    public void sort();
    
    /** Binary search for value */
    public int binarySearch(int value);
}

/**
 * Generic pair of two values
 */
public class Pair<A, B> {
    /** First value */
    public final A a;
    
    /** Second value */
    public final B b;
    
    /** Create pair */
    public Pair(A a, B b);
    
    /** Get first value */
    public A getFirst();
    
    /** Get second value */
    public B getSecond();
    
    @Override
    public boolean equals(Object obj);
    
    @Override
    public int hashCode();
    
    @Override
    public String toString();
}

/**
 * Generic triple of three values
 */
public class Triple<A, B, C> {
    /** First value */
    public final A a;
    
    /** Second value */
    public final B b;
    
    /** Third value */
    public final C c;
    
    /** Create triple */
    public Triple(A a, B b, C c);
    
    @Override
    public boolean equals(Object obj);
    
    @Override
    public int hashCode();
    
    @Override
    public String toString();
}

/**
 * Map with two keys mapping to single value
 */
public class DoubleKeyMap<K1, K2, V> {
    /** Internal storage */
    protected Map<K1, Map<K2, V>> data = new HashMap<>();
    
    /** Put value with two keys */
    public V put(K1 k1, K2 k2, V v);
    
    /** Get value by two keys */
    public V get(K1 k1, K2 k2);
    
    /** Remove value by two keys */
    public V remove(K1 k1, K2 k2);
    
    /** Get all values for first key */
    public Map<K2, V> get(K1 k1);
    
    /** Get all first-level keys */
    public Set<K1> keySet();
    
    /** Get all values */
    public Collection<V> values();
}

/**
 * Map where each key can have multiple values
 */
public class MultiMap<K, V> {
    /** Internal storage */
    protected Map<K, List<V>> data = new HashMap<>();
    
    /** Add value to key */
    public void map(K key, V value);
    
    /** Get list of values for key */
    public List<V> get(K key);
    
    /** Get all keys */
    public Set<K> keySet();
    
    /** Get all value lists */
    public Collection<List<V>> values();
    
    /** Check if key has any values */
    public boolean containsKey(K key);
    
    /** Remove all values for key */
    public List<V> remove(K key);
    
    /** Remove specific value from key */
    public boolean remove(K key, V value);
    
    /** Get size (total number of key-value pairs) */
    public int size();
}

/**
 * Command-line tool for testing grammars (grun command)
 */
public class TestRig {
    /** Main entry point for grammar testing */
    public static void main(String[] args) throws Exception;
    
    /** Process input with specified grammar and rule */
    public void process(String grammarName, String startRuleName, 
                       InputStream is, boolean printTree) throws Exception;
}

# Test grammar interactively
grun MyGrammar expr -tree
# Type input, press Ctrl+D (Unix) or Ctrl+Z (Windows)

# Test with file input
grun MyGrammar expr -tree input.txt

# Show tokens only
grun MyGrammar expr -tokens input.txt

# Show GUI tree viewer
grun MyGrammar expr -gui input.txt

/**
 * General utility methods
 */
public class Utils {
    /** Join array elements with separator */
    public static String join(Object[] array, String separator);
    
    /** Join iterable elements with separator */
    public static String join(Iterable<?> iter, String separator);
    
    /** Escape string for display */
    public static String escapeWhitespace(String s, boolean escapeSpaces);
    
    /** Write object to file */
    public static void writeFile(String fileName, String content);
    
    /** Read file to string */
    public static String readFile(String fileName) throws IOException;
    
    /** Convert integer to hex string */
    public static String hex(int value);
    
    /** Convert character to escaped string */
    public static String escapeChar(int c);
    
    /** Check if character is printable */
    public static boolean isPrintable(int c);
    
    /** Get platform-specific line separator */
    public static String getLineSeparator();
}

/**
 * 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 into elements */
    public static XPathElement[] split(String path);
}

/**
 * Base class for XPath elements
 */
public abstract class XPathElement {
    /** Node name being matched */
    protected String nodeName;
    
    /** Whether this element inverts the match */
    protected boolean invert;
    
    /** Evaluate element against parse tree node */
    public abstract Collection<ParseTree> evaluate(ParseTree t);
}

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

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

// Find ID tokens under expr rules
Collection<ParseTree> exprIds = XPath.findAll(tree, "//expr//ID", parser);

// Find direct children
Collection<ParseTree> directIds = XPath.findAll(tree, "/expr/ID", parser);

// Find any nodes with specific text
Collection<ParseTree> plusNodes = XPath.findAll(tree, "//'+'", parser);

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

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

// Multi-pass analysis using properties
ParseTreeProperty<String> nodeTypes = new ParseTreeProperty<>();
ParseTreeProperty<Integer> exprValues = new ParseTreeProperty<>();
ParseTreeProperty<Set<String>> usedVariables = new ParseTreeProperty<>();

// First pass: classify nodes
ParseTreeWalker walker = new ParseTreeWalker();
walker.walk(new MyBaseListener() {
    @Override
    public void enterExpr(MyParser.ExprContext ctx) {
        if (ctx.getChildCount() == 3) {
            nodeTypes.put(ctx, "binary_op");
        } else if (ctx.getChildCount() == 1) {
            nodeTypes.put(ctx, "primary");
        }
    }
}, tree);

// Second pass: compute values
MyVisitor<Integer> calculator = new MyBaseVisitor<Integer>() {
    @Override
    public Integer visitExpr(MyParser.ExprContext ctx) {
        Integer result = visitChildren(ctx);
        if (result != null) {
            exprValues.put(ctx, result);
        }
        return result;
    }
};
calculator.visit(tree);

// Query results
for (ParseTree node : nodeTypes.keySet()) {
    String type = nodeTypes.get(node);
    Integer value = exprValues.get(node);
    System.out.println("Node type: " + type + ", value: " + value);
}

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

// Find patterns using XPath
Collection<ParseTree> assignments = XPath.findAll(tree, "//assignment", parser);
Collection<ParseTree> functionCalls = XPath.findAll(tree, "//functionCall", parser);
Collection<ParseTree> identifiers = XPath.findAll(tree, "//ID", parser);

// Complex analysis
for (ParseTree assignment : assignments) {
    // Find all identifiers in this assignment
    Collection<ParseTree> assignmentIds = XPath.findAll(assignment, ".//ID", parser);
    
    // Get assignment target (first identifier)
    List<ParseTree> children = Trees.getChildren(assignment);
    if (!children.isEmpty() && children.get(0) instanceof TerminalNode) {
        TerminalNode target = (TerminalNode) children.get(0);
        System.out.println("Assignment to: " + target.getText());
    }
}

// Tree structure analysis
List<ParseTree> allNodes = Trees.descendants(tree);
System.out.println("Total nodes: " + allNodes.size());

// Find deepest node
int maxDepth = 0;
ParseTree deepestNode = null;
for (ParseTree node : allNodes) {
    int depth = Trees.getNodeDepth(tree, node);
    if (depth > maxDepth) {
        maxDepth = depth;
        deepestNode = node;
    }
}
System.out.println("Deepest node at depth " + maxDepth + ": " + deepestNode.getText());

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

// Interval set for token types
IntervalSet keywords = new IntervalSet();
keywords.add(MyLexer.IF);
keywords.add(MyLexer.ELSE);
keywords.add(MyLexer.WHILE);
keywords.add(MyLexer.FOR);

// Check token types
if (keywords.contains(token.getType())) {
    System.out.println("Found keyword: " + token.getText());
}

// Integer list for positions
IntegerList errorPositions = new IntegerList();
errorPositions.add(10);
errorPositions.add(25);
errorPositions.add(42);

// Double key map for symbol table
DoubleKeyMap<String, String, String> symbolTable = new DoubleKeyMap<>();
symbolTable.put("function", "main", "int");
symbolTable.put("variable", "x", "double");

String mainType = symbolTable.get("function", "main"); // "int"

// Multi-map for dependencies
MultiMap<String, String> dependencies = new MultiMap<>();
dependencies.map("Parser.java", "Lexer.java");
dependencies.map("Parser.java", "Tree.java");
dependencies.map("Main.java", "Parser.java");

List<String> parserDeps = dependencies.get("Parser.java");
// ["Lexer.java", "Tree.java"]