On Mon, Mar 05, 2012 at 11:28:24AM -0500, Tom Lane wrote: > Robert Haas <robertmh...@gmail.com> writes: > > I think the right way to imagine this is as though the regular > > expression were being matched to the source text in left-to-right > > fashion. > > No, it isn't. You are headed down the garden path that leads to a > Perl-style definition-by-implementation, and in particular you are going > to end up with an implementation that fails to satisfy the POSIX > standard. POSIX requires an *overall longest* match (at least for cases > where all quantifiers are greedy), and that sometimes means that the > quantifiers can't be processed strictly left-to-right greedy. An > example of this is
On the otherhand, I think requiring an "overall longest match" makes
your implementation non-polynomial complexity. The simplest example I
can think of is the knapsack problem, where given weights x_n and a
total W, can be converted to a regex problem as matching a string with
W a's against the regex:
a{x_1}?a{x_2}?a{x_3}? etc...
Yes, Perl (and others) don't guarentee an overall longest match. I
think they want you to consider regular expressions as a specialised
parsing language where you can configure a state machine to process
your strings. Not ideal, but predicatable.
The question is, what are users expecting of the PostgreSQL regex
implementation?
Have a nice day,
--
Martijn van Oosterhout <klep...@svana.org> http://svana.org/kleptog/
> He who writes carelessly confesses thereby at the very outset that he does
> not attach much importance to his own thoughts.
-- Arthur Schopenhauer
signature.asc
Description: Digital signature
