Re: How make multifinished DFA for merged regexps?

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

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