5 ms·
How do you match arbitrarily repeating patterns, which may/probably have a combinatoric expansion, without effectively writing your own parser? If you're using
by Xophmeister 9y ago
How do you match arbitrarily repeating patterns, which may/probably have a combinatoric expansion, without effectively writing your own parser? If you're using a language where writing a parser is relatively easy (e.g., Lisp, Haskell, etc.) or your patterns are trivial, then fair enough. Otherwise, good luck with that.
For example, in Python, if I want to match "foo" followed by any number of "bar"s and/or "quux"s at the end of the string, I could write this:
if re.match(r"foo(bar|quux)*$", my_string):
...
...without going to the trouble writing a recursive-descent parser or state machine, your way would be something like this:
def ends_with_foo_etc(s):
if s.endswith("foo"):
return True
after_last = len(s) - s[::-1].find("oof")
if after_last > len(s):
return False
good_tail = True
while good_tail and after_last < len(s):
if s[after_last:after_last + 3] == "bar":
after_last += 3
elif s[after_last:after_last + 4] == "quux":
after_last += 4
else:
good_tail = False
return good_tail
if ends_with_foo_etc(my_string):
...
That's both excessively terse -- for a really simple pattern -- almost certainly slower and, most importantly, brittle in that it couples your pattern to your implementation in a non-trivial way. If your pattern changes, you may have to completely rewrite your matching function.
It's also worth noting that a typical regex API will do more than just match patterns; e.g., extracting subpatterns/groups, splitting, etc.
- kazinator 9y agoYour implementation seems complicated. The regular expression "foo(bar|quux)*" denotes a set of strings: { "foo", "foobar", "fooquux", "foobarbar", "foobarquux", "fooquuxbar", "fooquuxquux", ... } Since this is anchored to the right, we can look at this from right to left: it's any mixture, including empty, of "quux" or "bar" elements, preceded by "foo". From this, a very simple algorithm pops out: while (string does not end with "foo") { if (string ends with "quux") chop off "quux" from end of string else if (string ends with "bar") chop off "bar" from end of string else return "no match" } return "match"
- Xophmeister 9y agoMy implementation was the first thing that popped into my head. Yours works too (although note that yours will probably reallocate memory every time it chops the end off the string, so it'll be slower). A RD parser or finite state machine would also work. My point was rather that regular expressions are a much better tool for this type of task (see the reasons given at the end of my previous comment). Writing fewer lines of code to do the same job is usually a good idea, providing it remains understandable. Personally, I find the syntax of regular expressions pretty straightforward and a lot of languages even allow you write comments within them to make them even easier to follow.
- deleted 9y ago[deleted]
- jmnicolas 9y agoTo be frank I don't have very complex use cases. But in your example even while not knowing Python I can understand your code. To be sure to truly understand your regex I would need to do a lot of Googling and a lot of thinking. Regexes are not KISS IMO.