# 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
```