11 Mar 2000 13:12:50 -0500

Related articles |
---|

Regex -> DFA question bkubesh@earthlink.net (bkubesh) (2000-03-11) |

Regex -> DFA question uday@cs.unipune.ernet.in (Uday Khedkar) (2000-04-01) |

Re: Regex -> DFA question cfc@world.std.com (Chris F Clark) (2000-04-03) |

From: | bkubesh <bkubesh@earthlink.net> |

Newsgroups: | comp.compilers |

Date: | 11 Mar 2000 13:12:50 -0500 |

Organization: | Road Runner - Texas |

Keywords: | DFA |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.