0
# Utilities
1

2
ANTLR4 provides various utility classes and helpers for tree manipulation, data structures, testing infrastructure, and common operations.
3

4
## Capabilities
5

6
### Tree Utilities
7

8
Static utility methods for common parse tree operations and analysis.
9

10
```java { .api }
11
/**
12
 * Static utility methods for parse trees
13
 */
14
public class Trees {
15
    /** Convert tree to string representation */
16
    public static String toStringTree(ParseTree t);
17
    
18
    /** Convert tree to string using parser for rule names */
19
    public static String toStringTree(ParseTree t, Parser parser);
20
    
21
    /** Convert tree to string using rule names list */
22
    public static String toStringTree(ParseTree t, List<String> ruleNames);
23
    
24
    /** Get all children of a parse tree node */
25
    public static List<ParseTree> getChildren(ParseTree t);
26
    
27
    /** Get all ancestors of a parse tree node up to root */
28
    public static List<ParseTree> getAncestors(ParseTree t);
29
    
30
    /** Find all descendant nodes with specified token type */
31
    public static Collection<ParseTree> findAllTokenNodes(ParseTree t, int ttype);
32
    
33
    /** Find all descendant nodes with specified rule index */
34
    public static Collection<ParseTree> findAllRuleNodes(ParseTree t, int ruleIndex);
35
    
36
    /** Get all descendant nodes */
37
    public static List<ParseTree> descendants(ParseTree t);
38
    
39
    /** Get ancestor of specified rule type */
40
    public static ParserRuleContext getAncestorOfType(ParserRuleContext ctx, 
41
                                                     Class<? extends ParserRuleContext> ruleType);
42
    
43
    /** Strip parse tree to text content only */
44
    public static String stripParseTree(ParseTree t);
45
    
46
    /** Get node depth in tree */
47
    public static int getNodeDepth(ParseTree tree, ParseTree node);
48
    
49
    /** Check if one node is ancestor of another */
50
    public static boolean isAncestorOf(ParseTree ancestor, ParseTree node);
51
}
52
```
53

54
**Usage Examples:**
55

56
```java
57
import org.antlr.v4.runtime.tree.*;
58

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

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

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

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

76
// Text extraction
77
String textOnly = Trees.stripParseTree(tree);
78
```
79

80
### Parse Tree Properties
81

82
Associate arbitrary data with parse tree nodes using a map-like interface.
83

84
```java { .api }
85
/**
86
 * Associate arbitrary data with parse tree nodes
87
 */
88
public class ParseTreeProperty<V> {
89
    /** Internal map for storing associations */
90
    protected Map<ParseTree, V> annotations = new IdentityHashMap<>();
91
    
92
    /** Associate value with parse tree node */
93
    public V put(ParseTree node, V value) {
94
        return annotations.put(node, value);
95
    }
96
    
97
    /** Get value associated with parse tree node */
98
    public V get(ParseTree node) {
99
        return annotations.get(node);
100
    }
101
    
102
    /** Remove association for parse tree node */
103
    public V removeFrom(ParseTree node) {
104
        return annotations.remove(node);
105
    }
106
    
107
    /** Clear all associations */
108
    public void clear() {
109
        annotations.clear();
110
    }
111
    
112
    /** Check if node has associated value */
113
    public boolean containsKey(ParseTree node) {
114
        return annotations.containsKey(node);
115
    }
116
    
117
    /** Get all nodes with associations */
118
    public Set<ParseTree> keySet() {
119
        return annotations.keySet();
120
    }
121
    
122
    /** Get all associated values */
123
    public Collection<V> values() {
124
        return annotations.values();
125
    }
126
}
127
```
128

129
**Usage Example:**
130

131
```java
132
import org.antlr.v4.runtime.tree.*;
133

134
// Create property maps
135
ParseTreeProperty<String> nodeTypes = new ParseTreeProperty<>();
136
ParseTreeProperty<Integer> nodeDepths = new ParseTreeProperty<>();
137
ParseTreeProperty<List<String>> nodeAttributes = new ParseTreeProperty<>();
138

139
// Associate data during tree walk
140
ParseTreeWalker walker = new ParseTreeWalker();
141
walker.walk(new MyBaseListener() {
142
    @Override
143
    public void enterExpr(MyParser.ExprContext ctx) {
144
        nodeTypes.put(ctx, "expression");
145
        nodeDepths.put(ctx, getDepth(ctx));
146
        
147
        List<String> attrs = new ArrayList<>();
148
        attrs.add("evaluated");
149
        nodeAttributes.put(ctx, attrs);
150
    }
151
}, tree);
152

153
// Use associations later
154
String type = nodeTypes.get(exprNode);
155
Integer depth = nodeDepths.get(exprNode);
156
List<String> attrs = nodeAttributes.get(exprNode);
157
```
158

159
### Data Structures
160

161
Efficient data structures used internally by ANTLR and available for use.
162

163
```java { .api }
164
/**
165
 * Set of integer intervals for efficient range operations
166
 */
167
public class IntervalSet implements IntSet {
168
    /** Create empty interval set */
169
    public IntervalSet();
170
    
171
    /** Create interval set from single interval */
172
    public IntervalSet(int a, int b);
173
    
174
    /** Create interval set from list of intervals */
175
    public IntervalSet(List<Interval> intervals);
176
    
177
    /** Add single integer to set */
178
    public void add(int el);
179
    
180
    /** Add range of integers to set */
181
    public void add(int a, int b);
182
    
183
    /** Add interval to set */
184
    public IntervalSet addAll(IntSet set);
185
    
186
    /** Get complement of this set */
187
    public IntervalSet complement(IntSet vocabulary);
188
    
189
    /** Subtract set from this set */
190
    public IntervalSet subtract(IntSet a);
191
    
192
    /** Get intersection with another set */
193
    public IntervalSet and(IntSet other);
194
    
195
    /** Get union with another set */
196
    public IntervalSet or(IntSet a);
197
    
198
    /** Check if contains element */
199
    public boolean contains(int el);
200
    
201
    /** Check if set is empty */
202
    public boolean isNil();
203
    
204
    /** Get size of set */
205
    public int size();
206
    
207
    /** Get minimum element */
208
    public int getMinElement();
209
    
210
    /** Get maximum element */
211
    public int getMaxElement();
212
    
213
    /** Convert to integer list */
214
    public List<Integer> toList();
215
    
216
    /** Convert to string with vocabulary */
217
    public String toString(Vocabulary vocabulary);
218
}
219

220
/**
221
 * Integer interval [a,b] 
222
 */
223
public class Interval {
224
    /** Start of interval (inclusive) */
225
    public int a;
226
    
227
    /** End of interval (inclusive) */
228
    public int b;
229
    
230
    /** Create interval */
231
    public Interval(int a, int b);
232
    
233
    /** Check if contains value */
234
    public boolean contains(int item);
235
    
236
    /** Get length of interval */
237
    public int length();
238
    
239
    /** Check if intervals overlap */
240
    public boolean intersects(Interval other);
241
    
242
    /** Get intersection with another interval */
243
    public Interval intersection(Interval other);
244
    
245
    /** Get union with another interval */
246
    public Interval union(Interval other);
247
}
248

249
/**
250
 * Resizable integer array with efficient operations
251
 */
252
public class IntegerList {
253
    /** Create empty list */
254
    public IntegerList();
255
    
256
    /** Create list with initial capacity */
257
    public IntegerList(int capacity);
258
    
259
    /** Create list from array */
260
    public IntegerList(int[] list);
261
    
262
    /** Add integer to end */
263
    public void add(int value);
264
    
265
    /** Add all integers from another list */
266
    public void addAll(int[] array);
267
    
268
    /** Get integer at index */
269
    public int get(int index);
270
    
271
    /** Check if contains value */
272
    public boolean contains(int value);
273
    
274
    /** Set value at index */
275
    public int set(int index, int value);
276
    
277
    /** Remove value at index */
278
    public int removeAt(int index);
279
    
280
    /** Remove first occurrence of value */
281
    public boolean removeValue(int value);
282
    
283
    /** Get size */
284
    public int size();
285
    
286
    /** Check if empty */
287
    public boolean isEmpty();
288
    
289
    /** Clear all elements */
290
    public void clear();
291
    
292
    /** Convert to array */
293
    public int[] toArray();
294
    
295
    /** Sort elements */
296
    public void sort();
297
    
298
    /** Binary search for value */
299
    public int binarySearch(int value);
300
}
301
```
302

303
### Generic Utility Classes
304

305
Generic classes for common data patterns.
306

307
```java { .api }
308
/**
309
 * Generic pair of two values
310
 */
311
public class Pair<A, B> {
312
    /** First value */
313
    public final A a;
314
    
315
    /** Second value */
316
    public final B b;
317
    
318
    /** Create pair */
319
    public Pair(A a, B b);
320
    
321
    /** Get first value */
322
    public A getFirst();
323
    
324
    /** Get second value */
325
    public B getSecond();
326
    
327
    @Override
328
    public boolean equals(Object obj);
329
    
330
    @Override
331
    public int hashCode();
332
    
333
    @Override
334
    public String toString();
335
}
336

337
/**
338
 * Generic triple of three values
339
 */
340
public class Triple<A, B, C> {
341
    /** First value */
342
    public final A a;
343
    
344
    /** Second value */
345
    public final B b;
346
    
347
    /** Third value */
348
    public final C c;
349
    
350
    /** Create triple */
351
    public Triple(A a, B b, C c);
352
    
353
    @Override
354
    public boolean equals(Object obj);
355
    
356
    @Override
357
    public int hashCode();
358
    
359
    @Override
360
    public String toString();
361
}
362

363
/**
364
 * Map with two keys mapping to single value
365
 */
366
public class DoubleKeyMap<K1, K2, V> {
367
    /** Internal storage */
368
    protected Map<K1, Map<K2, V>> data = new HashMap<>();
369
    
370
    /** Put value with two keys */
371
    public V put(K1 k1, K2 k2, V v);
372
    
373
    /** Get value by two keys */
374
    public V get(K1 k1, K2 k2);
375
    
376
    /** Remove value by two keys */
377
    public V remove(K1 k1, K2 k2);
378
    
379
    /** Get all values for first key */
380
    public Map<K2, V> get(K1 k1);
381
    
382
    /** Get all first-level keys */
383
    public Set<K1> keySet();
384
    
385
    /** Get all values */
386
    public Collection<V> values();
387
}
388

389
/**
390
 * Map where each key can have multiple values
391
 */
392
public class MultiMap<K, V> {
393
    /** Internal storage */
394
    protected Map<K, List<V>> data = new HashMap<>();
395
    
396
    /** Add value to key */
397
    public void map(K key, V value);
398
    
399
    /** Get list of values for key */
400
    public List<V> get(K key);
401
    
402
    /** Get all keys */
403
    public Set<K> keySet();
404
    
405
    /** Get all value lists */
406
    public Collection<List<V>> values();
407
    
408
    /** Check if key has any values */
409
    public boolean containsKey(K key);
410
    
411
    /** Remove all values for key */
412
    public List<V> remove(K key);
413
    
414
    /** Remove specific value from key */
415
    public boolean remove(K key, V value);
416
    
417
    /** Get size (total number of key-value pairs) */
418
    public int size();
419
}
420
```
421

422
### Testing Infrastructure
423

424
Command-line tool for testing grammars interactively.
425

426
```java { .api }
427
/**
428
 * Command-line tool for testing grammars (grun command)
429
 */
430
public class TestRig {
431
    /** Main entry point for grammar testing */
432
    public static void main(String[] args) throws Exception;
433
    
434
    /** Process input with specified grammar and rule */
435
    public void process(String grammarName, String startRuleName, 
436
                       InputStream is, boolean printTree) throws Exception;
437
}
438
```
439

440
The TestRig (accessible via `grun` command) accepts these arguments:
441
- Grammar name
442
- Start rule name  
443
- Input options: `-tokens` (show tokens), `-tree` (show parse tree), `-gui` (show GUI), `-ps` (PostScript output)
444
- Input source: file name or stdin
445

446
**Usage Examples:**
447

448
```bash
449
# Test grammar interactively
450
grun MyGrammar expr -tree
451
# Type input, press Ctrl+D (Unix) or Ctrl+Z (Windows)
452

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

456
# Show tokens only
457
grun MyGrammar expr -tokens input.txt
458

459
# Show GUI tree viewer
460
grun MyGrammar expr -gui input.txt
461
```
462

463
### General Utilities
464

465
Static utility methods for common operations.
466

467
```java { .api }
468
/**
469
 * General utility methods
470
 */
471
public class Utils {
472
    /** Join array elements with separator */
473
    public static String join(Object[] array, String separator);
474
    
475
    /** Join iterable elements with separator */
476
    public static String join(Iterable<?> iter, String separator);
477
    
478
    /** Escape string for display */
479
    public static String escapeWhitespace(String s, boolean escapeSpaces);
480
    
481
    /** Write object to file */
482
    public static void writeFile(String fileName, String content);
483
    
484
    /** Read file to string */
485
    public static String readFile(String fileName) throws IOException;
486
    
487
    /** Convert integer to hex string */
488
    public static String hex(int value);
489
    
490
    /** Convert character to escaped string */
491
    public static String escapeChar(int c);
492
    
493
    /** Check if character is printable */
494
    public static boolean isPrintable(int c);
495
    
496
    /** Get platform-specific line separator */
497
    public static String getLineSeparator();
498
}
499
```
500

501
## XPath Querying
502

503
XPath-like querying system for parse trees.
504

505
```java { .api }
506
/**
507
 * XPath-like querying of parse trees
508
 */
509
public class XPath {
510
    /** Find all nodes matching XPath expression */
511
    public static Collection<ParseTree> findAll(ParseTree tree, String xpath, Parser parser);
512
    
513
    /** Compile XPath expression into elements */
514
    public static XPathElement[] split(String path);
515
}
516

517
/**
518
 * Base class for XPath elements
519
 */
520
public abstract class XPathElement {
521
    /** Node name being matched */
522
    protected String nodeName;
523
    
524
    /** Whether this element inverts the match */
525
    protected boolean invert;
526
    
527
    /** Evaluate element against parse tree node */
528
    public abstract Collection<ParseTree> evaluate(ParseTree t);
529
}
530
```
531

532
**XPath Syntax Examples:**
533

534
```java
535
import org.antlr.v4.runtime.tree.xpath.XPath;
536

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

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

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

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

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

553
## Usage Patterns
554

555
### Tree Analysis and Annotation
556

557
```java
558
import org.antlr.v4.runtime.tree.*;
559

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

565
// First pass: classify nodes
566
ParseTreeWalker walker = new ParseTreeWalker();
567
walker.walk(new MyBaseListener() {
568
    @Override
569
    public void enterExpr(MyParser.ExprContext ctx) {
570
        if (ctx.getChildCount() == 3) {
571
            nodeTypes.put(ctx, "binary_op");
572
        } else if (ctx.getChildCount() == 1) {
573
            nodeTypes.put(ctx, "primary");
574
        }
575
    }
576
}, tree);
577

578
// Second pass: compute values
579
MyVisitor<Integer> calculator = new MyBaseVisitor<Integer>() {
580
    @Override
581
    public Integer visitExpr(MyParser.ExprContext ctx) {
582
        Integer result = visitChildren(ctx);
583
        if (result != null) {
584
            exprValues.put(ctx, result);
585
        }
586
        return result;
587
    }
588
};
589
calculator.visit(tree);
590

591
// Query results
592
for (ParseTree node : nodeTypes.keySet()) {
593
    String type = nodeTypes.get(node);
594
    Integer value = exprValues.get(node);
595
    System.out.println("Node type: " + type + ", value: " + value);
596
}
597
```
598

599
### Advanced Tree Queries
600

601
```java
602
import org.antlr.v4.runtime.tree.*;
603
import org.antlr.v4.runtime.tree.xpath.XPath;
604

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

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

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

627
// Find deepest node
628
int maxDepth = 0;
629
ParseTree deepestNode = null;
630
for (ParseTree node : allNodes) {
631
    int depth = Trees.getNodeDepth(tree, node);
632
    if (depth > maxDepth) {
633
        maxDepth = depth;
634
        deepestNode = node;
635
    }
636
}
637
System.out.println("Deepest node at depth " + maxDepth + ": " + deepestNode.getText());
638
```
639

640
### Data Structure Usage
641

642
```java
643
import org.antlr.v4.runtime.misc.*;
644

645
// Interval set for token types
646
IntervalSet keywords = new IntervalSet();
647
keywords.add(MyLexer.IF);
648
keywords.add(MyLexer.ELSE);
649
keywords.add(MyLexer.WHILE);
650
keywords.add(MyLexer.FOR);
651

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

657
// Integer list for positions
658
IntegerList errorPositions = new IntegerList();
659
errorPositions.add(10);
660
errorPositions.add(25);
661
errorPositions.add(42);
662

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

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

670
// Multi-map for dependencies
671
MultiMap<String, String> dependencies = new MultiMap<>();
672
dependencies.map("Parser.java", "Lexer.java");
673
dependencies.map("Parser.java", "Tree.java");
674
dependencies.map("Main.java", "Parser.java");
675

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