跳到主要内容
把正则画成弹珠轨道,画到最后被一个 `\1` 撑破了

把正则画成弹珠轨道,画到最后被一个 `\1` 撑破了

画唠
画唠

· 阅读约 6 分钟

昨晚刷 HN,看到有人把正则表达式渲染成三维弹珠轨道。珠子顺着管子滚,岔路分开,绕一圈回来,评论区一排“终于看懂了”。

我盯了很久,冒出一个不太合群的念头:这玩意儿画得漂亮,但它画的不是正则,是正则引擎。这是两件事。

把这俩分开,比那张图本身有用。正则没那么玄——玄的是你翻开教程看到的第一样东西。


我第一版图画错了。当时想给“正则是什么”搞个总览,画出来是这样:

   文本 ──► [ 正则 ] ──► true / false
              ?

看了一眼,想把自己关进小黑屋。这跟“函数”有什么区别,黑箱套黑箱,什么也没说出来。

重来。真正的画面是这个:

   c a t s
   ^            游标停在 c 上
   模式: c a t
   ^            对上了,游标往右挪一格

一个游标,从左往右挪,一个字符一个字符地啃。正则的绝大部分,就是“游标在字符串上走”这件事的语法糖。

画开看看:

   字面量   cat       游标依次吃掉 c、a、t
   任意     .         吃掉一个,什么都行
   或       a|b       岔路,两条都试试
   至多一次 x?        吃,或者不吃
   任意多次 x*        一直吃,吃到不想吃
   至少一次 x+        先吃一个,然后同上

整个核心就这几行。评论区有人把正则的基本操作归纳成“或、任意字符、至多一次、任意多次、至少一次”,我看到那条的反应是:对,就这五个,剩下全是标点和习惯。

那为什么大家觉得它玄?因为教程第一页就甩 ^\(?\d{3}\)?[-.\s]?\d{3}[-.\s]?\d{4}$。你让一个刚知道游标是什么的人看这行,他看见的是一堆反斜杠,不是五个算子。顺序该是 cat,再 c.t,再 c(a|u)t,再 c[a-z]t——每一步只加一样新东西。

我自己是从 \S+@\S+\.\S+ 开始学正则的。抄了三年,不知道 \S 是什么意思,只知道邮箱就这么写。这就是跳过游标的账单,到现在还在付。

不过这个游标比喻我也得先标一句:它只有一个方向,只会往前。真引擎不是,它会退回去。这句先记住,等下它要回来咬我。


回到那张三维图。它画的是自动机。圆圈加箭头:

         c          a          t
   (0) ────► (1) ────► (2) ────► ((3))

弹珠轨道就是这张图立起来,加个重力,加个摄像机跟拍。同一个东西,两种投影。

等等等等,先别急,我前面那句“它画的不是正则”说得太满了,收一下。

弹珠轨道对一件事有压倒性优势:回溯。圆圈箭头的图是静态的,你看不到引擎在 a* 上退回去重试。珠子滚回去那个动作,是“回溯”这个词我见过最贴切的视觉化。所以不是圆圈箭头完胜,是各画一半——静态结构看箭头,动态失败看弹珠。

这个比喻漏风的地方也正在这儿:弹珠是物理的,滚下去就是滚下去,有摩擦、有速度、有重力。真引擎没有重力,它在一棵可能性树上做深度优先搜索,哪条路先试、退回来又试哪条,全看实现。珠子滚得优雅,不代表回溯优雅。比喻只帮你抓住“它会退回去”这一层;退回去代价多大,得回来看真实机制。


好,正题来了。我试着把 (a+)\1 画成轨道,卡住了。

不是我不会画,是它画不出来。

前面那五个算子——或、任意字符、至多一次、任意多次、至少一次——再加上分组、字符类、锚点,它们全都落在同一个圈里:有限个状态,有限条边,一张纸画得完。所以轨道搭得出来。

\1 出圈了。它的意思是“回到你刚吃掉的那段,再吃一遍一模一样的东西”。要判断“一模一样”,轨道得记住刚才吃了多长、吃的是什么:

   (a+) 吃下 n 个 a ──► 轨道得记住 "n 是几、吃的是不是 a"
                          ↑
                    这一格不是圆圈,是一个无界的账本

无界的东西画不成有限状态图。这不是懒,是它真不在那个类里。所以有些引擎干脆不支持反向引用;支持它的,最坏情况匹配时间会退到指数级——嵌套量词叠起来那种写法,你去跑一下就知道,CPU 是真的会卡在那儿转圈,不是比喻。

✨ 就是这里,咔哒一下扣上了。轨道图这么酷却盖不住全部正则、某些引擎的实现选择为什么长这样、“我这条正则跑得好慢”为什么是个有答案的问题——一个 \1 全解释完了。

顺便区分一个被混得最狠的东西:捕获组本身没这个问题。捕获组只是“把匹配到的那段存起来给你用”,存完拉倒,不参与后面的匹配判定。只有反向引用——拿存下来的东西反过来约束匹配——才掉下去。这俩我混了很多年,混的时候还觉得自己挺懂。


可读性那段评论区吵得挺热。有人主张正则天生不可读,应该换成带标签的结构化写法。

我不太买账。不是他错,是 verbose 模式、命名捕获组、注释这些东西早就在引擎里躺着了,只是没人教。(?<area>\d{3}) 比 (\d{3}) 好读一百倍——但你得先知道有这回事。所以问题又绕回教学顺序。至于那些替代的匹配工具和语法,我熟的只有一两个,不乱评。

还有个题外话挺好笑的:发帖那位说这工具是拿 Agent Duel 造的,自己公司正在做那套系统,拿兴趣项目测 bug。一个专门帮人看懂机器怎么执行的工具,本身是机器写出来的。我不觉得这有什么可感慨的,就是觉得这个回路挺逗——绕一圈,机器帮人画图,教人看懂机器。

评论区另有人抱怨输入框只吃 301 个字符,还有位希望给弹珠加声音和跟随镜头。301 这个数很具体,我怀疑是某个默认值一直没改。


画开完了。老规矩自检一下:现在你能不能只用“游标在字符串上走”这一个画面,把 .、*、+、?、| 五个全解释一遍?解释不了的,就是那儿还没画开。

下期想画哪个?我手上有张没画顺的草图:DFA 和 NFA 到底差在哪、为什么实际实现大多往 NFA 那侧跑。中间那个子集构造,我到现在画得还别扭。

一个 \1,把整张轨道图撑破了。这玩意儿真的太酷了。

画唠
画唠

把被讲玄的概念用图 + 比喻 + 动手实验拆到咔哒扣明白,错的也保留。

查看主页 →