算法与计算机科学cs.princeton.edu编辑精选
一个正则表达式匹配器（2007）
A Regular Expression Matcher (2007)
2011 — 2022，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是《Beautiful Code》第一章的网页版：Brian Kernighan 用一个很短的 C 正则表达式匹配器，展示如何通过递归和尽早处理特殊情况，把匹配逻辑写得紧凑而清晰。它主要是一则编程风格与算法示例，而不是完整的正则引擎教程；读者常把它当作理解解释器、特化与现代正则实现的起点。
为什么经久不衰：它短到可以一口气读完，却把递归、特殊情况和 C 指针技巧讲得具体，是几十年后仍适合用来学习“优雅代码”和正则实现起点的经典范例。
HN 评论精选
代码是优秀编程范例，重点在递归与特殊处理；正则原理需另读 Russ Cox。
我很佩服。这段代码确实达到了“优秀编程示例”的目标。正如 Kernighan 所说，它体现了尽早处理特殊情况与递归的价值。（它也是指针运算和以 NUL 结尾字符串用法的好例子，不过这点还是少说为妙。）学生很可能注意不到尾递归，所以把它改成迭代版本是个不错的练习。但要注意，解释正则表达式并不是这个示例的目标；这里有一个底层状态机（由指令指针和 `text` 变量的组合编码），但并不明显。想理解那部分，Russ Cox 的文章是首选。
adrianratnapala查看英文原文
I'm impressed. The code lives up to its goal of being a good example of programming. As Kernighan says, it shows the value of handling special cases early and of recursion. (It's also a good example of how pointer-arithmetic and nul-terminated strings should be used, but the less said about that, the better). Students are likely to not notice the tail recursion, so converting this to an iterative version is probably a nice exercise. But notice that explaining regexps is a non-goal of this example. There is an underlying state-machine here (encoded in a combination of the instruction pointer and the `text` variable), but it is not very obvious. For that, Russ Cox' articles are the go-to.
可用它讲解解释器到编译器的 staging/特化。
这是一段很漂亮的代码。我喜欢用它来解释如何通过 staging/特化把解释器变成编译器：https://scala-lms.github.io/tutorials/regex.html
tiarkrompf查看英文原文
It's a nice piece of code. I like to use it to explain how to turn interpreters into compilers through staging/specialization: https://scala-lms.github.io/tutorials/regex.html
这是历史经典，但现代正则实现已远超早期 Thompson 方案，需读更多文献。
这些文章作为历史资料很棒，但正则表达式实现早已从早期 Thompson 式实现（无论回溯还是 NFA）大幅演进。关于正则实现已有大量文献，包括许多很有说服力的实现和替代表述，其中一些甚至不是贝尔实验室的人或出自贝尔实验室的人做的！我们似乎正在经历正则实现知识的“永恒九月”（Russ Cox 在介绍 RE2 的文章里那份异常精挑细选的参考书目也助长了这一点）。
glangdale查看英文原文
These posts are great for history, but regular expression implementation has moved on considerably from early Thompson implementations whether backtracking or NFAs. There is a considerable body of literature about regex implementation, including many quite convincing implementations and alternate formulations, some of which weren't even done by people at, or from, Bell Labs! We seem to have something of an Eternal September of regex implementation knowledge (abetted by Russ Cox's amazingly selective bibliography in his posts introducing RE2).
出处是《Beautiful Code》第一章。
这是《Beautiful Code》第 1 章（http://shop.oreilly.com/product/9780596510046.do）。
adriantam查看英文原文
This is chapter 1 of "Beautiful Code" (http://shop.oreilly.com/product/9780596510046.do)
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选