Re: How make multifinished DFA for merged regexps?

Path	csiph.com!xmission!news.snarked.org!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	Matt Timmermans <matt.timmermans@gmail.com>
Newsgroups	comp.compilers
Subject	Re: How make multifinished DFA for merged regexps?
Date	Mon, 23 Dec 2019 22:29:57 -0800 (PST)
Organization	Compilers Central
Lines	26
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<19-12-028@comp.compilers> (permalink)
References	<19-12-005@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset="UTF-8"
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="26605"; mail-complaints-to="abuse@iecc.com"
Keywords	lex, DFA
Posted-Date	25 Dec 2019 21:22:49 EST
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
In-Reply-To	<19-12-005@comp.compilers>
Xref	csiph.com comp.compilers:2409

Show key headers only | 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