Re: How to rewrite a regexp without word boundaries?

Hallvard B Furuseth <h.b.furuseth@usit.uio.no>
Tue, 07 Jul 2009 16:27:50 +0200

          From comp.compilers
Related articles
How to rewrite a regexp without word boundaries? dave_140390@hotmail.com (2009-07-05)
Re: How to rewrite a regexp without word boundaries? h.b.furuseth@usit.uio.no (Hallvard B Furuseth) (2009-07-05)
Re: How to rewrite a regexp without word boundaries? dave_140390@hotmail.com (2009-07-06)
Re: How to rewrite a regexp without word boundaries? haberg_20080406@math.su.se (Hans Aberg) (2009-07-07)
Re: How to rewrite a regexp without word boundaries? h.b.furuseth@usit.uio.no (Hallvard B Furuseth) (2009-07-07)
Re: How to rewrite a regexp without word boundaries? andrew@tomazos.com (Andrew Tomazos) (2009-07-07)
Re: How to rewrite a regexp without word boundaries? cfc@shell01.TheWorld.com (Chris F Clark) (2009-07-13)
Re: How to rewrite a regexp without word boundaries? hu47121@usenet.kitty.sub.org (2009-08-16)
Re: How to rewrite a regexp without word boundaries? dot@dotat.at (Tony Finch) (2009-08-16)
| List of all articles for this month |
From: Hallvard B Furuseth <h.b.furuseth@usit.uio.no>
Newsgroups: comp.compilers,comp.theory
Date: Tue, 07 Jul 2009 16:27:50 +0200
Organization: University of Oslo, Norway
References: 09-07-003 09-07-004 09-07-008
Keywords: lex, DFA
Posted-Date: 10 Jul 2009 18:38:08 EDT

dave_140390@hotmail.com writes:
> I am actually writing a tool that takes regexps as input and
> transforms them internally into NFAs/DFAs.


It's been way too long since I played with NFAs/DFAs, but anyway:
Since you are saying NFA, maybe this a somewhat theoretical exercise
so it's OK to produce one with a godawful number of states. Is the
following possible?


Make a \b-tracking DFA, one which only notices word boundaries.


Make an NFA for your regexp without '\b's, but rewrite it so any jump
from a \b in the regexp is the only jump into the destination state.


Join the two machines (combining all possible states from the two) so
they in effect run in parallel in a big machine. Give \b as additional
input from the 1st submachine to the "coming from \b" states in the 2nd.


--
Hallvard


Post a followup to this message

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