0
# Tree Walking
1
2
Traverse and transform parse trees using visitor patterns with pre-order, depth-first, and context-aware walking strategies. TatSu provides a comprehensive tree walking framework for AST analysis, transformation, and code generation.
3
4
## Capabilities
5
6
### Base Walker Classes
7
8
Foundation classes for implementing tree traversal patterns with automatic method dispatch and flexible visiting strategies.
9
10
```python { .api }
11
class NodeWalker:
12
"""
13
Base tree walker with method dispatch.
14
15
Features:
16
- Automatic method dispatch based on node types
17
- Flexible visiting patterns
18
- Extensible for custom node types
19
- Exception handling during traversal
20
"""
21
22
def walk(self, node):
23
"""
24
Walk a parse tree starting from the given node.
25
26
Parameters:
27
- node: Root node to start walking from
28
29
Returns:
30
Result of walking the tree (implementation dependent)
31
"""
32
33
def walk_children(self, node):
34
"""
35
Walk all children of the current node.
36
37
Parameters:
38
- node: Parent node whose children to walk
39
40
Returns:
41
List of results from walking each child
42
"""
43
44
def _find_walker(self, node):
45
"""
46
Find appropriate walker method for a node type.
47
48
Parameters:
49
- node: Node to find walker for
50
51
Returns:
52
Method: Walker method for the node type
53
"""
54
```
55
56
Usage example:
57
58
```python
59
import tatsu
60
from tatsu.walkers import NodeWalker
61
from tatsu.semantics import ModelBuilderSemantics
62
63
grammar = '''
64
expr = term ("+" term)*;
65
term = factor ("*" factor)*;
66
factor = "(" expr ")" | number;
67
number = /\d+/;
68
'''
69
70
class ExpressionWalker(NodeWalker):
71
"""Walk expression trees and collect information."""
72
73
def walk_expr(self, node):
74
"""Handle expression nodes."""
75
print(f"Found expression: {node}")
76
return self.walk_children(node)
77
78
def walk_term(self, node):
79
"""Handle term nodes."""
80
print(f"Found term: {node}")
81
return self.walk_children(node)
82
83
def walk_number(self, node):
84
"""Handle number nodes."""
85
print(f"Found number: {node}")
86
return int(str(node))
87
88
# Usage
89
model = tatsu.compile(grammar)
90
ast = model.parse("2 + 3 * 4", semantics=ModelBuilderSemantics())
91
92
walker = ExpressionWalker()
93
result = walker.walk(ast)
94
```
95
96
### Pre-Order Walker
97
98
Traverse trees in pre-order (parent before children), suitable for top-down analysis and code generation.
99
100
```python { .api }
101
class PreOrderWalker(NodeWalker):
102
"""
103
Pre-order tree traversal walker.
104
105
Visits parent nodes before their children, making it suitable for:
106
- Top-down analysis
107
- Code generation with forward declarations
108
- Dependency resolution
109
- Symbol table construction
110
"""
111
```
112
113
Usage example:
114
115
```python
116
from tatsu.walkers import PreOrderWalker
117
118
class CodeGenerator(PreOrderWalker):
119
"""Generate code using pre-order traversal."""
120
121
def __init__(self):
122
self.code = []
123
self.indent_level = 0
124
125
def walk_function_def(self, node):
126
"""Generate function definition."""
127
self.emit(f"def {node.name}({', '.join(node.params)}):")
128
self.indent_level += 1
129
130
# Walk children (function body)
131
self.walk_children(node)
132
133
self.indent_level -= 1
134
return node
135
136
def walk_assignment(self, node):
137
"""Generate assignment statement."""
138
self.emit(f"{node.target} = {self.evaluate_expr(node.value)}")
139
return node
140
141
def emit(self, code):
142
"""Emit code with proper indentation."""
143
indent = " " * self.indent_level
144
self.code.append(f"{indent}{code}")
145
146
def get_code(self):
147
"""Get generated code as string."""
148
return "\n".join(self.code)
149
150
# Usage
151
generator = CodeGenerator()
152
generator.walk(ast)
153
print(generator.get_code())
154
```
155
156
### Depth-First Walker
157
158
Traverse trees depth-first (children before parent), ideal for bottom-up analysis and evaluation.
159
160
```python { .api }
161
class DepthFirstWalker(NodeWalker):
162
"""
163
Depth-first tree traversal walker.
164
165
Visits child nodes before their parents, making it suitable for:
166
- Bottom-up evaluation
167
- Type inference
168
- Optimization passes
169
- Dependency analysis
170
- Post-order processing
171
"""
172
```
173
174
Usage example:
175
176
```python
177
from tatsu.walkers import DepthFirstWalker
178
179
class ExpressionEvaluator(DepthFirstWalker):
180
"""Evaluate arithmetic expressions using depth-first traversal."""
181
182
def walk_number(self, node):
183
"""Evaluate number literals."""
184
return int(str(node))
185
186
def walk_binary_op(self, node):
187
"""Evaluate binary operations."""
188
# Children are evaluated first (depth-first)
189
left = self.walk(node.left)
190
right = self.walk(node.right)
191
192
if node.operator == '+':
193
return left + right
194
elif node.operator == '*':
195
return left * right
196
elif node.operator == '-':
197
return left - right
198
elif node.operator == '/':
199
return left / right
200
else:
201
raise ValueError(f"Unknown operator: {node.operator}")
202
203
def walk_expr(self, node):
204
"""Handle expression nodes."""
205
if hasattr(node, 'terms'):
206
result = self.walk(node.terms[0])
207
for i in range(1, len(node.terms), 2):
208
op = node.terms[i]
209
operand = self.walk(node.terms[i + 1])
210
if op == '+':
211
result += operand
212
elif op == '-':
213
result -= operand
214
return result
215
return self.walk_children(node)
216
217
# Usage
218
evaluator = ExpressionEvaluator()
219
result = evaluator.walk(ast)
220
print(f"Expression evaluates to: {result}")
221
```
222
223
### Context-Aware Walker
224
225
Maintain context and state during tree traversal for advanced analysis requiring scope and environment tracking.
226
227
```python { .api }
228
class ContextWalker(NodeWalker):
229
"""
230
Context-aware tree walking with stack management.
231
232
Features:
233
- Context stack management
234
- Scope tracking
235
- State preservation across traversal
236
- Environment and symbol table support
237
"""
238
239
def get_node_context(self, node):
240
"""
241
Get context information for a specific node.
242
243
Parameters:
244
- node: Node to get context for
245
246
Returns:
247
Context information for the node
248
"""
249
250
def enter_context(self, context):
251
"""
252
Enter a new context scope.
253
254
Parameters:
255
- context: Context object to enter
256
"""
257
258
def leave_context(self):
259
"""
260
Leave the current context scope.
261
262
Returns:
263
Previous context that was left
264
"""
265
266
def push_context(self, context):
267
"""
268
Push context onto the context stack.
269
270
Parameters:
271
- context: Context to push
272
"""
273
274
def pop_context(self):
275
"""
276
Pop context from the context stack.
277
278
Returns:
279
Context that was popped
280
"""
281
```
282
283
Usage example:
284
285
```python
286
from tatsu.walkers import ContextWalker
287
288
class SymbolTableWalker(ContextWalker):
289
"""Build symbol table with scope awareness."""
290
291
def __init__(self):
292
super().__init__()
293
self.scopes = [{}] # Stack of symbol tables
294
self.current_scope = self.scopes[-1]
295
296
def enter_scope(self):
297
"""Enter a new lexical scope."""
298
new_scope = {}
299
self.scopes.append(new_scope)
300
self.current_scope = new_scope
301
302
def leave_scope(self):
303
"""Leave current lexical scope."""
304
if len(self.scopes) > 1:
305
self.scopes.pop()
306
self.current_scope = self.scopes[-1]
307
308
def walk_function_def(self, node):
309
"""Handle function definitions with new scope."""
310
# Add function to current scope
311
self.current_scope[node.name] = {
312
'type': 'function',
313
'params': node.params,
314
'node': node
315
}
316
317
# Enter function scope for parameters and body
318
self.enter_scope()
319
320
# Add parameters to function scope
321
for param in node.params:
322
self.current_scope[param] = {
323
'type': 'parameter',
324
'node': node
325
}
326
327
# Walk function body
328
self.walk_children(node.body)
329
330
# Leave function scope
331
self.leave_scope()
332
333
return node
334
335
def walk_variable_ref(self, node):
336
"""Handle variable references with scope resolution."""
337
var_name = str(node)
338
339
# Search scopes from innermost to outermost
340
for scope in reversed(self.scopes):
341
if var_name in scope:
342
return scope[var_name]
343
344
# Variable not found in any scope
345
raise NameError(f"Undefined variable: {var_name}")
346
347
def walk_assignment(self, node):
348
"""Handle variable assignments."""
349
var_name = str(node.target)
350
351
# Walk the value expression first
352
value_info = self.walk(node.value)
353
354
# Add variable to current scope
355
self.current_scope[var_name] = {
356
'type': 'variable',
357
'value': value_info,
358
'node': node
359
}
360
361
return node
362
363
# Usage
364
symbol_walker = SymbolTableWalker()
365
symbol_walker.walk(ast)
366
367
# Access symbol table
368
print("Global scope:", symbol_walker.scopes[0])
369
```
370
371
### Custom Walker Patterns
372
373
Advanced patterns for specialized tree walking needs.
374
375
```python { .api }
376
class MultiPassWalker(NodeWalker):
377
"""Walker that makes multiple passes over the tree."""
378
379
def __init__(self, passes):
380
"""
381
Initialize multi-pass walker.
382
383
Parameters:
384
- passes: List of pass functions to execute
385
"""
386
self.passes = passes
387
self.current_pass = 0
388
389
def walk_multi_pass(self, node):
390
"""Execute all passes on the tree."""
391
results = []
392
for i, pass_func in enumerate(self.passes):
393
self.current_pass = i
394
result = pass_func(node)
395
results.append(result)
396
return results
397
398
class CollectingWalker(NodeWalker):
399
"""Walker that collects nodes matching specific criteria."""
400
401
def __init__(self, predicate):
402
"""
403
Initialize collecting walker.
404
405
Parameters:
406
- predicate: Function that returns True for nodes to collect
407
"""
408
self.predicate = predicate
409
self.collected = []
410
411
def walk(self, node):
412
"""Walk tree and collect matching nodes."""
413
if self.predicate(node):
414
self.collected.append(node)
415
416
return self.walk_children(node)
417
418
def get_collected(self):
419
"""Get list of collected nodes."""
420
return self.collected
421
422
class TransformingWalker(NodeWalker):
423
"""Walker that transforms the tree structure."""
424
425
def walk(self, node):
426
"""Walk and transform nodes."""
427
# Transform current node
428
transformed = self.transform_node(node)
429
430
# Transform children
431
if hasattr(transformed, 'children'):
432
new_children = []
433
for child in transformed.children():
434
new_child = self.walk(child)
435
new_children.append(new_child)
436
transformed.set_children(new_children)
437
438
return transformed
439
440
def transform_node(self, node):
441
"""Override to implement node transformation."""
442
return node
443
444
# Usage examples
445
def is_number_node(node):
446
return hasattr(node, '__class__') and 'number' in node.__class__.__name__.lower()
447
448
# Collect all number nodes
449
collector = CollectingWalker(is_number_node)
450
collector.walk(ast)
451
numbers = collector.get_collected()
452
print(f"Found {len(numbers)} number nodes")
453
454
# Multi-pass analysis
455
def pass1_collect_functions(ast):
456
"""First pass: collect function definitions."""
457
# Implementation here
458
pass
459
460
def pass2_resolve_calls(ast):
461
"""Second pass: resolve function calls."""
462
# Implementation here
463
pass
464
465
multi_walker = MultiPassWalker([pass1_collect_functions, pass2_resolve_calls])
466
results = multi_walker.walk_multi_pass(ast)
467
```
468
469
### Error Handling in Walkers
470
471
```python
472
class SafeWalker(NodeWalker):
473
"""Walker with comprehensive error handling."""
474
475
def __init__(self):
476
self.errors = []
477
self.warnings = []
478
479
def walk(self, node):
480
"""Walk with error handling."""
481
try:
482
return super().walk(node)
483
except Exception as e:
484
self.errors.append({
485
'node': node,
486
'error': e,
487
'message': str(e)
488
})
489
return None # Continue walking despite errors
490
491
def walk_children(self, node):
492
"""Walk children with individual error handling."""
493
results = []
494
for child in getattr(node, 'children', lambda: [])():
495
try:
496
result = self.walk(child)
497
results.append(result)
498
except Exception as e:
499
self.warnings.append({
500
'parent': node,
501
'child': child,
502
'error': e
503
})
504
# Continue with other children
505
return results
506
507
def has_errors(self):
508
"""Check if any errors occurred during walking."""
509
return len(self.errors) > 0
510
511
def get_error_report(self):
512
"""Get detailed error report."""
513
report = []
514
for error in self.errors:
515
report.append(f"Error at {error['node']}: {error['message']}")
516
for warning in self.warnings:
517
report.append(f"Warning at {warning['parent']}: {warning['error']}")
518
return "\n".join(report)
519
520
# Usage with error handling
521
safe_walker = SafeWalker()
522
result = safe_walker.walk(ast)
523
524
if safe_walker.has_errors():
525
print("Errors occurred during walking:")
526
print(safe_walker.get_error_report())
527
else:
528
print("Walking completed successfully")
529
```