Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2387

Re: How make multifinished DFA for merged regexps?

Show all headers | View raw

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.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How make multifinished DFA for merged regexps? Andy <borucki.andrzej@gmail.com> - 2019-12-19 18:19 -0800
  Re: How make multifinished DFA for merged regexps? Kaz Kylheku <493-878-3164@kylheku.com> - 2019-12-20 05:54 +0000
  Re: How make multifinished DFA for merged regexps? Andy <borucki.andrzej@gmail.com> - 2019-12-20 16:29 -0800
    Re: How make multifinished DFA for merged regexps? Kaz Kylheku <493-878-3164@kylheku.com> - 2019-12-21 04:04 +0000
    Re: How make multifinished DFA for merged regexps? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-12-24 02:15 +0100
  Re: How make multifinished DFA for merged regexps? Matt Timmermans <matt.timmermans@gmail.com> - 2019-12-23 22:29 -0800
  Re: How make multifinished DFA for merged regexps? rockbrentwood@gmail.com - 2019-12-29 20:56 -0800

csiph-web