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

Groups > comp.compilers > #2388

How make multifinished DFA for merged regexps?

Show all headers | View raw

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
------------------------------------------------------------------------------

Back to comp.compilers | Previous | Next | Find similar

Thread

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

csiph-web