Re: How make multifinished DFA for merged regexps?

Matt Timmermans <matt.timmermans@gmail.com>
Mon, 23 Dec 2019 22:29:57 -0800 (PST)

          From comp.compilers

Related articles
How make multifinished DFA for merged regexps? borucki.andrzej@gmail.com (Andy) (2019-12-19)
Re: How make multifinished DFA for merged regexps? 493-878-3164@kylheku.com (Kaz Kylheku) (2019-12-20)
How make multifinished DFA for merged regexps? christopher.f.clark@compiler-resources.com (Christopher F Clark) (2019-12-20)
Re: How make multifinished DFA for merged regexps? borucki.andrzej@gmail.com (Andy) (2019-12-20)
Re: How make multifinished DFA for merged regexps? 493-878-3164@kylheku.com (Kaz Kylheku) (2019-12-21)
How make multifinished DFA for merged regexps? christopher.f.clark@compiler-resources.com (Christopher F Clark) (2019-12-23)
Re: How make multifinished DFA for merged regexps? DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2019-12-24)
Re: How make multifinished DFA for merged regexps? matt.timmermans@gmail.com (Matt Timmermans) (2019-12-23)
Re: How make multifinished DFA for merged regexps? christopher.f.clark@compiler-resources.com (Christopher F Clark) (2019-12-24)
Re: How make multifinished DFA for merged regexps? rockbrentwood@gmail.com (2019-12-29)
| List of all articles for this month |

From: Matt Timmermans <matt.timmermans@gmail.com>
Newsgroups: comp.compilers
Date: Mon, 23 Dec 2019 22:29:57 -0800 (PST)
Organization: Compilers Central
References: 19-12-005
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
In-Reply-To: 19-12-005

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


Post a followup to this message

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