TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

The Greatest Regex Trick Ever (2014)

227 点作者 user_235711超过 9 年前

24 条评论

wonnage超过 9 年前
Regular expressions match regular languages (hence the name). If your language involves pairs of things (e.g HTML), it&#x27;s not regular. Perl hacked support for this in via backreferences and other extensions, but these are slow and illegible. Use a proper context-free grammar parser if you need to parse a context free grammar, you know?<p>More broadly, people fear and misunderstand regexes because they have no idea how they work. It becomes much easier if you understand how they map to deterministic finite state machines. Recommended reading: <a href="https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp1.html" rel="nofollow">https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp1.html</a><p>Once you understand how they work, you can basically read a regex left to right and intuitively know all the strings they&#x27;d match. There is no such thing as an unmaintainable&#x2F;illegible basic regex - they&#x27;re just words with some placeholders in them - it&#x27;s when you cram in extended functionality (which is basically a programming language where all the keywords are single characters) that shit hits the fan.
评论 #10282632 未加载
评论 #10282802 未加载
评论 #10283195 未加载
评论 #10282751 未加载
评论 #10283148 未加载
评论 #10282643 未加载
评论 #10283177 未加载
评论 #10282627 未加载
评论 #10284175 未加载
JoeCoder_超过 9 年前
Here is the <i></i>TL;DR<i></i>. This regex matches Tarzan but not &quot;Tarzan&quot;:<p><pre><code> &quot;Tarzan&quot;|(Tarzan) </code></pre> You can also include more than one case of what you don&#x27;t want to match. This one also finds only the cases of Tarzan that don&#x27;t match the first three patterns:<p><pre><code> Tarzania|--Tarzan--|&quot;Tarzan&quot;|(Tarzan) </code></pre> You can even use more complex regexes. This matches all words not in an image tag:<p><pre><code> &lt;img[^&gt;]+&gt;|(\w+) </code></pre> And likewise this matches anything not surrounded by &lt;b&gt; tags:<p><pre><code> &lt;b&gt;[^&lt;]*&lt;&#x2F;b&gt;|([\w\s]+)</code></pre>
评论 #10283482 未加载
评论 #10283723 未加载
singingfish超过 9 年前
I once used the wonderful perl module [Regexp::Assemble](<a href="https:&#x2F;&#x2F;metacpan.org&#x2F;pod&#x2F;Regexp::Assemble" rel="nofollow">https:&#x2F;&#x2F;metacpan.org&#x2F;pod&#x2F;Regexp::Assemble</a>) to produce a regexp to match [every single suburb&#x2F;town name in Australia](<a href="https:&#x2F;&#x2F;gist.githubusercontent.com&#x2F;singingfish&#x2F;d43c884fbac0089d8523&#x2F;raw&#x2F;63eeaf88a2e8d896c07da3b2440080233dd48395&#x2F;regex%2520for%2520every%2520suburb%2520name%2520in%2520australia.txt" rel="nofollow">https:&#x2F;&#x2F;gist.githubusercontent.com&#x2F;singingfish&#x2F;d43c884fbac00...</a>) from a csv file download from the post office website. It was blazingly fast ... considering (better than the recdescent parser I&#x27;d been previously experimenting with).<p>Here&#x27;s the code that generated the regex:<p><pre><code> use Regexp::Assemble; my $ra = Regexp::Assemble-&gt;new; while (&lt;$FH&gt;) { $csv-&gt;parse($_); next if $. == 1; my @fields = $csv-&gt;fields; $ra-&gt;add($fields[1]); } my $suburbs = $ra-&gt;as_string;</code></pre>
评论 #10282335 未加载
bza超过 9 年前
This technique is unreliable in practice, and the author&#x27;s discussion is confused.<p>First, their explanation doesn&#x27;t make sense. They&#x27;re supposing that there&#x27;s some determinacy in the order in which a matcher can be expected to examine the different possible matches. But that&#x27;s provably not the case: if it were, then deterministic and non-determinsitic finite automata would be inequivalent.<p>But the technique in question does seem to require some determinacy as to which of several alternatives will match against a string. Where does that determinacy come from? The semantics of the alternation operator (the &#x27;|&#x27;) as usually formulated don&#x27;t specify any preference among alternations. For that reason, POSIX <i>additionally</i> requires that a matcher return the longest possible match (and if there are several such, the leftmost is what must be returned). Where you do find an explicit guarantee concerning which of several different possible ways of matching will be preferred, it&#x27;s almost certainly because the engine is aiming at POSIX compliance.<p>Such compliance has a significant cost, though, as it requires the matcher to consider <i>all</i> possible matches (in order to find the largest). For that reason, most regex engines forego strict POSIX compliance and only guarantee that some match will be returned if one exists, not that that match will be the leftmost longest. Some engines offer the option of requesting strict POSIX behavior, but the default will always be to eagerly return the first match encountered (and recall the point above that there provably can&#x27;t be a guarantee about the order in which matches are encountered, in general).<p>You should never do this in production code unless you&#x27;re sure that your matcher is POSIX-compliant.
edoloughlin超过 9 年前
I almost wrote this off as it seemed to be about how to write unmaintainable regex soup but the author pulled something quite elegant out of the hat at the end.
leeoniya超过 9 年前
this one is great, too. matches all printable ascii characters:<p>[ -~]<p><a href="http:&#x2F;&#x2F;www.catonmat.net&#x2F;blog&#x2F;my-favorite-regex&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.catonmat.net&#x2F;blog&#x2F;my-favorite-regex&#x2F;</a>
评论 #10282424 未加载
smegel超过 9 年前
&gt; Match Tarzan but not &quot;Tarzan&quot;<p>Unfortunately it doesn&#x27;t work.<p>Let&#x27;s say I wanted to match a string following Tarzan but not &quot;Tarzan&quot;, I will try his technique:<p><pre><code> (&quot;Tarzan&quot;|(Tarzan))\s+and JillOfTheJungle </code></pre> Unfortunately this matches both:<p><pre><code> &quot;Tarzan&quot; and JillOfTheJungle </code></pre> and<p><pre><code> Tarzan and JillOfTheJungle </code></pre> Or maybe he meant:<p>&gt; Capture Tarzan but not &quot;Tarzan&quot;
评论 #10282435 未加载
评论 #10283165 未加载
rntz超过 9 年前
This &quot;trick&quot; is simply exploiting a bug in regex implementations.<p>The regex<p><pre><code> &quot;Tarzan&quot;|(Tarzan) </code></pre> should match the string<p><pre><code> &quot;Tarzan&quot; </code></pre> in <i>two</i> ways: first, matching the entire string; and second, matching the substring &quot;Tarzan&quot; in the whole string &quot;\&quot;Tarzan\&quot;&quot;. But most regex implementations drop extra overlapping matches. I argue this is incorrect behavior, because it complicates understanding what a regex <i>means</i> - you have to understand the &#x2F;order&#x2F; in which your regular expression matcher interprets your regular expression, which is an implementation detail. I conjecture that a DFA-based regex engine would not be able to exhibit this order-biased behavior, at least not with the standard approach.<p>However, it&#x27;s interesting that this &quot;bug&quot; turns out to be a &quot;feature&quot; for the case of excluding other behavior. I&#x27;m not sure what conclusion to draw from this.
评论 #10284495 未加载
aaronbrethorst超过 9 年前
This article desperately needs a tl;dr, but major props for the two regex tricks at the very top of the page.
userbinator超过 9 年前
That reminds me of something else with regex which I thought was extremely clever: implementing an A* search: <a href="http:&#x2F;&#x2F;realgl.blogspot.com&#x2F;2013&#x2F;08&#x2F;battlecode.html" rel="nofollow">http:&#x2F;&#x2F;realgl.blogspot.com&#x2F;2013&#x2F;08&#x2F;battlecode.html</a>
评论 #10283732 未加载
incepted超过 9 年前
Meh.<p>I think an even greater Regexp trick is the regular expression that determines primality:<p><a href="http:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;3296050&#x2F;how-does-this-regex-find-primes" rel="nofollow">http:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;3296050&#x2F;how-does-this-reg...</a>
评论 #10283503 未加载
smsm42超过 9 年前
Very nice trick, while using of foo|(bar) is very simple, somehow I don&#x27;t see such approach being used very often, and it looks like it could simplify a number of things.
rbobby超过 9 年前
Maybe I&#x27;m too old. I tend to think of a regex as either matching or not matching.<p>Finding a bit of code that uses a capture to determine whether a match was found seems like it would easily be confusing&#x2F;inobvious.<p>Some pretty clear commenting and it would be ok... maybe.<p>Also... I wonder how well it would work as part of a larger regex, one that already uses captures (or non-capturing groups)? The examples are all nice, short and sweet... but how often do regex based solutions stay short and sweet? A few maintenance cycles&#x2F;years and suddenly you&#x27;ve got this funky regex&#x2F;capture thing that only Bob understands and he&#x27;s way to busy to talk to you for 5 minutes... and once you change things then Bob suddenly finds time to review your code to complain how you broke it for such a simple change. There goes your bonus you told the wife you were sure to get so you could take her and the kids on vacation. The day after your divorce finalized Bob sends you a fix request to use that improved scheme of yours because the old regex one isn&#x27;t flexible enough anymore.
forrestthewoods超过 9 年前
I thought the answer was going to be &quot;tricking the world into thinking regex was a good idea&quot;. I&#x27;ve always considered regex to have the rare and elusive &quot;write only&quot; flag. Write only. As opposed to read only. Because once you write a regex that&#x27;s it. You will never know what it does ever again.
评论 #10282471 未加载
评论 #10282840 未加载
评论 #10282352 未加载
评论 #10282303 未加载
评论 #10282405 未加载
评论 #10282308 未加载
评论 #10282457 未加载
评论 #10282584 未加载
brey超过 9 年前
Very elegant, I like it.<p>Except I&#x27;m now having a major case of semantic satiation for the word &quot;Tarzan&quot;...
chris_wot超过 9 年前
I love regexes but they make my head hurt. I really rather badly need to spend some time properly learning it inside and out.
评论 #10283013 未加载
bro-stick超过 9 年前
Unimpressive. The author of this article obviously didn&#x27;t have a compiler class where one learns how regexes are basically glorified NFAs that are deterministicly convertible into a much more efficient DFA state machines (read: PCRE JIT), instead of assuming regexes are processed by O(N^2) algorithms.
评论 #10283704 未加载
wodenokoto超过 9 年前
Generally I found it strange how difficult it is to do a search for everything except something.<p>The script looks elegant, but like the author mentions, doesn&#x27;t work in a text-editor, so I would consider it the greatest.
评论 #10282639 未加载
amluto超过 9 年前
How does this handle &#x27;&quot;Tarzan&quot; Tarzan&#x27;?
jfb超过 9 年前
Convincing the world that they don&#x27;t exist?
logn超过 9 年前
More like the author tricked you by changing the problem halfway through the very long article. Try this instead:<p><pre><code> (?:(?&lt;!&quot;)|(?!Tarzan&quot;))Tarzan</code></pre>
jwhite超过 9 年前
... and now you have two problems.
pkaye超过 9 年前
Reminds me of this quote from Jamie Zawinski: &quot;Some people, when confronted with a problem, think &quot;I know, I&#x27;ll use regular expressions.&quot; Now they have two problems.&quot;
评论 #10283154 未加载
评论 #10283111 未加载
edward超过 9 年前
Parsing HTML with a regex? You should read this answer on Stack Overflow: <a href="http:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;1732454&#x2F;84250" rel="nofollow">http:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;1732454&#x2F;84250</a>