How create DFA with multiple finished states for lexers?

Question

Is possible to create DFA directly from regular expression. But for lexical analyse is needed "joined" DFA with many finish states, for example one state for string, one for integers, one for floats etc. How do such DFA? Maybe convert many DFA's to one or join DFA's to one NFA and next convert it to DFA?

Answer 1

As Rick Decker rightly noted, real-world lexical analysers produce a DFA with multiple final states.

Lexical analysers created via Lex-like generators differ from theoretical DFAs in several respects, and this is only one of them. Another obvious difference is that they don't stop at the end of the input string.

Instead, lexical analyser generators generally work as if they ran all DFAs corresponding to the lexer rules in parallel (in practice using a DFA with multiple end states), and applying the following rules:

1. The DFA that "wins" is the one that proceeded the furthest (often called the "maximal munch" rule).

2. If more than one DFA would accept that maximal-length input, the one that occurred first in the specification file "wins" (the disambiguation rule).

The disambiguation rule is used, for example, to distinguish keywords (e.g. if, else, while) from identifiers. Ignoring underscores for the moment, an identifier is (typically) any lexeme that starts with an alphabetic character followed zero or more alphanumeric characters, but isn't a keyword. You could create a regular expression which matches this, but it's much easier to specify keywords before identifiers and let the lexical analyser generator do the disambiguation for you.