Languages & Interpreters

A machine whose only memory is which state it is in: one table lookup per symbol, accept if it ends on a double ring, then merge the states no word can tell apart.

A regular expression compiles to a machine with one state per letter that runs in many states at once; turning each set of states into one state gives a DFA.

A grammar becomes a program: one method per rule, one token of lookahead per decision, and a tree comes out whose shape is the precedence of the operators.

Run a program by walking its syntax tree: visit a node, evaluate its children, act on their values. The tree is the program, and a loop is the walk coming back to the same node.

Compile the tree once into postfix instructions and run them with a stack: fetch, advance, execute. A loop is a jump backwards, and nothing is matched on its kind again.