编程与软件工程nikic.github.io
正则表达式的真正威力（2012）
The true power of regular expressions (2012)
2013 — 2018，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章深入讲解 PCRE（带回溯的正则引擎）与形式语言理论中“正则表达式”的区别：PCRE 因支持回溯和反向引用，表达能力远超正则语言，甚至可以用来解 NP 完全问题（如 3-SAT）。作者通过把正则匹配编码为 NP 完全问题，展示了这种“实用正则”的真实计算能力与潜在风险。
为什么经久不衰：它澄清了一个流传甚广的概念混淆——工程中的 regex 与理论上的正则语言根本不是一回事，这种理解对避免灾难性回溯等实际问题至今仍然关键。
HN 评论精选
实践中的 regex 已远超理论正则文法，两者同名但内涵不同
我觉得这是计算机科学作为数学分支与“编程开发”这种应用计算机科学之间的一个有趣副作用。我记得入学前参观学校计算机系时，有学生在讨论是否存在检测素数的正则表达式。我当时暗自好笑——因为在我心目中那根本不是正则表达式该干的事。结果还真有这样的正则表达式。实践中的正则表达式既涵盖学术上的 3 型正则文法，也包含一堆因实际应用有用而附加进去的东西。
Fripplebubby查看英文原文
I find this to be an interesting side effect of computer science as a branch of mathematics vs applied computer science in "programming" and "development". I remember touring the computer science building at the university I would end up attending before I had enrolled there - some students in one room were discussing whether there was a regular expression for detecting prime numbers. I laughed to myself - because in my mind, that's not at all what a regular expression was. Sure enough, there is in fact such a regular expression (or "regex pattern", if you prefer)[1]. Regular expressions in practice encompass BOTH the academic level-3 regular grammar stuff, and a bunch of other stuff that's been tacked on because it's useful in real-world applications. [1] - This has been posted on HN before, probably a bunch of times: https://iluxonchik.github.io/regular-expression-check-if-number-is-prime/
PCRE 与形式正则表达式机制和复杂度完全不同，不应混为一谈
我一直不理解软件工程界为什么仅仅因为 PCRE 语法与“形式”正则表达式相似，就把它也叫正则表达式。两者有充分理由区分开，因为特性完全不同：PCRE 可能使用无界的额外内存和指数级时间；形式正则表达式只需线性时间和内存，且只能匹配正则语言。它们的工作机制完全不同（一个是有穷自动机，一个是基于栈的模式匹配器）。正则表达式不能匹配 HTML，PCRE 可以。混淆两者没有好处。
alipang查看英文原文
I've never understood the software engineering community's desire to call PCREs regular expressions simply because it has similar syntax to "formal" regular expressions. There is good reason to distinguish the two, since they have completely different characteristics. PCREs may use an unbounded amount of extra memory, and may use exponential time. "Formal" regular expressions take linear time and memory, and can match only the regular languages. They operate completely differently (a regular automation vs. a stack based pattern matcher). Regular expressions can NOT match HTML, PCREs CAN. Conflating the two is not helpful.
文章真正揭示的是混淆两者带来的危险
换个标题的话：混淆正则表达式与回溯模式匹配器的真正危险。不知道还能不能重新引入这种区分。
plesner查看英文原文
Alternative title: the true danger of conflating regular expressions and backtracking pattern matchers. I wonder if it would be possible to reintroduce that distinction.
比 NP 完全更难的问题也存在，如 PSPACE 完全问题
“如果有人找到了 NP 完全问题的快速解法，人类几乎所有计算难题就一举解决了”——其实还有很多（可能）比 NP 完全更难的有趣计算难题，比如 PSPACE 完全问题，例如求解国际象棋，或者更切题的：判断某个正则表达式是否生成某字母表上的所有字符串。
FartyMcFarter查看英文原文
> So if somebody found a fast solution to a NP-complete problem, pretty much all of the computationally hard problems of humanity would be solved all in one strike. There are plenty of interesting computationally hard problems that are (probably) harder than NP-complete problems, e.g. PSPACE-complete problems. For example solving chess, or more on topic, the problem of "does this regular expression generate all strings over this alphabet"?
并非所有正则库都偏离理论，如 re2 基于有穷自动机
PCRE 确实被广泛使用，但也有一些正则库没有偏离形式正则语言理论太远，最著名的是基于有穷自动机引擎的 Google re2。
zokier查看英文原文
While true that PCRE is widely used, it is also true that there are several regexp libraries that do not veer very far from the formal regular language theory. Most notably Googles re2 which is based on finite automation engine.
历次讨论
同类还值得读
开源应用架构
The Architecture of Open Source Applications
《开源软件架构》（AOSA）是一本在线免费书，邀请知名开源项目的作者亲自剖析其内部设计，涵盖 SQLAlchemy、LLVM、Audacity、Apache、Bash 等系统。
编程与软件工程上首页 9 次 · 2011–2024aosabook.org编辑精选编程语言简史：简短、不完整且多半错误
A Brief, Incomplete, and Mostly Wrong History of Programming Languages
一篇以戏谑、故意不准确的方式回顾编程语言史的博客文章，用夸张轶事和讽刺定义串起 Lisp、C、C++、Java、JavaScript、PHP 等语言。
编程与软件工程上首页 8 次 · 2009–2021james-iry.blogspot.comSQLite 是如何测试的
How SQLite is tested
SQLite 官方文档页，系统介绍 SQLite 的测试体系：多种测试方法（TCL 测试、模糊测试、回归测试、静态分析等）和海量测试用例，展示了这个小型开源项目如何靠极致测试获得…
编程与软件工程上首页 8 次 · 2009–2025sqlite.org编辑精选高级编程语言（2009）
Advanced programming languages (2009)
Matt Might 的经典文章，按用途推荐“高级编程语言”：如果追求就业就选主流语言，如果追求表达力、学术研究或创业，则推荐 Haskell、OCaml、Scala 等函数式语…
编程与软件工程上首页 8 次 · 2009–2022matt.might.net我的 Forth 与栈机器经历
Yosefk - My history with Forth & stack machines
作者以亲身经历回顾了使用 Forth 语言和栈式机器的历程：既赞叹其简洁优雅、代码量小、可自举的优点，也坦率指出栈操作在实际编程中的痛苦，以及 Forth 社区文化中的问题。
编程与软件工程上首页 8 次 · 2010–2024yosefk.com编辑精选