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

Groups > comp.compilers > #2409

Re: How make multifinished DFA for merged regexps?

Show all headers | View raw

On Thursday, 19 December 2019 23:01:24 UTC-5, Andy  wrote:
> I can create DFA direct from regexp.
> But for language lexer I must have DFA for couple regexp.
> One solution is crating DFA with multi finished states.
> For example
> r0 = ab
> r1 = ac
>
>   | 0 | 1
> a | 1 |
> b |   | 2(F)
> c |   | 3(F)
>
> How to check if r0 and r1 are disjoint?

You build the NFA with a different kind of accepting state for each
rule.  When you build the DFA with subset construction, each DFA state
will correspond to a set of NFA states, and therefore each accepting
state will correspond to a *set* of rules.

The rules are all disjoint if all those sets are singletons.

If you do Hopcroft minimization, then your initial partition puts each
distinct set of accepted rules in its own partition.

I have an open source project that does this if it helps: https://github.com/mtimmerm/dfalex

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