How is maximal-munch implemented?

The maximal munch algorithm is implemented by adding a small amount of mutable state to the DFA executor, and adding the ability of the DFA executor to "rewind" the input: in effect, providing it with functions like tell() and seek().

It's also worth noting that the DFA is not complete, in the sense that the transition function is not complete. Some {state, input} pairs do not have a defined result. [Note 2]

With that in mind, the algorithm is as follows:

Set Accepted NFA State to ⊥Set Accepted Position to Tell(Input Stream)Set State to Starting StateRepeat:  If State ∈ Accepting:    Set Accepted NFA State to Accepting NFA State for State  [Note 1]    Set Accepted Position to Tell(Input Stream)  Read one symbol from Input Stream into Next Symbol  If there is a transition from {State, Next Symbol} to New State:    Set State to New State    Continue the loop  Otherwise:    Rewind Input Stream to Accepted Position    Return Accepted NFA State

If the algorithm returns ⊥, then no token was recognized and the input stream will have been rewound to the initial position.

Notes:

1. The NFA typically has an unambiguous homomorphism between states and accepting actions, but the DFA construction algorithm may combine two accepting NFA states with different actions. In this case, the flex algorithm is to give priority to the first action in the input file. In the above algorithm, we represent this by mapping each accepting DFA state to the component accepting NFA state which has priority.

2. It's easy to make the DFA complete by adding an additional (and unique) sink state which is non-accepting and which only has transitions to itself. Then we can add the sink state as a transition for any otherwise unspecified transition. If we call the sink state ⊥ then it will be clear how to modify the algorithm provided; in practice, this isn't at all necessary because in practice we don't care that the DFA is incomplete. It does have some impact on state minimization algorithms, though.