StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Very interesting question. In my quick search, I didn't find anything predefined (not even in Perl) that solves this problem.</p> <p>EDIT: Ouch, it seems Java has something similar called hitEnd() -- see Alan M's answer. What hitEnd() does is say that the result of match() (either true or false) might be modified by additional input. The book 'Mastering Regular Expressions" says it's not very reliable though (not sure why, page 392 not available in google books).</p> <p>Depending on what features of regular expressions you use, a quick hack like writing some sort of prefixes of your regexp:</p> <p>e.g. for a+a*b+c your prefixes will be:</p> <pre> a+ a+a* a+a*b+ a+a*b+c </pre> <p>and try to match any of them with your string might work. This quick hack is made difficult if you use the choice operator, if you use the range operator {n,m} or back-references.</p> <p>That being said, I think the good solution is to slightly modify the matching algorithm. </p> <p>The matching algorithm normally employed is a backtracking algorithm (which works well in practice, even if worst case behavior is exponential). This algorithm successfully terminates whenever it has reached the end of the regexp (even if not the entire string was consumed). What you need to do is to modify the termination condition such that it also terminates successfully when it has consumed all of the input.</p> <p>That being said, you'd probably have to actually implement the algorithm in JavaScript. Hopefully this will become part of libraries such as Jquery.</p> <p>For more references and theory on the algorithm, check this article out:</p> <p><a href="http://swtch.com/~rsc/regexp/regexp1.html" rel="nofollow noreferrer">http://swtch.com/~rsc/regexp/regexp1.html</a></p> <p>(even if it makes a case against the backtracking algorithm and suggests a FA based algorithm (but the FA cannot handle back-references)).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload