为什么不能使用正则表达式来解析 HTML/XML: 用外行的术语作正式的解释

没有哪一天在 SO 中不会问到如何使用正则表达式解析(X) HTML 或 XML 的问题。

虽然用 演示正则表达式对于此任务的不可行性的示例或 表达式集合来表示这个概念相对容易，但是我仍然找不到一个 正式的来解释为什么不能用外行的术语来做这件事。

到目前为止，我能在这个网站上找到的唯一正式的解释可能是极其准确的，但对于自学成才的程序员来说也是相当神秘的:

这里的缺陷是 HTML 是 Chomsky Type 2语法(上下文无关) RegEx 是 Chomsky Type 3语法(正则表达式)

或:

正则表达式只能匹配正则语言，但 HTML 是 上下文无关语言

或:

一个有限自动机(它是一个正则数据库的底层数据结构) 表达式)除了它所处的状态之外没有内存，如果 你有任意深的嵌套，你需要一个任意大 这与有限自动机的概念相冲突。

或:

常规语言的抽取引理是您不能这样做的原因 那个。

[公平地说: 上面的大部分解释链接到维基百科页面，但是这些并不比答案本身更容易理解]。

所以我的问题是: 能否有人提供一个翻译，在外行的术语正式解释为什么不可能使用正则表达式解析(X) HTML/XML？

编辑: 在阅读了第一个答案后，我想我应该澄清一下: 我在寻找一个“翻译”，也简短地 解释它试图翻译的概念: 在一个答案的结尾，读者应该有一个粗略的想法-例如-什么是“常规语言”和“上下文无关文法”的含义..。

35844 次浏览
小开

因为 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% 的通用的基于正则表达式的提取例程将无法正确地提供 div中 ID 为 foo的所有内容，因为它们无法区分该 div 的结束标记和 bar div 的结束标记。这是因为他们没有办法说“好的，我现在已经下降到两个 div 中的第二个，所以我看到的下一个 div 关闭将我带回一个，下一个是第一个的关闭标记。”。程序员通常会针对特定情况设计特殊情况下的正则表达式，一旦 foo中引入更多的标记，这些正则表达式就会中断，必须在时间和挫折方面付出巨大代价才能解决这个问题。这就是为什么人们对整件事都很生气。

小开

正则表达式是具有有限个(通常相当小)离散状态的机器。

要解析 XML、 C 或任意嵌套语言元素的任何其他语言，您需要记住您的深度。也就是说，必须能够计算大括号/括号/标记。

你不能用有限的内存来计数。可能有比状态更多的大括号级别！您可能能够解析语言中限制嵌套级别数量的子集，但是这将是非常繁琐的。

小开

语法是单词可以去哪里的正式定义。例如，形容词在名词 in English grammar之前，但在名词 en la gramática española之后。 上下文无关意味着语法在所有上下文中普遍适用。上下文敏感意味着在某些上下文中有额外的规则。

例如，在 C # 中，using在文件顶部的 using System;中的意思与 using (var sw = new StringWriter (...))不同。一个更相关的示例是代码中的以下代码:

void Start ()
{
string myCode = @"
void Start()
{
Console.WriteLine (""x"");
}
";
}
小开
最佳答案

集中注意力在这个上面:

一个有限自动机(它是一个正则数据库的底层数据结构) 表达式)除了它所处的状态之外没有内存，如果 你有任意深的嵌套，你需要一个任意大 这与有限自动机的概念相冲突。

正则表达式的 定义相当于一个有限自动机(每个模式有一个不同的自动机)可以执行字符串是否与模式匹配的测试。有限自动机没有内存——没有堆栈，没有堆，没有无限的磁带可以涂鸦。它所拥有的只是有限数量的内部状态，每个状态都可以从正在测试的字符串中读取一个输入单元，并使用它来决定下一个移动到哪个状态。作为特殊情况，它有两个终止状态: “是的，那匹配”和“不，那不匹配”。

另一方面，HTML 的结构可以任意深度嵌套。要确定一个文件是否是有效的 HTML，您需要检查所有的结束标记是否与前一个开始标记匹配。要理解它，您需要知道哪个元素被关闭。没有任何方法来“记住”你所看到的开始标签，没有机会。

但是请注意，大多数“正则表达式”库实际上允许的不仅仅是正则表达式的严格定义。如果他们能够匹配后向引用，那么他们已经超越了常规语言。因此，不应该在 HTML 上使用正则表达式库的原因要比 HTML 不规则这一简单事实稍微复杂一些。

小开

正则语言是一种可以与有限状态机匹配的语言。

(理解有限状态机、下推机和图灵机基本上是大学四年级计算机科学课程的课程。)

考虑下面的机器，它识别字符串“ hi”。

(Start) --Read h-->(A)--Read i-->(Succeed)
\                  \
\                  -- read any other value-->(Fail)
-- read any other value-->(Fail)

这是一个识别正则语言的简单机器; 括号中的每个表达式都是一个状态，每个箭头都是一个转换。构建这样的机器将允许您针对正则语言测试任何输入字符串——因此，是一个正则表达式。

HTML 要求您了解的不仅仅是您所处的状态——它还需要您以前看到的历史记录，以便与标记嵌套匹配。如果向计算机添加一个堆栈，但它不再是“常规”堆栈，则可以实现这一点。这就是所谓的下推机，并识别一种语法。

小开

HTML 不能代表一种常规语言的事实是在转移人们的注意力。正则表达式和正则语言 听起来有点像，但它们不是——它们确实有着相同的起源，但是在学术上的“正则语言”和当前引擎的匹配能力之间存在着显著的差距。事实上，几乎所有的现代正则表达式引擎都支持非正则特性——一个简单的例子就是 (.*)\1。它使用反向引用来匹配一个字符重复序列，例如 123123或者 bonbon。递归/平衡结构的匹配使这些更加有趣。

维基百科引用 拉里 · 沃尔的一句话说得很好:

“正则表达式”[ ... ]与真正的正则表达式只有很小的关系。尽管如此，这个词已经随着我们模式匹配引擎的能力而增长，所以我不打算在这里与语言的必要性作斗争。然而，我通常称它们为“ regex”(或者“ regexen”，当我处于盎格鲁-撒克逊情绪时)。

正如你所看到的，“正则表达式只能匹配正则语言”不过是一个常见的谬论。

那为什么不呢？

不将 HTML 与正则表达式匹配的一个很好的理由是，“仅仅因为您可以并不意味着您应该”。尽管可能-只是有更好的工具。考虑:

  • 有效的 HTML 比你想象的更难/更复杂。

  • 有许多类型的“有效的”HTML ——例如，在 HTML 中有效的，在 XHTML 中无效。

  • 互联网上大部分自由格式的 HTML 都是 无论如何都是无效的。HTML 库在处理这些问题方面也做得很好，并且针对许多常见情况进行了测试。

  • 通常情况下，如果不对部分数据进行整体解析，就不可能对其进行匹配。例如，您可能正在查找所有标题，并最终在注释或字符串文本中进行匹配。<h1>.*?</h1>可能是寻找主题的一次大胆尝试，但它可能会发现:

      <!-- <h1>not the title!</h1> -->

    甚至:

      <script>
var s = "Certainly <h1>not the title!</h1>";
</script>

最后一点是最重要的:

  • 使用专用的 HTML 解析器比您能想到的任何正则表达式都要好。通常，XPath 允许以更好的表达方式查找所需的数据和 使用 HTML 解析器比大多数人意识到的要容易得多。

在 Jeff Atwood 的 blog: 解析克苏鲁方式中可以找到关于这个主题的一个很好的总结，以及关于何时混合正则表达式和 HTML 可能是合适的一个重要评论。

何时使用正则表达式解析 HTML 更好？

在大多数情况下，最好在库提供的 DOM 结构上使用 XPath。尽管如此，与流行的观点相反，在一些情况下，我强烈建议使用正则表达式而不是解析器库:

考虑到其中的一些条件:

  • 当您需要一次性更新您的 HTML 文件时，并且您知道结构是一致的。
  • 当你有一个非常小的 HTML 代码片段。
  • 当您处理的不是 HTML 文件，而是类似的模板引擎时(在这种情况下很难找到解析器)。
  • 当你想要改变 HTML 的某些部分时，但是 不是全部-一个解析器，据我所知，不能回答这个问题: 它会解析整个文档，保存整个文档，改变你从来不想改变的部分。
小开

不使用正则表达式解析 XML 和 HTML 的另一个实际原因与计算机科学理论毫无关系: 正则表达式要么极其复杂，要么就是错误的。

例如，编写一个匹配的正则表达式就非常好

<price>10.65</price>

但是如果你的代码是正确的，那么:

  • 它必须在开始和结束标记的元素名称后面都允许空格

  • 如果文档位于命名空间中，则应允许使用任何命名空间前缀

  • 它可能允许并忽略开始标记中出现的任何未知属性(取决于特定词汇表的语义)

  • 它可能需要在小数值之前和之后允许空格(同样，取决于特定 XML 词汇表的详细规则)。

  • 它不应该匹配看起来像元素，但实际上位于注释或 CDATA 节中的内容(如果存在恶意数据试图欺骗解析器的可能性，这一点就尤其重要)。

  • 如果输入无效，它可能需要提供诊断信息。

当然，这取决于您所应用的质量标准。我们在 StackOverflow 上看到很多问题，人们必须以特定的方式生成 XML (例如，标记中没有空格) ，因为应用程序需要以特定的方式来读取 XML。如果您的代码有一定的寿命，那么它应该能够以 XML 标准允许的任何方式处理传入的 XML，而不仅仅是您正在测试代码的一个示例输入文档，这一点非常重要。

小开

在纯理论意义上，正则表达式不可能解析 XML。它们的定义方式不允许它们存储任何以前的状态，从而防止任意标记的正确匹配，并且它们不能渗透到任意的嵌套深度，因为嵌套需要内置到正则表达式中。

然而，现代的正则表达式解析器是为开发人员的实用性而构建的，而不是为了遵循精确的定义。因此，我们有了像反向引用和递归这样的东西，它们利用了以前状态的知识。使用它们，创建一个可以探索、验证或解析 XML 的正则表达式非常简单。

举个例子,

(?:
<!\-\-[\S\s]*?\-\->
|
<([\w\-\.]+)[^>]*?
(?:
\/>
|
>
(?:
[^<]
|
(?R)
)*
<\/\1>
)
)

这将找到下一个格式正确的 XML 标记或注释，并且只有当它的整个内容格式正确时才能找到它。(该表达式已经使用 Notepad + + 进行了测试，Notepad + + 使用 Boost C + + 的 regex 库，该库与 PCRE 非常接近。)

它是这样运作的:

  1. 第一个块与注释匹配。有必要首先处理这个问题，以便处理任何注释掉的代码，否则可能会导致挂起。
  2. 如果不匹配，它将查找标记的开头。注意，它使用括号来捕获名称。
  3. 这个标记要么以 />结束，从而完成标记，要么以 >结束，在这种情况下，它将通过检查标记的内容来继续。
  4. 它将继续解析，直到达到 <，此时它将递归回表达式的开头，允许它处理注释或新标记。
  5. 它将继续循环，直到到达文本的末尾或者到达无法解析的 <。当然，不匹配将导致重新开始这个过程。否则，<可能是这个迭代的结束标记的开始。使用结束标记 <\/\1>中的反向引用，它将匹配当前迭代的开始标记(深度)。只有一个捕捉组，所以这场比赛很简单。这使得它独立于所使用的标记的名称，尽管如果需要，您可以修改捕获组以仅捕获特定的标记。
  6. 此时，它将要么踢出当前递归，直到下一级，要么以匹配结束。

这个例子解决了处理空格或者通过使用字符组来识别相关内容的问题，这些字符组仅仅是否定 <或者 >，或者在注释的情况下，使用 [\S\s]，它将匹配任何东西，包括回车和新行，甚至在单行模式下，一直到达到 因此，它只是简单地将所有内容视为有效，直到它达到某些有意义的内容。

对于大多数情况，这样的正则表达式并不特别有用。它将验证 XML 的格式是否正确，但这就是它真正要做的，并且它不考虑属性(尽管这是一个简单的添加)。之所以这么简单，是因为它忽略了像这样的现实问题，以及标记名的定义。如果真的能用的话，它就更像野兽了。一般来说，真正的 XML 解析器要好得多。这一个可能最适合教授递归如何工作。

长话短说: 在实际工作中使用 XML 解析器，如果您想使用正则表达式，那么可以使用它。

小开

不要使用正则表达式解析 XML/HTML，使用适当的 XML/HTML 解析器和强大的 查询。

理论:

根据编译原理，基于 有限状态机有限状态机的正则表达式无法解析 XML/HTML。由于 XML/HTML 的层次结构，您需要使用 下推自动机并使用诸如 YACC之类的工具操作 LALR语法。

RealLife TM 中的日常工具:

您可以使用下列方法之一:

默认情况下，xmllint 通常与 libxml2，xpath1一起安装(请选中 我的包装纸，使用换行符分隔输出

Xmlstarlet 可以编辑、选择、转换... 默认情况下未安装 xpath1

通过 perl 模块 XML: : XPath，xpath1安装的 XPath

Xidel xpath3

Saxon-lint 我自己的项目,@Michael Kay 的 Saxon-HE Java 库 xpath3的包装器

或者你可以使用高级语言和适当的图书馆，我想:

的 lxml(from lxml import etree)

的 XML::LibXML，XML::XPath，XML::Twig::XPath，< a href = “ https://metacpan.org/pod/HTML: : TreeBuilder: : XPath”rel = “ nofollow noReferrer”> HTML::TreeBuilder::XPath

，< a href = “ https://sputnick.fr/script/parsing-HTML-with-NokogiriXpath.rb.html”rel = “ nofollow noReferrer”> 检查这个示例

DOMXpath，< a href = “ https://sputnick.fr/script/parsing-HTML-with-DOMXpath.php.html”rel = “ nofollow noReferrer”> 检查这个示例

检查: 使用带 HTML 标记的正则表达式

小开

因此，其他人已经走了，并给出了大多数这些事情的简短定义，但我真的不认为他们涵盖为什么正则表达式是什么。

关于什么是有限状态机有一些很好的资源，但是简而言之，计算机科学的一篇开创性的论文证明了 regex 的基本语法(由 grep 使用的标准语法，而不是扩展语法，如 PCRE)总是可以被操纵成一个有限状态机，这意味着一个“机器”，你总是在一个盒子里，并且有有限的方法可以移动到下一个盒子。简而言之，你总是可以通过查看当前字符来判断你下一步需要做什么。(是的，即使是像“匹配至少4次，但不超过5次”这样的事情，你仍然可以创建一个像这样的机器)(我应该注意到，我在这里描述的机器在技术上只是有限状态机的一个子类型，但它可以实现任何其他子类型，所以...)

这非常好，因为您总是可以非常有效地评估这样的机器，即使是对于大的输入。研究这类问题(当我喂养的东西数量变大时，我的算法是如何运行的)称为研究该技术的计算复杂性。如果你熟悉很多微积分是如何处理函数在接近无穷大时的行为的，那么，就是这样了。

那么，标准正则表达式有什么了不起之处呢？任何给定的正则表达式都可以在不超过 O (N)的时间内匹配一个长度为 N 的字符串(这意味着将输入的长度加倍所需的时间加倍: 它没有说明给定输入的速度)(当然，有些更快: 正则表达式 * 可以在 O (1)中匹配，这意味着常量，时间)。原因很简单: 记住，因为系统从每个状态只有几条路径，所以你永远不会“回去”，你只需要检查每个字符一次。这意味着即使我传递给你一个100GB 的文件，你仍然能够很快地处理它: 这是伟大的！.

现在，非常清楚为什么不能使用这样的机器来解析任意的 XML: 可以使用无限的标记中标记，要正确解析，需要无限的状态。但是，如果允许递归替换，PCRE 就是图灵完成的: 因此它完全可以解析 HTML！即使没有，PCRE 也可以解析任何上下文无关文法，包括 XML。所以答案是“是的，你可以”。现在，它可能需要 EXPTIME (你不能使用我们整洁的有限状态机，所以你需要使用一个能够倒带的大型解析器，这意味着一个精心制作的表达式将花费几个世纪在一个大文件上) ，但仍然。有可能。

但是让我们快速讨论一下为什么这是一个糟糕的主意。首先，虽然你会看到很多人说“天哪，正则表达式是如此强大”，但事实是... 他们不是。它们的本质很简单。这种语言非常简单: 你只需要知道一些元字符及其含义，你就可以理解(最终)用它写的任何东西。然而，问题是这些元字符是你所拥有的全部。他们可以做很多事情，但是他们的目的是简明扼要地表达相当简单的事情，而不是试图描述一个复杂的过程。

XML 确实很复杂。在其他一些答案中很容易找到例子: 你不能匹配注释字段中的内容，等等。在编程语言中表示所有这些都需要付出努力: 这就是变量和函数的好处！PCRE 的所有特性都无法接近这一点。任何手工制作的实现都会有问题: 扫描元字符来检查匹配的括号是很困难的，而且不像你可以注释你的代码。定义一种元语言并将其编译为 regex 会更容易: 在这一点上，您最好使用您用来编写元编译器的语言并编写一个 XML 解析器。这样对你来说更容易，跑得更快，而且总体上更好。

想了解更多关于这方面的信息，请查看 这个网站。它很好地用通俗的语言解释了这一切。


提交答案