Re: POSIX regex subexpression matching semantics

Stefan Monnier <monnier+comp/compilers/news/@flint.cs.yale.edu> wrote:
> I'd thus argue that when `(a*)*' is matched against `bc' the subexpression
> should not match at all (i.e. the outer repetition operator loops 0
> times rather than once).
> And more generally, if the body of a repetition operator can match the empty
> string, it should only match such an empty string if necessary (since
> it will always be possible). Matching the empty string is made necessary
> when there is a minimum number of matches as is the case with `+' and
> with `{n,m}'.


This seems reasonable.


> The rule that subexpressions also should match the longest match is
> often not properly followed by backtracking implementations (i.e.
> all implementations I can think of that allow the use of backreferences.
> I'm actually curious: has anyone tried to extend an NFA or DFA so
> as to allow matching backreferences ?).


There is GNU Rx (a.k.a. librx), which is supposed to comply with the
POSIX regex spec in every way, and seems to follow the longest match
rule quite well. There were still some bugs/misfeatures in version
1.8a when I tried it out, though.


--
http://www.iki.fi/vl/

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