Re: How make multifinished DFA for merged regexps?

On 2019-12-20, Andy <borucki.andrzej@gmail.com> wrote:
> I can create DFA direct from regexp.
> But for language lexer I must have DFA for couple regexp.


These are just combined as if with |, in some way that retains the
association between acceptance states an rules.


If we go NFA to DFA, what we can do is compile the individual regexes to
NFA, and then combine them into a big NFA. Each of the little baby
NFA's has its own NFA acceptance state(s), We associate those state with the
original regex rule.


When we go to DFA, we are now looking at subsets of NFA states. A state
of the DFA is a set of the states of the NFA.


Thus a DFA state can potentially contain one or more NFA acceptance
states. Since those NFA states are each associated with a lexer rules,
that means that, transitively, a DFA acceptance state is associated with
one or more rules.


If a DFA acceptance state is associated with more than one rule, we can
trim away all but the topmost rule. When that state occurs (that token
is matched) we trigger the first rule, ignoring the others.
That's how it is in Lex: if two or more rules match the same input, the
first rule appearing in the Lex program dominates.


Furthermore, after trimming away the superfluous rules, we can identify
all rules that are then no longer attached to the DFA and warn the
programmer about them.

Return to the comp.compilers page.
Search the comp.compilers archives again.