第 4 章 · 07 正则的边界:为什么不能匹配配对括号

第 4 章 · 07 正则的边界:为什么不能匹配配对括号

本节摘要:这是第 4 章的收尾节,讲一个常被问的问题:「为什么正则不能匹配配对的括号/嵌套的 HTML 标签?」答案藏在第 01 节的理论里:有限自动机没有「栈」,记不住嵌套深度。本节要把这个边界讲透,并指出:这类问题需要「下推自动机」(带栈的自动机),也就是「上下文无关文法」——这正是第 9 章编译器的领地。所以这一节既是第 4 章的句号,也是通往第 9 章的桥。

内容来源:基于形式语言理论整理的导读。

学习目标

阅读完本节,你应当能够:

1. 说清「正则不能匹配配对括号/嵌套结构」这个事实。
2. 解释根因:有限自动机没有栈,无法记录嵌套深度。
3. 理解「正则语言」属于 Chomsky 分级的第 3 类(最弱),而配对结构属于第 2 类「上下文无关语言」。
4. 说清解决这类问题需要「下推自动机」或「递归下降解析」——第 9 章编译器的领地。

一、学习价值:知道边界才能用对工具

无数新手尝试用正则解析 HTML、匹配嵌套括号、解析 JSON,结果写出脆弱的「看似能用」的正则,在边界情况上崩盘。根本原因:正则的理论能力不足以处理「嵌套结构」。理解这个边界,你才能:

• 不在正则里做它做不到的事(用解析器而非正则解析 HTML/JSON)。
• 理解为什么需要「编译器」这种更强的工具——它处理正则处理不了的嵌套语法。
• 把第 4 章(正则,处理「正则语言」)与第 9 章(编译器,处理「上下文无关语言」)连起来。

二、认知拆解:为什么配对括号匹配不了

问题:配对括号

考虑语言 L = { 所有的括号串,且括号配对 },比如 ()、(())、()()、((())) 都是,但 (、)(、(() 不是。

要用正则匹配,你需要记住「当前未闭合的左括号有几个」——可能 1 个、2 个、N 个。但有限自动机只有有限个状态,无法记住「任意多个」。所以,无论你怎么写正则(\([^)]*\) 之类的尝试),都无法正确匹配任意深度的配对括号——它要么漏匹配深层、要么错匹配不配对的。

根因:有限自动机无栈

第 01 节讲的有限自动机,只有「状态」这一个记忆手段,且状态数有限。匹配配对括号需要「记住嵌套深度」,深度任意——这要求无限种状态(每种深度一种),有限自动机做不到。

Chomsky 分级:正则在能力阶梯的哪一档

Noam Chomsky 把形式语言分成四级,能力递增:

正则(第 3 级)是最弱的——它能匹配线性模式(一行扫过去),但不能匹配嵌套结构。配对括号、算术表达式、JSON 这类「需要数嵌套」的,属于第 2 级「上下文无关语言」,需要下推自动机(带栈的自动机)——栈用来记录嵌套层级,遇到左括号压栈、遇到右括号弹栈。

这意味着什么

处理配对括号、HTML、JSON、代码语法,需要「带栈」的解析器——也就是编译器的「语法分析器」(第 9 章)。所以:

• 正则适合:线性文本模式(日志、表单验证、简单提取)。
• 正则不适合:嵌套结构(HTML、JSON、代码)——用解析器。

三、上手第一步:体会边界

1. 试着用正则匹配 (()()) 这类配对括号,体会它做不到。
2. 想象一个「带栈」的匹配过程:遇 ( 压栈,遇 ) 弹栈,栈空=配对。这是第 9 章解析器的基础。
3. 读第 9 章,看「下推自动机」如何用递归下降实现,处理正则处理不了的嵌套。

本节要点回顾

1. 正则不能匹配配对括号/嵌套结构(HTML、JSON、代码语法)——这是理论边界,非实现缺陷。
2. 根因:有限自动机只有有限状态、无栈,记不住任意嵌套深度。
3. Chomsky 分级:正则(第 3 级)最弱;配对结构属于第 2 级「上下文无关语言」,需带栈的下推自动机。
4. 实践建议:嵌套结构用解析器(编译器技术),别硬用正则。
5. 这是第 4 章到第 9 章的桥:正则处理「线性」,编译器处理「嵌套」——能力阶梯的下一步。

推荐上手顺序

1. 试着用正则匹配配对括号,亲手体会它做不到。
2. 理解「带栈」的解决思路(遇左压、遇右弹)。
3. 进入第 9 章,学习递归下降解析(下推自动机的程序实现)。
4. 至此第 4 章结束——你造了正则引擎,也理解了它的能力边界。

至此第 4 章「造正则引擎」全部讲完。本章从理论(正则=自动机)出发,经 NFA/DFA、Thompson 构造、匹配策略、语法实现、捕获组,落到能力边界。你不仅造了一个正则引擎,更预演了第 9 章编译器的前端思想。下一章我们造文本编辑器——把「匹配文本」升级到「交互式编辑文本」。