0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ It depends on the definition of DFA you're using, but many authors allow a DFA to have several final states. $\endgroup$ Dec 20 '19 at 17:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.