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

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