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

Groups > comp.compilers > #2388 > unrolled thread

How make multifinished DFA for merged regexps?

Back to article view | Back to comp.compilers

Contents

  How make multifinished DFA for merged regexps? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-12-20 06:15 -0500

#2388 — How make multifinished DFA for merged regexps?

Andy <borucki.andrzej@gmail.com> 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.
example below
> How to check if r0 and r1 are disjoint?

> For example
> r0 = ab
          ab(F0)
> r1 = ac
           ac(F1)
>    | 0 | 1
> a | 1 |
> b |    | 2(F)
             2(F0)
> c |    | 3(F)
             3(F1)

There are two solutions.

1, Don't just blindly merge your REs, keep the original regex name as
part of the final step.  See, how I indicated it in my tweak to your
example.

2. Don't merge the REs at all, build the final DFA from the REs in parallel.

The easiest way to see how to do that is to do roughly what building
the LR(0) machine does when doing SLR/LALR parsing.  That's a variant
of the subset construction algorithm that does essentially what you
want.   That's how we made Yacc++ do ELR grammars.

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

[toc] | [standalone]

Back to top | Article view | comp.compilers

csiph-web