Re: How to rewrite a regexp without word boundaries?

dave_140390@hotmail.com wrote:
>>> I have been wondering, with limited success, how to rewrite a regexp
>>> without word boundaries.


> ...I am
> actually writing a tool that takes regexps as input and transforms
> them internally into NFAs/DFAs. ... I don't know how to
> transform a regexp that contains "\b" at an arbitrary position into an
> equivalent NFA/DFA.




I don't think that is possible: that is an additional mechanism on top
of the reg-ex structure.


Formally, let C be the character set, and C* the set of strings (the
free monoid on the set C). Then a language L is a subset of C*. The
regular expressions are operations on subsets of C* that define
languages. If L is a regular expression language, then a string either
matches - it is a subset of L - or it does not.


Now, when used in a regular expression matcher program, one selects a
parsing point in the string and looks at the set of strings of
successive lengths from that point. Usually, the match is the longest of
those strings that are in L. But there is a choice, which does not
depend on L.


So I think you need to implement a mechanism without the NFA/DFA
structure that identifies the \b boundaries.


      Hans

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