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>
43 lines
1.5 KiB
Markdown
43 lines
1.5 KiB
Markdown
# Expression Evaluator
|
|
|
|
## Overview
|
|
Educational project teaching DAGs and state machines through a calculator.
|
|
Pure Python, no external dependencies.
|
|
|
|
## Running
|
|
```bash
|
|
python main.py "3 + 4 * 2" # single expression
|
|
python main.py # REPL mode
|
|
python main.py --show-tokens --show-ast --trace "expr" # show internals
|
|
python main.py --dot "3+4*2" | dot -Tpng -o ast.png # AST diagram
|
|
python main.py --dot-fsm | dot -Tpng -o fsm.png # FSM diagram
|
|
```
|
|
|
|
## Testing
|
|
```bash
|
|
python -m pytest tests/ -v
|
|
```
|
|
|
|
## Architecture
|
|
- `tokenizer.py` -- Explicit finite state machine (Mealy machine) tokenizer
|
|
- `parser.py` -- Recursive descent parser building an AST (DAG)
|
|
- `evaluator.py` -- Post-order tree walker (topological sort evaluation)
|
|
- `visualize.py` -- Graphviz dot generation for AST and FSM diagrams
|
|
- `main.py` -- CLI entry point with argparse, REPL mode
|
|
|
|
## Key Design Decisions
|
|
- State machine uses an explicit transition table (dict), not implicit if/else
|
|
- Unary minus resolved by examining previous token context
|
|
- Power operator (`^`) is right-associative (grammar uses right-recursion)
|
|
- AST nodes are dataclasses; evaluation uses structural pattern matching
|
|
- Graphviz output is raw dot strings (no graphviz Python package needed)
|
|
|
|
## Grammar
|
|
```
|
|
expression ::= term ((PLUS | MINUS) term)*
|
|
term ::= unary ((MULTIPLY | DIVIDE) unary)*
|
|
unary ::= UNARY_MINUS unary | power
|
|
power ::= atom (POWER power)?
|
|
atom ::= NUMBER | LPAREN expression RPAREN
|
|
```
|