0
# Tree Processing
1
2
Parse tree representation and processing including tree nodes, visitor patterns for traversal, and transformer classes for modification and data extraction.
3
4
## Capabilities
5
6
### Tree Representation
7
8
The Tree class represents parse tree nodes containing rule data and child elements.
9
10
```python { .api }
11
class Tree:
12
"""
13
Parse tree node containing rule data and children.
14
"""
15
16
def __init__(self, data: str, children: list, meta=None):
17
"""
18
Initialize tree node.
19
20
Parameters:
21
- data: Rule name or alias
22
- children: List of child nodes/tokens
23
- meta: Position metadata (line, column, etc.)
24
"""
25
26
def pretty(self, indent_str: str = ' ') -> str:
27
"""
28
Return indented string representation for debugging.
29
30
Parameters:
31
- indent_str: String used for indentation
32
33
Returns:
34
str: Pretty-printed tree representation
35
"""
36
37
def iter_subtrees(self) -> Iterator['Tree']:
38
"""
39
Depth-first iteration over all subtrees including self.
40
41
Returns:
42
Iterator[Tree]: Subtree iterator
43
"""
44
45
def iter_subtrees_topdown(self) -> Iterator['Tree']:
46
"""
47
Breadth-first iteration over subtrees.
48
49
Returns:
50
Iterator[Tree]: Subtree iterator (top-down)
51
"""
52
53
def find_pred(self, pred: Callable[['Tree'], bool]) -> Iterator['Tree']:
54
"""
55
Find all nodes matching predicate function.
56
57
Parameters:
58
- pred: Predicate function taking Tree and returning bool
59
60
Returns:
61
Iterator[Tree]: Matching nodes
62
"""
63
64
def find_data(self, data: str) -> Iterator['Tree']:
65
"""
66
Find all nodes with specific data value.
67
68
Parameters:
69
- data: Rule name to search for
70
71
Returns:
72
Iterator[Tree]: Nodes with matching data
73
"""
74
75
def scan_values(self, pred: Callable[[Any], bool]) -> Iterator[Any]:
76
"""
77
Find all values (non-Tree children) matching predicate.
78
79
Parameters:
80
- pred: Predicate function for values
81
82
Returns:
83
Iterator[Any]: Matching values
84
"""
85
86
def expand_kids_by_index(self, *indices: int) -> None:
87
"""
88
Expand children at specified indices into parent's children list.
89
90
Parameters:
91
- *indices: Indices of children to expand
92
"""
93
94
def expand_kids_by_data(self, *data_values: str) -> None:
95
"""
96
Expand children with specified data values.
97
98
Parameters:
99
- *data_values: Data values of children to expand
100
"""
101
102
def copy(self) -> 'Tree':
103
"""
104
Create shallow copy of tree.
105
106
Returns:
107
Tree: Copied tree
108
"""
109
110
def set(self, data: str, children: list) -> 'Tree':
111
"""
112
Create new tree with specified data and children.
113
114
Parameters:
115
- data: New rule name
116
- children: New children list
117
118
Returns:
119
Tree: New tree instance
120
"""
121
122
# Properties
123
data: str # Rule name or alias
124
children: list # Child nodes and tokens
125
meta: Meta # Position metadata
126
127
# Position properties (deprecated, use meta)
128
line: int # Line number
129
column: int # Column number
130
end_line: int # End line number
131
end_column: int # End column number
132
```
133
134
### Memory-Optimized Tree
135
136
Slotted tree class for memory efficiency in large parse trees.
137
138
```python { .api }
139
class SlottedTree(Tree):
140
"""
141
Memory-optimized tree with __slots__.
142
"""
143
__slots__ = ('data', 'children', 'rule', '_meta')
144
```
145
146
### Position Metadata
147
148
Container for position information when propagate_positions is enabled.
149
150
```python { .api }
151
class Meta:
152
"""
153
Container for position metadata.
154
"""
155
156
def __init__(self):
157
self.empty = True
158
159
# Position attributes (set by parser when propagate_positions=True)
160
line: int # Start line (1-based)
161
column: int # Start column (1-based)
162
start_pos: int # Start position in input
163
end_line: int # End line (1-based)
164
end_column: int # End column (1-based)
165
end_pos: int # End position in input
166
empty: bool # Whether metadata is empty
167
```
168
169
### Tree Transformers
170
171
Classes for transforming parse trees into other data structures or modified trees.
172
173
```python { .api }
174
class Transformer:
175
"""
176
Transforms trees bottom-up according to node data.
177
Calls methods named after rules to transform nodes.
178
"""
179
180
def __init__(self, visit_tokens: bool = True):
181
"""
182
Initialize transformer.
183
184
Parameters:
185
- visit_tokens: Whether to visit token nodes
186
"""
187
188
def transform(self, tree: Tree) -> Any:
189
"""
190
Transform tree and return result.
191
192
Parameters:
193
- tree: Tree to transform
194
195
Returns:
196
Any: Transformation result
197
"""
198
199
def __mul__(self, other: 'Transformer') -> 'TransformerChain':
200
"""
201
Chain transformers using * operator.
202
203
Parameters:
204
- other: Transformer to chain
205
206
Returns:
207
TransformerChain: Chained transformers
208
"""
209
210
def __default__(self, data: str, children: list, meta) -> Any:
211
"""
212
Default transformation when no method found.
213
214
Parameters:
215
- data: Rule name
216
- children: Transformed children
217
- meta: Position metadata
218
219
Returns:
220
Any: Default transformation (usually Tree)
221
"""
222
223
def __default_token__(self, token: Token) -> Any:
224
"""
225
Default token transformation.
226
227
Parameters:
228
- token: Token to transform
229
230
Returns:
231
Any: Token transformation result
232
"""
233
234
__visit_tokens__: bool # Class attribute for token visiting
235
```
236
237
### In-Place Transformers
238
239
Transformers that modify trees in-place for memory efficiency.
240
241
```python { .api }
242
class Transformer_InPlace(Transformer):
243
"""
244
Non-recursive transformer that modifies tree in-place.
245
"""
246
247
class Transformer_InPlaceRecursive(Transformer):
248
"""
249
Recursive transformer that modifies tree in-place.
250
"""
251
252
class Transformer_NonRecursive(Transformer):
253
"""
254
Non-recursive transformer for processing huge trees.
255
Avoids stack overflow on very deep trees.
256
"""
257
```
258
259
### Transformer Chaining
260
261
Utility for combining multiple transformers.
262
263
```python { .api }
264
class TransformerChain:
265
"""
266
Chains multiple transformers together.
267
"""
268
269
def __init__(self, *transformers: Transformer):
270
"""
271
Initialize transformer chain.
272
273
Parameters:
274
- *transformers: Transformers to chain
275
"""
276
277
def transform(self, tree: Tree) -> Any:
278
"""
279
Apply all transformers in sequence.
280
281
Parameters:
282
- tree: Input tree
283
284
Returns:
285
Any: Final transformation result
286
"""
287
288
def __mul__(self, other: Transformer) -> 'TransformerChain':
289
"""
290
Add transformer to chain.
291
292
Parameters:
293
- other: Transformer to add
294
295
Returns:
296
TransformerChain: Extended chain
297
"""
298
```
299
300
### Tree Visitors
301
302
Classes for traversing trees without modification, useful for analysis and extraction.
303
304
```python { .api }
305
class Visitor:
306
"""
307
Non-recursive tree visitor for analysis without modification.
308
"""
309
310
def visit(self, tree: Tree) -> None:
311
"""
312
Visit tree bottom-up.
313
314
Parameters:
315
- tree: Tree to visit
316
"""
317
318
def visit_topdown(self, tree: Tree) -> None:
319
"""
320
Visit tree top-down.
321
322
Parameters:
323
- tree: Tree to visit
324
"""
325
326
def __default__(self, tree: Tree) -> None:
327
"""
328
Default visit method when no specific method found.
329
330
Parameters:
331
- tree: Tree node being visited
332
"""
333
334
class Visitor_Recursive:
335
"""
336
Recursive tree visitor, slightly faster than non-recursive.
337
"""
338
```
339
340
### Tree Interpreter
341
342
Advanced visitor with explicit visit control for complex tree processing.
343
344
```python { .api }
345
class Interpreter:
346
"""
347
Tree interpreter with explicit visit control.
348
"""
349
350
def visit(self, tree: Tree) -> Any:
351
"""
352
Visit single node without visiting children.
353
354
Parameters:
355
- tree: Tree node to visit
356
357
Returns:
358
Any: Visit result
359
"""
360
361
def visit_children(self, tree: Tree) -> list:
362
"""
363
Visit all children of node.
364
365
Parameters:
366
- tree: Parent tree node
367
368
Returns:
369
list: Results from visiting children
370
"""
371
372
def __default__(self, tree: Tree) -> Any:
373
"""
374
Default behavior when no method found.
375
376
Parameters:
377
- tree: Tree node
378
379
Returns:
380
Any: Default result
381
"""
382
```
383
384
### Visitor Decorators and Utilities
385
386
Decorators and functions for customizing visitor/transformer behavior.
387
388
```python { .api }
389
def v_args(inline: bool = False, meta: bool = False, tree: bool = False,
390
wrapper: Callable = None):
391
"""
392
Decorator to modify visitor/transformer method arguments.
393
394
Parameters:
395
- inline: Pass children as *args instead of list
396
- meta: Include meta information as parameter
397
- tree: Pass entire tree instead of just children
398
- wrapper: Custom wrapper function
399
400
Returns:
401
Callable: Decorator function
402
"""
403
404
def inline_args(f):
405
"""
406
Deprecated decorator. Use v_args(inline=True) instead.
407
"""
408
409
def visit_children_decor(func):
410
"""
411
Decorator for interpreter methods to auto-visit children.
412
413
Parameters:
414
- func: Method to decorate
415
416
Returns:
417
Callable: Decorated method
418
"""
419
420
def merge_transformers(*transformers, **kwargs) -> Transformer:
421
"""
422
Merge multiple transformers into combined namespaces.
423
424
Parameters:
425
- *transformers: Transformer instances to merge
426
- **kwargs: Additional options
427
428
Returns:
429
Transformer: Merged transformer
430
"""
431
```
432
433
### Ambiguity Handling
434
435
Transformer for processing ambiguous parse results.
436
437
```python { .api }
438
class CollapseAmbiguities(Transformer):
439
"""
440
Transforms ambiguous trees into lists of unambiguous alternatives.
441
Converts _ambig nodes into lists containing all possible interpretations.
442
"""
443
```
444
445
### Exception for Node Removal
446
447
Exception used to remove nodes during transformation.
448
449
```python { .api }
450
class Discard(Exception):
451
"""
452
When raised in transformer callback, discards node from parent.
453
The node will not appear in the transformed result.
454
"""
455
```
456
457
## Usage Examples
458
459
### Basic Tree Processing
460
461
```python
462
from lark import Lark, Tree
463
464
parser = Lark(grammar)
465
tree = parser.parse("2 + 3 * 4")
466
467
# Pretty print tree
468
print(tree.pretty())
469
470
# Find specific nodes
471
additions = list(tree.find_data('add'))
472
numbers = list(tree.find_data('number'))
473
474
# Iterate over all subtrees
475
for subtree in tree.iter_subtrees():
476
print(f"Rule: {subtree.data}, Children: {len(subtree.children)}")
477
```
478
479
### Creating a Transformer
480
481
```python
482
from lark import Transformer, v_args
483
484
class Calculator(Transformer):
485
"""Transform parse tree into calculated result."""
486
487
@v_args(inline=True)
488
def add(self, left, right):
489
return left + right
490
491
@v_args(inline=True)
492
def mul(self, left, right):
493
return left * right
494
495
def number(self, children):
496
return int(children[0])
497
498
# Apply transformer
499
calc = Calculator()
500
result = calc.transform(tree)
501
print(f"Result: {result}")
502
```
503
504
### Transformer with Token Handling
505
506
```python
507
from lark import Transformer, Token
508
509
class MyTransformer(Transformer):
510
def __init__(self):
511
super().__init__(visit_tokens=True)
512
513
def IDENTIFIER(self, token):
514
# Transform identifier tokens
515
return token.value.upper()
516
517
def __default_token__(self, token):
518
# Default token handling
519
return token.value
520
```
521
522
### Visitor for Analysis
523
524
```python
525
from lark import Visitor
526
527
class VariableCollector(Visitor):
528
def __init__(self):
529
self.variables = set()
530
531
def identifier(self, tree):
532
self.variables.add(tree.children[0].value)
533
534
# Collect variables
535
collector = VariableCollector()
536
collector.visit(tree)
537
print(f"Variables found: {collector.variables}")
538
```
539
540
### Chaining Transformers
541
542
```python
543
from lark import Transformer
544
545
class FirstTransform(Transformer):
546
def rule1(self, children):
547
return "first_" + str(children[0])
548
549
class SecondTransform(Transformer):
550
def rule1(self, children):
551
return children[0] + "_second"
552
553
# Chain transformers
554
chained = FirstTransform() * SecondTransform()
555
result = chained.transform(tree)
556
```
557
558
### Using Interpreter
559
560
```python
561
from lark import Interpreter
562
563
class MyInterpreter(Interpreter):
564
def expression(self, tree):
565
# Manually control child visiting
566
left = self.visit(tree.children[0])
567
op = tree.children[1].value
568
right = self.visit(tree.children[2])
569
570
if op == '+':
571
return left + right
572
elif op == '*':
573
return left * right
574
575
def number(self, tree):
576
return int(tree.children[0].value)
577
```
578
579
### Handling Ambiguous Results
580
581
```python
582
from lark import Lark, CollapseAmbiguities
583
584
# Parse with ambiguity="explicit"
585
parser = Lark(ambiguous_grammar, ambiguity="explicit")
586
tree = parser.parse(text)
587
588
# Collapse ambiguities into lists
589
collapse = CollapseAmbiguities()
590
alternatives = collapse.transform(tree)
591
592
# Process each alternative
593
for alt in alternatives:
594
process_interpretation(alt)
595
```