Implementing Finite State Machines
Using an Array
The state of finite state machine is a mutable variable.
- State - type denoting states
- Char - denotes symbols of alphabet
Behavior is given by a big array delta
delta : Array[State,Array[Char,State]]
the initial state is q0.
When in state q and reading symbol c, value delta(q)(c) gives new state:
q = delta(q)(c)
So, next state is computed by table lookup.
Final state can be given by a set or an array
F : Array[State,Boolean]
Essentially, we build an interpreter for finite state machine programs
- q0, delta, F - abstract syntax for finite state machine programs
Compiled Finite State Machine
Previous approach describes an interpreter for finite state machines.
What would a compiler look like?
What do compiled finite state machine descriptions look like?
Finite state encoded as program point.
For arbitrary transitions need to jump to arbitrary program counter.
- need general gotos (jumps)
This implicit encoding of state is what we use (at least partly) in manually constructed lexers.