提问人：mac 提问时间：7/20/2011 最后编辑：philipxymac 更新时间：8/7/2023 访问量：39272
为什么不能使用正则表达式来解析 HTML/XML：通俗易懂的正式解释
Why it's not possible to use regex to parse HTML/XML: a formal explanation in layman's terms
问：
在 SO 上，没有一天没有关于解析 （X）HTML 或 XML 的问题，并被问到正则表达式。
虽然想出一些例子来证明正则表达式对于这项任务的不可行性，或者用一组表达式来表示这个概念是相对容易的，但我仍然无法在 SO 上找到一个正式的解释，说明为什么这不可能用外行的话来完成。
到目前为止，我在这个网站上能找到的唯一正式的解释可能非常准确，但对于自学成才的程序员来说也相当神秘：
这里的缺陷是 HTML 是 Chomsky Type 2 语法（上下文无关） grammar） 和 RegEx 是 Chomsky Type 3 语法（正则表达式）
或：
正则表达式只能匹配正则语言，但 HTML 是 与上下文无关的语言。
或：
有限自动机（这是常规数据结构 expression） 除了它所处的状态之外没有内存，并且如果 你有任意深度的嵌套，你需要一个任意大的嵌套 自动机，它与有限自动机的概念相冲突。
或：
常规语言的 Pumping 引理是你不能做的原因 那。
[上述大部分解释都链接到维基百科页面，但这些页面并不比答案本身更容易理解]。
上面给出的正式解释的通俗术语是什么，为什么不能使用正则表达式来解析 （X）HTML/XML？
我正在寻找一个翻译，它也简要解释了它试图翻译的概念：在答案的最后，读者应该对“常规语言”和“上下文无关语法”的含义有一个粗略的了解。
答：
21赞
Ianus Chiaroscuro
7/20/2011
#1
因为 HTML 可以无限嵌套，而正则表达式无法真正应对这一点，因为它无法跟踪它所进入和产生的历史。<tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>
一个简单的结构，说明了困难：
<body><div id="foo">Hi there! <div id="bar">Bye!</div></div></body>
99.9% 的基于正则表达式的广义提取例程将无法正确地为我提供 ID 中的所有内容，因为它们无法将该 div 的结束标记与 div 的结束标记区分开来。那是因为他们没有办法说“好吧，我现在已经下降到两个 div 中的第二个，所以我看到的下一个 div close 会让我回来一个，之后的那个是第一个 div 的关闭标签”。程序员通常通过为特定情况设计特殊情况的正则表达式来响应，一旦内部引入更多标签，这些正则表达式就会中断，并且必须以巨大的时间和挫败感成本来解开。这就是为什么人们对整件事感到生气的原因。divfoobarfoo
评论
1赞
mac
7/20/2011
感谢答案，但我的问题不是“为什么我不能使用正则表达式......”。我的问题是关于“翻译”我提供的正式解释！:)
7赞
Ianus Chiaroscuro
7/20/2011
从某种意义上说，这是所有这些语言的翻译，最接近的是“正则表达式只能匹配常规语言，但 HTML 是一种上下文无关语言”，以及关于有限自动机的翻译。这真的都是一样的原因。
0赞
mac
7/20/2011
对不起，也许我的问题没有说清楚（欢迎提出改进建议！但我正在寻找一个也能解释“翻译”的答案。你的答案既没有阐明“常规语言”也没有阐明“上下文无关语言”的概念......
6赞
Ianus Chiaroscuro
7/20/2011
解释这些术语与行话本身一样具有技术性，并且会分散所有精确语言所表达的实际含义的注意力，这就是我发布的内容。
5赞
Kobi
7/20/2011
<(\w+)(?:\s+\w+="[^"]*")*>(?R)*</\1>|[\w\s!']+匹配您的代码示例。
9赞
n. m. could be an AI
7/20/2011
#2
正则表达式是具有有限（通常相当少）离散状态的机器。
要解析 XML、C 或任何其他具有任意嵌套语言元素的语言，您需要记住您的深度。也就是说，您必须能够计算大括号/括号/标签。
你不能用有限的内存来计数。大括号级别可能比您的状态还要多！您也许能够解析限制嵌套级别数量的语言子集，但这会非常乏味。
评论
1赞
Sean Werkema
2/24/2022
这个答案确实是通俗的正确答案，就像所提出的问题一样。状态机无法数到它们事先不知道的任何数字。如果要匹配标签，需要首先计算在它们之前有多少个标签，而状态机根本无法做到这一点。您可以创建可以计数到特定已知数量的标签的状态机，例如正好是 3 个、4 个或 57 个，但您不能创建可以计算未知 N 个标签的状态机。</div><div>
8赞
agent-j
7/20/2011
#3
语法是对单词可以去哪里的正式定义。例如，在英语语法中，形容词在名词之前，但在名词 en la gramática española 之后。 上下文无关意味着语法在所有上下文中普遍适用。上下文相关意味着在某些上下文中还有其他规则。
例如，在 C# 中，文件顶部的意思与 .更相关的示例是代码中的以下代码：usingusing System;using (var sw = new StringWriter (...))
void Start ()
{
string myCode = @"
void Start()
{
Console.WriteLine (""x"");
}
";
}
评论
0赞
Taemyr
6/4/2015
但无上下文并不意味着常规。匹配的 paranthesis 语言与上下文无关，但不是常规的。
0赞
reinierpost
11/21/2015
应该补充的是，正则表达式（除非您添加了Perl中存在的扩展）等同于常规语法，这意味着它们不能描述任意深度嵌套的结构，例如任意深度平衡的括号或HTML元素的开始和结束标记。
140赞
Steve Jessop
7/20/2011
#4
专注于这一点：
有限自动机（这是常规数据结构 expression） 除了它所处的状态之外没有内存，并且如果 你有任意深度的嵌套，你需要一个任意大的嵌套 自动机，它与有限自动机的概念相冲突。
正则表达式的定义等价于这样一个事实，即字符串是否与模式匹配的测试可以由有限自动机（每个模式一个不同的自动机）执行。有限自动机没有内存 - 没有堆栈，没有堆，没有无限的磁带可以涂鸦。它所拥有的只是有限数量的内部状态，每个状态都可以从被测试的字符串中读取一个输入单元，并使用它来决定下一步要移动到哪个状态。作为特殊情况，它有两种终止状态：“是，匹配”和“不，不匹配”。
另一方面，HTML 具有可以任意嵌套的结构。要确定文件是否为有效的 HTML，您需要检查所有结束标记是否与之前的开始标记匹配。要理解它，您需要知道哪个元素正在关闭。没有任何办法“记住”你看到的开场标签，就没有机会。
但请注意，大多数“正则表达式”库实际上只允许对正则表达式进行严格定义。如果它们可以匹配反向引用，那么它们已经超越了常规语言。因此，您不应该在 HTML 上使用正则表达式库的原因比 HTML 不规则的简单事实要复杂一些。
评论
1赞
GDP2
2/9/2016
这里还有一个关于有限状态自动机的很好的解释：youtube.com/watch?v=vhiiia1_hC4
11赞
Sean McMillan
7/20/2011
#5
常规语言是一种可以与有限状态机匹配的语言。
（了解有限状态机、下推机和图灵机基本上是大学计算机科学四年级课程的课程。
请考虑以下计算机，它识别字符串“hi”。
(Start) --Read h-->(A)--Read i-->(Succeed)
\ \
\ -- read any other value-->(Fail)
-- read any other value-->(Fail)
这是一台简单的机器，可以识别常规语言;括号中的每个表达式都是一个状态，每个箭头都是一个过渡。构建这样的机器将允许您根据常规语言（因此是正则表达式）测试任何输入字符串。
HTML 要求您知道的不仅仅是您所处的状态，它还需要您以前看到的内容的历史记录，以匹配标记嵌套。如果将堆栈添加到计算机中，则可以完成此操作，但随后它不再是“常规”堆栈。这称为下推机，可识别语法。
评论
2赞
mac
7/20/2011
“了解有限状态机、下推机和图灵机基本上是 300 级 CS 课程的课程。”我知道这是试图说明这个话题的难度/先进性，但我不熟悉你所指的学校系统，你能以非特定国家的方式澄清一下吗？谢谢！:)
1赞
Sean McMillan
7/20/2011
我已经更新了它。我不知道这太难理解了，只是在堆栈溢出帖子中解释。
67赞
Kobi
7/20/2011
#6
HTML 不代表常规语言这一事实是一条红鲱鱼。正则表达式和正则语言听起来有点相似，但事实并非如此——它们确实有着相同的起源，但学术上的“常规语言”与当前引擎的匹配能力之间存在着明显的距离。事实上，几乎所有的现代正则表达式引擎都支持非常规功能——一个简单的例子是。它使用反向引用来匹配重复的字符序列 - 例如 或 .递归/平衡结构的匹配使这些变得更加有趣。(.*)\1123123bonbon
维基百科用拉里·沃尔（Larry Wall）的一句话很好地表达了这一点：
“正则表达式”[...]与真正的正则表达式只有轻微的关联。尽管如此，这个术语已经随着我们的模式匹配引擎的功能而增长，所以我不打算在这里试图与语言的必要性作斗争。然而，我通常称它们为“正则表达式”（或“正则表达式”，当我处于盎格鲁-撒克逊人的情绪中时）。
正如你所看到的，“正则表达式只能匹配常规语言”，只不过是一个普遍说法的谬误。
那么，为什么不呢？
不将 HTML 与正则表达式匹配的一个很好的理由是“仅仅因为你可以并不意味着你应该”。虽然可能是可能的 - 但有更好的工具可以完成这项工作。考虑到：
有效的 HTML 比您想象的更难/更复杂。
“有效”HTML 有很多种类型——例如，在 HTML 中有效的 HTML 在 XHTML 中无效。
无论如何，在 Internet 上找到的许多自由格式 HTML 都是无效的。HTML 库在处理这些问题方面也做得很好，并且针对许多这些常见情况进行了测试。
很多时候，如果不将其作为一个整体进行解析，就不可能匹配部分数据。例如，您可能正在查找所有标题，并最终在注释或字符串文本中匹配。 可能是寻找主标题的大胆尝试，但它可能会发现：
<h1>.*?</h1><!-- <h1>not the title!</h1> -->甚至：
<script> var s = "Certainly <h1>not the title!</h1>"; </script>
最后一点是最重要的：
- 使用专用的 HTML 解析器比你能想到的任何正则表达式都要好。很多时候，XPath 允许以更好的表达方式来查找所需的数据，并且使用 HTML 解析器比大多数人意识到的要容易得多。
Jeff Atwood 的博客中对这个主题进行了很好的总结，并对何时混合正则表达式和 HTML 可能合适进行了重要评论：解析 Html 克苏鲁之道。
什么时候使用正则表达式来解析 HTML 比较好？
在大多数情况下，最好在库可以为您提供的 DOM 结构上使用 XPath。尽管如此，与流行的观点相反，在某些情况下，我强烈建议使用正则表达式而不是解析器库：
给定以下几个条件：
- 当您需要一次性更新 HTML 文件时，并且您知道结构是一致的。
- 当你有一个非常小的 HTML 片段时。
- 当您处理的不是 HTML 文件，而是类似的模板引擎时（在这种情况下很难找到解析器）。
- 当您想更改 HTML 的某些部分而不是全部时 - 据我所知，解析器无法响应此请求：它将解析整个文档，并保存整个文档，更改您从未想过更改的部分。
评论
4赞
mac
7/20/2011
这是一篇关于何时（不）使用正则表达式解析 HTML 的非常清晰且写得很好的文章，但它几乎不是我问题的答案。我可以建议你把它移到这个问题上吗？我认为它会让你在那里获得更多的声誉，但最重要的是，我认为这将是一个未来访问者会发现它更相关的地方（@Bart Kiers 对我的问题发表了评论，提醒访问者现代正则表达式引擎的“额外功能”）。
1赞
Kobi
7/20/2011
@mac - 非常感谢。实际上，我确实考虑过。我知道我没有回答你的问题，但我认为这个问题基本上不正确——你要求解释错误的原因......不过你有个好主意，也许另一个问题更合适......
0赞
Peter Mortensen
8/7/2023
www.codinghorror.com 链接似乎已断开（超时）。
0赞
Kobi
8/7/2023
@PeterMortensen - 已修复！
7赞
Michael Kay
6/13/2018
#7
不使用正则表达式来解析 XML 和 HTML 还有另一个与计算机科学理论完全无关的实际原因：你的正则表达式要么非常复杂，要么是错误的。
例如，编写一个正则表达式来匹配一切都很好
<price>10.65</price>
但是，如果你的代码是正确的，那么：
它必须在开始和结束标记中的元素名称后允许空格
如果文档位于命名空间中，则它应该允许使用任何命名空间前缀
它可能应该允许并忽略开始标签中出现的任何未知属性（取决于特定词汇表的语义）
它可能需要在十进制值之前和之后允许空格（同样，取决于特定 XML 词汇表的详细规则）。
它不应与看起来像元素的内容匹配，但实际上位于注释或 CDATA 部分中（如果恶意数据可能试图欺骗您的解析器，这一点就变得尤为重要）。
如果输入无效，则可能需要提供诊断。
当然，其中一些取决于您应用的质量标准。我们在 Stack Overflow 上看到很多问题，人们必须以特定方式生成 XML（例如，标签中没有空格），因为它是由需要以特定方式编写的应用程序读取的。如果您的代码具有任何类型的寿命，那么重要的是它应该能够处理以 XML 标准允许的任何方式编写的传入 XML，而不仅仅是您正在测试代码的一个示例输入文档。
2赞
buchWyrm
6/20/2018
#8
从纯粹的理论意义上讲，正则表达式不可能解析 XML。它们的定义方式不允许它们记住任何先前的状态，从而阻止任意标记的正确匹配，并且它们无法渗透到任意嵌套深度，因为嵌套需要内置到正则表达式中。
然而，现代正则表达式解析器是为它们对开发人员的实用性而构建的，而不是它们对精确定义的遵守。因此，我们有诸如反向引用和递归之类的东西，它们利用了先前状态的知识。使用这些，创建可以浏览、验证或解析 XML 的正则表达式非常简单。
例如，考虑一下，
(?:
<!\-\-[\S\s]*?\-\->
|
<([\w\-\.]+)[^>]*?
(?:
\/>
|
>
(?:
[^<]
|
(?R)
)*
<\/\1>
)
)
这将找到下一个格式正确的 XML 标记或注释，并且只有在其全部内容格式正确时才会找到它。（此表达式已使用 Notepad++ 进行了测试，Notepad++ 使用 Boost C++ 的正则表达式库，该库非常接近 PCRE。
其工作原理如下：
- 第一个区块与注释匹配。有必要首先进行，以便它将处理任何可能导致挂起的注释掉的代码。
- 如果不匹配，它将查找标记的开头。请注意，它使用括号来捕获名称。
- 此标记要么以 结尾，从而完成标记，要么以 结尾，在这种情况下，它将通过检查标记的内容来继续。
/>> - 它将继续解析，直到到达 ，此时它将递归回表达式的开头，从而允许它处理注释或新标签。
< - 它将继续循环，直到到达文本的末尾或无法解析的文本。当然，不匹配将导致它重新开始该过程。否则，可能是此迭代的结束标记的开始。在结束标记内使用反向引用，它将匹配当前迭代（深度）的开始标记。只有一个捕获组，所以这个匹配是一件简单的事情。这使得它独立于所用标签的名称，但如果需要，您可以修改捕获组以仅捕获特定标签。
<<<\/\1> - 在这一点上，它要么踢出当前的递归，上升到下一个级别，要么以比赛结束。
此示例通过使用仅否定 或 的字符组来解决处理空格或识别相关内容的问题，或者在注释的情况下，通过使用 ，它将匹配任何内容，包括回车符和换行符，即使在单行模式下也是如此，一直持续到到达 .因此，它只是将所有内容视为有效，直到它达到有意义的内容。<>[\S\s]-->
在大多数情况下，像这样的正则表达式并不是特别有用。它将验证 XML 的格式是否正确，但这就是它真正要做的，并且它不考虑属性（尽管这将是一个简单的添加）。之所以这么简单，是因为它遗漏了现实世界中这样的问题，以及标签名称的定义。让它真正使用会让它更像一头野兽。一般来说，真正的XML解析器会好得多。这个可能最适合教授递归的工作原理。
长话短说：在实际工作中使用XML解析器，如果你想使用正则表达式，请使用它。
评论
4赞
Michael Kay
9/2/2018
只有当输入格式正确时，此正则表达式才会匹配的说法是不正确的。它不检查名称是否为有效的 XML 名称，不检查属性，不检查实体和字符引用，不处理 CDATA 或处理指令。当你说它已经过测试时，我非常怀疑它是否已经在类似于XML一致性测试套件的任何设备上进行了测试。这就是我所见过的所有使用正则表达式处理 XML 的尝试的问题：它们只处理少量输入，但不能处理任何可以合法传递给应用程序的 XML。
3赞
Michael Kay
9/2/2018
此外，还有一些格式正确的输入与正则表达式不匹配。例如，它不允许在结束标记中的名称后使用空格。这些故障中的大多数都很容易修复，但是一旦您修复了所有故障，您最终会得到完全无法使用的东西。当然，真正的问题是，你不仅希望解析器给你一个是/否的答案，你还希望它将信息传递给一个用它做一些有用事情的应用程序。
3赞
Gilles Quénot
4/4/2019
#9
不要使用正则表达式解析 XML/HTML。使用适当的 XML/HTML 解析器和强大的 XPath 查询。
理论：
根据编译理论，XML/HTML 不能使用基于有限状态机的正则表达式进行解析。由于 XML/HTML 的分层结构，您需要使用下推自动机并使用 YACC 等工具操作 LALR 语法。
©®™ shell 中的真实日常工具：
您可以使用以下方法之一：
xmllint，通常默认安装，xpath1（检查我的包装器以换行符分隔输出libxml2
xmlstarlet 可以编辑、选择、转换等。默认情况下不安装它，xpath1
xpath，通过 Perl 的模块 XML：：XPath 安装 xpath1
xidel xpath3
saxon-lint，我自己的项目，@Michael Kay 的 Saxon-HE Java 库 xpath3 的包装器
或者您可以使用高级语言和适当的库，我想到：
Python 的 lxml (from lxml import etree)
Perl 的 XML：：LibXML、XML：：XPath、XML：：Twig：：XPath 和 HTML：：TreeBuilder：：XPath
4赞
Calum McConnell
12/15/2020
#10
所以其他人已经为其中的大多数给出了简短的定义，但我真的不认为它们涵盖了为什么普通的正则表达式是它们。
关于什么是有限状态机，有一些很好的资源，但简而言之，计算机科学中的一篇开创性论文证明了正则表达式的基本语法（grep 使用的标准语法，而不是扩展语法，如 PCRE）总是可以纵到有限状态机中，这意味着你总是在一个盒子里的“机器”， 并且移动到下一个框的方法数量有限。简而言之，你总是可以通过查看当前角色来判断你需要做的下一件事。（是的，即使涉及到“至少匹配 4 次，但不超过 5 次”之类的事情，您仍然可以创建这样的机器）（我应该注意，我在这里描述的机器在技术上只是有限状态机的一个子类型，但它可以实现任何其他子类型，所以......
这很好，因为您始终可以非常有效地评估这样的机器，即使是对于大输入。研究这类问题（当我喂食的东西数量变大时，我的算法如何表现）被称为研究技术的计算复杂性。如果你熟悉很多微积分如何处理函数在接近无穷大时的行为，那么，差不多就是这样。
那么，标准正则表达式有什么好处呢？好吧，任何给定的正则表达式都可以在不超过 O（N） 的时间内匹配长度为 N 的字符串（这意味着将输入长度加倍会使所需的时间增加一倍：它没有说明给定输入的速度）（当然，有些速度更快：正则表达式 * 可以在 O（1） 中匹配，表示常数，时间）。原因很简单：请记住，因为系统只有来自每个状态的几条路径，所以你永远不会“回去”，你只需要检查每个字符一次。这意味着即使我给你一个 100 GB 的文件，你仍然可以很快地处理它：这太棒了！
现在，很清楚为什么你不能使用这样的机器来解析任意的 XML：你可以有无限的标签中的标签，而要正确解析，你需要无限数量的状态。但是，如果你允许递归替换，PCRE 是图灵完备的：所以它可以完全解析 HTML！即使您不这样做，PCRE 也可以解析任何上下文无关的语法，包括 XML。所以答案是“是的，你可以”。现在，它可能需要指数级的时间（你不能使用我们简洁的有限状态机，所以你需要使用一个可以倒带的大型花哨解析器，这意味着一个精心设计的表达式将花费几个世纪的大文件），但仍然如此。可能。
但是，让我们快速谈谈为什么这是一个糟糕的主意。首先，虽然你会看到很多人说“天哪，正则表达式太强大了”，但现实是......但事实并非如此。它们很简单。这门语言非常简单：你只需要知道几个元字符和它们的含义，你就可以（最终）理解其中写的任何内容。然而，问题是这些元字符就是你所拥有的。看，它们可以做很多事情，但它们旨在简明扼要地表达相当简单的事情，而不是试图描述一个复杂的过程。
XML肯定很复杂。在其他一些答案中很容易找到示例：您无法匹配评论字段中的内容等。用编程语言表示所有这些需要工作：这就是变量和函数的好处！PCRE的所有功能都无法与之相提并论。任何手工制作的实现都会有问题：扫描元字符的斑点以检查匹配的括号是很困难的，而且你不能注释你的代码。定义一种元语言，并将其编译为正则表达式会更容易：在这一点上，你不妨直接使用你编写元编译器的语言，并编写一个XML解析器。对你来说会更容易，运行速度更快，而且整体效果更好。
有关这方面的更多信息，请查看此网站。它用通俗易懂的语言很好地解释了所有这些东西。
评论