0
# Parse Tree API
1

2
The ANTLR4 parse tree API provides comprehensive functionality for building, navigating, and manipulating parse trees using visitor and listener patterns.
3

4
## Capabilities
5

6
### Parse Tree Interfaces
7

8
Core interfaces defining the structure of parse trees.
9

10
```java { .api }
11
/**
12
 * Base interface for all parse tree nodes
13
 */
14
public interface ParseTree extends SyntaxTree {
15
    /** Get parent node */
16
    ParseTree getParent();
17
    
18
    /** Get child node at index */
19
    ParseTree getChild(int i);
20
    
21
    /** Get number of children */
22
    int getChildCount();
23
    
24
    /** Accept visitor for tree traversal */
25
    <T> T accept(ParseTreeVisitor<? extends T> visitor);
26
    
27
    /** Get text representation of subtree */
28
    String getText();
29
    
30
    /** Get text with spaces between tokens */
31
    String toStringTree();
32
    
33
    /** Get source interval for this node */
34
    Interval getSourceInterval();
35
}
36

37
/**
38
 * Parse tree node representing parser rule invocation
39
 */
40
public interface RuleNode extends ParseTree {
41
    /** Get rule context for this node */
42
    RuleContext getRuleContext();
43
}
44

45
/**
46
 * Parse tree leaf node representing terminal/token
47
 */
48
public interface TerminalNode extends ParseTree {
49
    /** Get token for this terminal node */
50
    Token getSymbol();
51
}
52

53
/**
54
 * Parse tree node representing syntax error
55
 */
56
public interface ErrorNode extends TerminalNode {
57
    // Inherits from TerminalNode
58
}
59
```
60

61
### Parser Rule Context
62

63
Context classes providing detailed information about rule invocations.
64

65
```java { .api }
66
/**
67
 * Parse tree node for parser rules with context information
68
 */
69
public class ParserRuleContext extends RuleContext implements RuleNode {
70
    /** Parent context */
71
    public ParserRuleContext parent;
72
    
73
    /** State when rule was invoked */
74
    public int invokingState;
75
    
76
    /** List of child nodes */
77
    public List<ParseTree> children;
78
    
79
    /** Start token for this rule */
80
    public Token start;
81
    
82
    /** Stop token for this rule */
83
    public Token stop;
84
    
85
    /** Exception that caused rule to exit */
86
    public RecognitionException exception;
87
    
88
    /** Add terminal child node */
89
    public void addChild(TerminalNode t);
90
    
91
    /** Add rule child node */
92
    public void addChild(RuleContext ruleInvocation);
93
    
94
    /** Remove last child */
95
    public void removeLastChild();
96
    
97
    /** Add error node child */
98
    public void addErrorNode(ErrorNode errorNode);
99
    
100
    /** Add child at specific index */
101
    public void addChild(int index, ParseTree child);
102
    
103
    /** Get child of specific type */
104
    public <T extends ParseTree> T getChild(Class<T> ctxType, int i);
105
    
106
    /** Get terminal child */
107
    public TerminalNode getToken(int ttype, int i);
108
    
109
    /** Get all terminal children of type */
110
    public List<TerminalNode> getTokens(int ttype);
111
    
112
    /** Get rule child by type */
113
    public <T extends ParserRuleContext> T getRuleContext(Class<T> ctxType, int i);
114
    
115
    /** Get all rule children of type */
116
    public <T extends ParserRuleContext> List<T> getRuleContexts(Class<T> ctxType);
117
    
118
    /** Accept visitor */
119
    @Override
120
    public <T> T accept(ParseTreeVisitor<? extends T> visitor);
121
    
122
    /** Get text from start to stop token */
123
    @Override
124
    public String getText();
125
    
126
    /** Convert subtree to string with parser info */
127
    public String toStringTree(Parser parser);
128
    
129
    /** Convert subtree to string with rule names */
130
    public String toStringTree(List<String> ruleNames);
131
    
132
    /** Get source interval */
133
    @Override
134
    public Interval getSourceInterval();
135
}
136

137
/**
138
 * Base class for rule contexts
139
 */
140
public class RuleContext {
141
    /** Parent rule context */
142
    public RuleContext parent;
143
    
144
    /** Invoking state */
145
    public int invokingState;
146
    
147
    /** Calculate depth in parse tree */
148
    public int depth();
149
    
150
    /** Check if context is empty */
151
    public boolean isEmpty();
152
    
153
    /** Get source interval */
154
    public Interval getSourceInterval();
155
    
156
    /** Get rule index */
157
    public int getRuleIndex();
158
    
159
    /** Get invoking state */
160
    public int getInvokingState();
161
    
162
    /** Set invoking state */
163
    public void setInvokingState(int invokingState);
164
    
165
    /** Set parent context */
166
    public void setParent(RuleContext parent);
167
    
168
    /** Get parent context */
169
    public RuleContext getParent();
170
    
171
    /** Get payload (returns this) */
172
    public RuleContext getPayload();
173
    
174
    /** Get text representation */
175
    public String getText();
176
    
177
    /** Convert to string tree */
178
    public String toStringTree();
179
}
180
```
181

182
### Visitor Pattern
183

184
Interface and base class for implementing the visitor pattern on parse trees.
185

186
```java { .api }
187
/**
188
 * Visitor pattern interface for parse tree traversal
189
 */
190
public interface ParseTreeVisitor<T> {
191
    /** Visit parse tree node and return result */
192
    T visit(ParseTree tree);
193
    
194
    /** Visit all children of rule node */
195
    T visitChildren(RuleNode node);
196
    
197
    /** Visit terminal node */
198
    T visitTerminal(TerminalNode node);
199
    
200
    /** Visit error node */
201
    T visitErrorNode(ErrorNode node);
202
}
203

204
/**
205
 * Base implementation of visitor pattern with default behavior
206
 */
207
public abstract class AbstractParseTreeVisitor<T> implements ParseTreeVisitor<T> {
208
    /** Visit tree node, delegating to appropriate method */
209
    @Override
210
    public T visit(ParseTree tree) {
211
        return tree.accept(this);
212
    }
213
    
214
    /** Visit all children and return result of last non-null visit */
215
    @Override
216
    public T visitChildren(RuleNode node) {
217
        T result = defaultResult();
218
        int n = node.getChildCount();
219
        for (int i = 0; i < n; i++) {
220
            if (!shouldVisitNextChild(node, result)) {
221
                break;
222
            }
223
            
224
            ParseTree c = node.getChild(i);
225
            T childResult = c.accept(this);
226
            result = aggregateResult(result, childResult);
227
        }
228
        return result;
229
    }
230
    
231
    /** Visit terminal node (default returns defaultResult()) */
232
    @Override
233
    public T visitTerminal(TerminalNode node) {
234
        return defaultResult();
235
    }
236
    
237
    /** Visit error node (default returns defaultResult()) */
238
    @Override
239
    public T visitErrorNode(ErrorNode node) {
240
        return defaultResult();
241
    }
242
    
243
    /** Default result value */
244
    protected T defaultResult() {
245
        return null;
246
    }
247
    
248
    /** Aggregate results from multiple children */
249
    protected T aggregateResult(T aggregate, T nextResult) {
250
        return nextResult;
251
    }
252
    
253
    /** Determine if should visit next child */
254
    protected boolean shouldVisitNextChild(RuleNode node, T currentResult) {
255
        return true;
256
    }
257
}
258
```
259

260
**Usage Example:**
261

262
```java
263
import org.antlr.v4.runtime.tree.*;
264

265
// Custom visitor implementation
266
public class MyVisitor extends MyBaseVisitor<String> {
267
    @Override
268
    public String visitExpr(MyParser.ExprContext ctx) {
269
        if (ctx.getChildCount() == 3) {
270
            String left = visit(ctx.getChild(0));
271
            String op = ctx.getChild(1).getText();
272
            String right = visit(ctx.getChild(2));
273
            return "(" + left + " " + op + " " + right + ")";
274
        }
275
        return visitChildren(ctx);
276
    }
277
    
278
    @Override
279
    public String visitTerminal(TerminalNode node) {
280
        return node.getText();
281
    }
282
}
283

284
// Use visitor
285
ParseTree tree = parser.expr();
286
MyVisitor visitor = new MyVisitor();
287
String result = visitor.visit(tree);
288
```
289

290
### Listener Pattern
291

292
Interface and walker for implementing the listener pattern on parse trees.
293

294
```java { .api }
295
/**
296
 * Listener pattern interface for parse tree events
297
 */
298
public interface ParseTreeListener {
299
    /** Called when entering any rule */
300
    void enterEveryRule(ParserRuleContext ctx);
301
    
302
    /** Called when exiting any rule */
303
    void exitEveryRule(ParserRuleContext ctx);
304
    
305
    /** Called when visiting terminal node */
306
    void visitTerminal(TerminalNode node);
307
    
308
    /** Called when visiting error node */
309
    void visitErrorNode(ErrorNode node);
310
}
311

312
/**
313
 * Tree walker utility for traversing parse trees with listeners
314
 */
315
public class ParseTreeWalker {
316
    /** Default walker instance */
317
    public static final ParseTreeWalker DEFAULT = new ParseTreeWalker();
318
    
319
    /** Walk tree with listener, calling enter/exit methods */
320
    public void walk(ParseTreeListener listener, ParseTree t) {
321
        if (t instanceof ErrorNode) {
322
            listener.visitErrorNode((ErrorNode) t);
323
            return;
324
        } else if (t instanceof TerminalNode) {
325
            listener.visitTerminal((TerminalNode) t);
326
            return;
327
        }
328
        
329
        RuleNode r = (RuleNode) t;
330
        ParserRuleContext ctx = (ParserRuleContext) r.getRuleContext();
331
        
332
        enterRule(listener, r);
333
        
334
        for (int i = 0; i < t.getChildCount(); i++) {
335
            walk(listener, t.getChild(i));
336
        }
337
        
338
        exitRule(listener, r);
339
    }
340
    
341
    /** Enter rule node */
342
    protected void enterRule(ParseTreeListener listener, RuleNode r) {
343
        ParserRuleContext ctx = (ParserRuleContext) r.getRuleContext();
344
        listener.enterEveryRule(ctx);
345
        ctx.enterRule(listener);
346
    }
347
    
348
    /** Exit rule node */
349
    protected void exitRule(ParseTreeListener listener, RuleNode r) {
350
        ParserRuleContext ctx = (ParserRuleContext) r.getRuleContext();
351
        ctx.exitRule(listener);
352
        listener.exitEveryRule(ctx);
353
    }
354
}
355
```
356

357
**Usage Example:**
358

359
```java
360
import org.antlr.v4.runtime.tree.*;
361

362
// Custom listener implementation
363
public class MyListener extends MyBaseListener {
364
    @Override
365
    public void enterExpr(MyParser.ExprContext ctx) {
366
        System.out.println("Entering expression: " + ctx.getText());
367
    }
368
    
369
    @Override
370
    public void exitExpr(MyParser.ExprContext ctx) {
371
        System.out.println("Exiting expression: " + ctx.getText());
372
    }
373
    
374
    @Override
375
    public void visitTerminal(TerminalNode node) {
376
        System.out.println("Terminal: " + node.getText());
377
    }
378
}
379

380
// Use listener
381
ParseTree tree = parser.expr();
382
ParseTreeWalker walker = new ParseTreeWalker();
383
MyListener listener = new MyListener();
384
walker.walk(listener, tree);
385
```
386

387
### Tree Utility Methods
388

389
Static utility methods for common parse tree operations.
390

391
```java { .api }
392
/**
393
 * Static utility methods for parse trees
394
 */
395
public class Trees {
396
    /** Convert tree to string representation */
397
    public static String toStringTree(ParseTree t);
398
    
399
    /** Convert tree to string using parser */
400
    public static String toStringTree(ParseTree t, Parser parser);
401
    
402
    /** Convert tree to string using rule names */
403
    public static String toStringTree(ParseTree t, List<String> ruleNames);
404
    
405
    /** Get all children of a parse tree node */
406
    public static List<ParseTree> getChildren(ParseTree t);
407
    
408
    /** Get all ancestors of a parse tree node */
409
    public static List<ParseTree> getAncestors(ParseTree t);
410
    
411
    /** Find all nodes with specified token type */
412
    public static Collection<ParseTree> findAllTokenNodes(ParseTree t, int ttype);
413
    
414
    /** Find all nodes with specified rule index */
415
    public static Collection<ParseTree> findAllRuleNodes(ParseTree t, int ruleIndex);
416
    
417
    /** Find all descendant nodes with specified rule index */
418
    public static Collection<ParseTree> descendants(ParseTree t);
419
    
420
    /** Get node ancestors up to specified rule type */
421
    public static ParserRuleContext getAncestorOfType(ParserRuleContext ctx, Class<? extends ParserRuleContext> ruleType);
422
    
423
    /** Strip parse tree to text only */
424
    public static String stripParseTree(ParseTree t);
425
}
426
```
427

428
### Parse Tree Properties
429

430
Associate arbitrary data with parse tree nodes.
431

432
```java { .api }
433
/**
434
 * Associate arbitrary data with parse tree nodes
435
 */
436
public class ParseTreeProperty<V> {
437
    /** Associate value with parse tree node */
438
    public V put(ParseTree node, V value);
439
    
440
    /** Get value associated with parse tree node */
441
    public V get(ParseTree node);
442
    
443
    /** Remove association for parse tree node */
444
    public V removeFrom(ParseTree node);
445
}
446
```
447

448
**Usage Example:**
449

450
```java
451
import org.antlr.v4.runtime.tree.*;
452

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

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

460
// Retrieve data
461
String type = nodeTypes.get(exprNode); // "arithmetic"
462
```
463

464
## Pattern Matching
465

466
XPath-like querying of parse trees.
467

468
```java { .api }
469
/**
470
 * XPath-like querying of parse trees
471
 */
472
public class XPath {
473
    /** Find all nodes matching XPath expression */
474
    public static Collection<ParseTree> findAll(ParseTree tree, String xpath, Parser parser);
475
    
476
    /** Compile XPath expression */
477
    public static XPathElement[] split(String path);
478
}
479
```
480

481
**Usage Example:**
482

483
```java
484
import org.antlr.v4.runtime.tree.xpath.XPath;
485

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

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

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

496
## Usage Patterns
497

498
### Basic Tree Traversal
499

500
```java
501
import org.antlr.v4.runtime.tree.*;
502

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

506
// Simple visitor
507
MyVisitor visitor = new MyVisitor();
508
String result = visitor.visit(tree);
509

510
// Simple listener
511
ParseTreeWalker walker = new ParseTreeWalker();
512
MyListener listener = new MyListener();
513
walker.walk(listener, tree);
514
```
515

516
### Complex Tree Analysis
517

518
```java
519
import org.antlr.v4.runtime.tree.*;
520

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

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

529
// Convert to string
530
String treeString = Trees.toStringTree(tree, parser);
531
System.out.println(treeString);
532
```
533

534
### Tree Modification and Analysis
535

536
```java
537
import org.antlr.v4.runtime.tree.*;
538

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

543
// Visitor that computes and stores depth
544
public class DepthVisitor extends MyBaseVisitor<Integer> {
545
    @Override
546
    public Integer visitExpr(MyParser.ExprContext ctx) {
547
        int maxChildDepth = 0;
548
        for (int i = 0; i < ctx.getChildCount(); i++) {
549
            Integer childDepth = visit(ctx.getChild(i));
550
            if (childDepth != null && childDepth > maxChildDepth) {
551
                maxChildDepth = childDepth;
552
            }
553
        }
554
        int thisDepth = maxChildDepth + 1;
555
        depths.put(ctx, thisDepth);
556
        return thisDepth;
557
    }
558
    
559
    @Override
560
    public Integer visitTerminal(TerminalNode node) {
561
        depths.put(node, 0);
562
        return 0;
563
    }
564
}
565

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

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