How is maximal-munch implemented?

Question

I am studying compilers and am learning about lexical analysis. I understand that one specifies each lexeme as a regular expression, and using flex, a lexer can be automatically generated. I am further learning about how the regular expression is converted to an NFA which is then converted to a DFA, where it can be quickly evaluated.

However, my question is, how is the maximal-munch rule implemented? Internally, how does the lexer know to "keep going" to find the longest possible lexeme?

Thanks!

Answer 1

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 State
Repeat:
  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.