Regex -> DFA question

My question is very similiar to Paul Johnston's question about a month
ago, but with a twist. When constructing multiple Regex's how does one
handle the following case:


R1 | R2


Where R1=(ab.*cd) and R2=(gh.*ij)


Suppose we process the following input: abghxxcidij


After we have processed the starting sequences, it would seem as though
we need to be able to "cross track" between the two expressions in the
OR. How do I handle this case for R2 in the above example. If I first
construct the NFA using backtracking epsilon transitions and convert to
DFA, I dont see how the DFA will handle this case correctly. It will be
stuck in R1 waiting for a 'd' when it should have accepted the input in
R2.


It seems very likely this problem has already been solved. Am I missing
something?
Thanks in advance,
-bkubesh


> Paul Johnston wrote:
> The problem I have now is that I am failing to translate a *set* of
> regular expression into a lexical analyzer (rather than just one
> regular expression). If I had built this tool going from regex to NFA


> to DFA, rather than straight to a DFA, then this would be solved by
> constructing a new start state s0 and linking to each NFA pattern with


> an epsilon-transition, as shown on the diagram on page 130.

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