01d5532823
Educational calculator teaching FSMs (explicit transition table tokenizer) and DAGs (recursive descent parser with AST evaluation). Includes CLI with REPL, graphviz visualization, and 61 tests. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
148 lines
4.8 KiB
Python
148 lines
4.8 KiB
Python
"""
|
|
Part 3: DAG Evaluation -- Tree Walker
|
|
=======================================
|
|
Evaluating the AST bottom-up is equivalent to topological-sort
|
|
evaluation of a DAG. We must evaluate a node's children before
|
|
the node itself -- just like in any dependency graph.
|
|
|
|
For a tree, post-order traversal gives a topological ordering.
|
|
The recursive evaluate() function naturally does this:
|
|
1. Recursively evaluate all children (dependencies)
|
|
2. Combine the results (compute this node's value)
|
|
3. Return the result (make it available to the parent)
|
|
|
|
This is the same pattern as:
|
|
- make: build dependencies before the target
|
|
- pip/npm install: install dependencies before the package
|
|
- Spreadsheet recalculation: compute referenced cells first
|
|
"""
|
|
|
|
from parser import NumberNode, BinOpNode, UnaryOpNode, Node
|
|
from tokenizer import TokenType
|
|
|
|
|
|
# ---------- Errors ----------
|
|
|
|
class EvalError(Exception):
|
|
pass
|
|
|
|
|
|
# ---------- Evaluator ----------
|
|
|
|
OP_SYMBOLS = {
|
|
TokenType.PLUS: '+',
|
|
TokenType.MINUS: '-',
|
|
TokenType.MULTIPLY: '*',
|
|
TokenType.DIVIDE: '/',
|
|
TokenType.POWER: '^',
|
|
TokenType.UNARY_MINUS: 'neg',
|
|
}
|
|
|
|
|
|
def evaluate(node):
|
|
"""
|
|
Evaluate an AST by walking it bottom-up (post-order traversal).
|
|
|
|
This is a recursive function that mirrors the DAG structure:
|
|
each recursive call follows a DAG edge to a child node.
|
|
Children are evaluated before parents -- topological order.
|
|
"""
|
|
match node:
|
|
case NumberNode(value=v):
|
|
return v
|
|
|
|
case UnaryOpNode(op=TokenType.UNARY_MINUS, operand=child):
|
|
return -evaluate(child)
|
|
|
|
case BinOpNode(op=op, left=left, right=right):
|
|
left_val = evaluate(left)
|
|
right_val = evaluate(right)
|
|
match op:
|
|
case TokenType.PLUS:
|
|
return left_val + right_val
|
|
case TokenType.MINUS:
|
|
return left_val - right_val
|
|
case TokenType.MULTIPLY:
|
|
return left_val * right_val
|
|
case TokenType.DIVIDE:
|
|
if right_val == 0:
|
|
raise EvalError("division by zero")
|
|
return left_val / right_val
|
|
case TokenType.POWER:
|
|
return left_val ** right_val
|
|
|
|
raise EvalError(f"unknown node type: {type(node)}")
|
|
|
|
|
|
def evaluate_traced(node):
|
|
"""
|
|
Like evaluate(), but records each step for educational display.
|
|
Returns (result, list_of_trace_lines).
|
|
|
|
The trace shows the topological evaluation order -- how the DAG
|
|
is evaluated from leaves to root. Each step shows a node being
|
|
evaluated after all its dependencies are resolved.
|
|
"""
|
|
steps = []
|
|
counter = [0] # mutable counter for step numbering
|
|
|
|
def _walk(node, depth):
|
|
indent = " " * depth
|
|
counter[0] += 1
|
|
step = counter[0]
|
|
|
|
match node:
|
|
case NumberNode(value=v):
|
|
result = v
|
|
display = _format_number(v)
|
|
steps.append(f"{indent}Step {step}: {display} => {_format_number(result)}")
|
|
return result
|
|
|
|
case UnaryOpNode(op=TokenType.UNARY_MINUS, operand=child):
|
|
child_val = _walk(child, depth + 1)
|
|
result = -child_val
|
|
counter[0] += 1
|
|
step = counter[0]
|
|
steps.append(
|
|
f"{indent}Step {step}: neg({_format_number(child_val)}) "
|
|
f"=> {_format_number(result)}"
|
|
)
|
|
return result
|
|
|
|
case BinOpNode(op=op, left=left, right=right):
|
|
left_val = _walk(left, depth + 1)
|
|
right_val = _walk(right, depth + 1)
|
|
sym = OP_SYMBOLS[op]
|
|
match op:
|
|
case TokenType.PLUS:
|
|
result = left_val + right_val
|
|
case TokenType.MINUS:
|
|
result = left_val - right_val
|
|
case TokenType.MULTIPLY:
|
|
result = left_val * right_val
|
|
case TokenType.DIVIDE:
|
|
if right_val == 0:
|
|
raise EvalError("division by zero")
|
|
result = left_val / right_val
|
|
case TokenType.POWER:
|
|
result = left_val ** right_val
|
|
counter[0] += 1
|
|
step = counter[0]
|
|
steps.append(
|
|
f"{indent}Step {step}: {_format_number(left_val)} {sym} "
|
|
f"{_format_number(right_val)} => {_format_number(result)}"
|
|
)
|
|
return result
|
|
|
|
raise EvalError(f"unknown node type: {type(node)}")
|
|
|
|
result = _walk(node, 0)
|
|
return result, steps
|
|
|
|
|
|
def _format_number(v):
|
|
"""Display a number as integer when possible."""
|
|
if isinstance(v, float) and v == int(v):
|
|
return str(int(v))
|
|
return str(v)
|