为什么不可能使用正则表达式解析HTML/XML：通俗易懂的正式解释

Question

为什么不可能使用正则表达式解析HTML/XML：通俗易懂的正式解释

regexlanguage-agnostic

144

在SO上，没有一天能过去没有关于使用正则表达式解析(X)HTML或XML的问题。

虽然相对来说很容易提供演示正则表达式在此任务中不可行性的示例，或者提供表示该概念的表达式集合，但我仍然无法在SO上找到一个以通俗易懂的方式 正式地 解释为什么这是不可能的。

到目前为止，在这个网站上我唯一能找到的正式解释可能非常准确，但对于自学编程人员来说也相当晦涩：

这里的缺陷在于HTML是Chomsky Type 2文法（上下文无关语法），而RegEx是Chomsky Type 3文法（正则表达式）

或者：

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

或者：

有限自动机（是正则表达式的数据结构）除了所处的状态之外没有记忆，如果您有任意深度的嵌套，则需要一个任意大的自动机，这与有限自动机的概念相冲突。

或者：

正则语言的泵引理就是你不能这样做的原因。

简单来说，为什么不能使用正则表达式解析（X）HTML / XML？因为HTML / XML具有嵌套结构，而正则表达式只能处理线性结构。正则表达式是一种描述字符串模式的工具，而HTML / XML是一种由标签和属性组成的结构化文档。正则表达式无法处理这种结构化信息，因此需要更强大的工具，如上下文无关文法和解析器。正则语言是一种比上下文无关文法更弱的语言类型，因此无法处理HTML / XML这样的结构化文档。

- mac

24

请注意，在计算机科学中，“正则表达式”与现代“正则表达式实现”（编程语言中使用的工具/API）有很大的区别。后者可以“记住”它们遇到的内容，甚至可以匹配递归定义的（子）模式，使它们比理论上的“正则表达式”更能匹配/分析/识别复杂的内容。 - Bart Kiers

1

@Bart：这仅适用于滥用"正则表达式"术语的语言。 POSIX ERE是纯正则表达式。 - R.. GitHub STOP HELPING ICE

3

@R..，所以你称POSIX为“现代实现”：P。但说真的：是的，你说得对，那些确实是正则表达式。我应该说“许多现代正则表达式实现”或“PCRE正则表达式实现”。 - Bart Kiers

5

我很难认真对待那些基本上滥用严谨语言来向无知的程序员自我营销的编程语言。 - R.. GitHub STOP HELPING ICE

4

很遗憾，PCRE实现被称为“正则表达式”，但不重视这种语言是过分的。我的意思是，你难道不认真对待Perl、Java、Python、Ruby、JavaScript、.NET等吗？ - Bart Kiers

显示剩余5条评论

10个回答

67

HTML不代表正则语言这一事实是个误导。正则表达式和正则语言听起来有些相似，但它们并不相同——尽管它们有着相同的起源，但学术上的“正则语言”与引擎当前的匹配能力之间存在明显差距。事实上，几乎所有现代正则表达式引擎都支持非正则特性——一个简单的例子是使用反向引用来匹配重复的字符序列，例如123123或bonbon。匹配递归/平衡结构使这些更加有趣。

维基百科通过Larry Wall的一句话很好地解释了这一点:

“正则表达式”[...]只与真正的正则表达式略微相关。尽管如此，随着我们的模式匹配引擎的功能增强，这个术语已经得到了发展，所以我不打算在这里与语言必要性进行斗争。然而，当我处于盎格鲁-撒克逊情绪时，我通常会称它们为“regexes”（或“regexen”）。

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

那么，为什么不呢？

不使用正则表达式匹配HTML的一个很好的原因是“仅仅因为你可以并不意味着你应该这样做”。虽然可能是可能的——但有更好的工具来完成这项工作。考虑到：

Valid HTML is harder/more complex than you may think.
There are many types of "valid" HTML - what is valid in HTML, for example, isn't valid in XHTML.
Much of the free-form HTML found on the internet is not valid anyway. HTML libraries do a good job of dealing with these as well, and were tested for many of these common cases.
Very often it is impossible to match a part of the data without parsing it as a whole. For example, you might be looking for all titles, and end up matching inside a comment or a string literal. <h1>.*?</h1> may be a bold attempt at finding the main title, but it might find:
```
  
```
Or even:
```
  <script>
  var s = "Certainly <h1>not the title!</h1>";
  </script>
```

最后一点是最重要的：

使用专用的HTML解析器比你能想到的任何正则表达式都更好。很多时候，XPath可以更好地表达查找所需数据的方式，并且使用HTML解析器比大多数人意识到的要容易得多。

关于这个主题的一个很好的总结，以及关于何时混合使用正则表达式和HTML可能是适当的重要评论，可以在Jeff Atwood的博客中找到：Parsing Html The Cthulhu Way。

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

在大多数情况下，最好在库可以提供的DOM结构上使用XPath。尽管如此，与普遍观点相反，有几种情况我会强烈建议使用正则表达式而不是解析器库：

给定以下几个条件之一：

当您需要对HTML文件进行一次性更新时，并且您知道结构是一致的。
当您只有一小段HTML时。
当您不处理HTML文件，而是类似的模板引擎（在这种情况下很难找到解析器）。
当您想要更改HTML的某些部分，但不是全部 - 就我所知，解析器无法回答这个请求：它将解析整个文档，并保存整个文档，更改您从未想过更改的部分。

- Kobi

4

这篇文章非常清晰且写得很好，讲述了何时（不应该）使用正则表达式解析HTML，但它并不能回答我的问题。我可以建议你将其移至此问题吗？我认为这样做会使您在那里获得更多的声誉，但最重要的是，我认为这将是未来访问者更相关的地方（@Bart Kiers在我的问题中留下了一条评论，提醒访问者现代正则表达式引擎的“额外功能”）。 - mac

1

@mac - 非常感谢。实际上，我确实考虑过这个问题。我知道我没有回答你的问题，但我认为这个问题基本上是不正确的 - 你要求解释错误的原因...不过你有一个好主意，也许另一个问题更合适... - Kobi

www.codinghorror.com链接似乎已损坏（超时）。 - Peter Mortensen

@PeterMortensen - 修复完成！ - Kobi

21

因为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>

大多数基于正则表达式的通用提取程序无法正确给出ID为foo的

中所有内容，因为它们无法区分该div的结束标记和bar div的结束标记。这是因为它们没有办法说：“好的，我现在进入了两个div中的第二个，所以我看到的下一个div关闭标记将使我向外返回一个div，而其后的关闭标记是第一个div的关闭标记”。程序员通常会针对特定情况设计特殊情况的正则表达式，但一旦在foo内引入更多标记，这些正则表达式就会失效，并需要花费巨大的时间和精力进行排除。这就是为什么人们对整个过程感到愤怒的原因。

- Ianus Chiaroscuro

1

感谢您的回答，但我的问题不是“为什么我不能使用正则表达式...”。我的问题是关于“翻译”我提供的正式解释！ :) - mac

7

某种程度上，这是所有内容的翻译，最接近的含义是“正则表达式只能匹配正则语言，但HTML是一种上下文无关的语言”，还有一个关于有限状态自动机的说法。其实都是同一个原因。 - Ianus Chiaroscuro

抱歉，也许我在问题表述上不够清晰（欢迎提出改进意见！）。但我正在寻找一个同时解释“翻译”的答案。你的回答并没有澄清“常规语言”和“无上下文语言”概念... - mac

6

解释那些术语会和术语本身一样技术性，会分散注意力，而且会使所有精确用语所表达的实际含义变得模糊不清。重要的是理解我发表的内容。 - Ianus Chiaroscuro

5

<(\w+)(?:\s+\w+="[^"]*")*>(?R)*</\1>|[\w\s!']+ 匹配你的代码示例。 - Kobi

11

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

（理解有限状态机、下推自动机和图灵机基本上是大学计算机科学四年级课程的内容。）

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

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

这是一个简单的机器，用于识别正则语言；括号中的每个表达式都代表一个状态，箭头则表示转移。构建这样的机器将使您能够测试任何输入字符串是否符合正则语言--因此就是一个正则表达式。

HTML要求您不仅知道当前的状态--还需要了解之前所见内容的历史记录，以匹配标签嵌套。如果您在机器上添加一个堆栈，可以完成这项任务，但它就不再是"正则"了。这被称为推导机器，并可识别语法。

- Sean McMillan

2

理解有限状态机（Finite State Machines）、下推自动机（Push-down Machines）和图灵机（Turing Machines）基本上是一门 300 级计算机科学课程的课程大纲。 - mac

1

我已经更新了它。我不知道它是否太难理解，只是在stackoverflow帖子中解释起来有点困难。 - Sean McMillan

9

正则表达式是一种拥有有限（通常相当小）离散状态的机器。

要解析XML、C或任何具有任意嵌套语言元素的语言，您需要记住自己所在的深度。也就是说，您必须能够计算大括号/方括号/标签的数量。

您无法使用有限的内存来计数。可能会有比您拥有的状态更多的大括号层级！您可能能够解析子集语言，该语言限制了嵌套级别的数量，但这将非常繁琐。

- n. m.

1

这个答案确实是用通俗易懂的语言回答问题的。状态机无法预先计算到任何数字。如果你想匹配</div>标签，你需要先计算出在它们之前有多少个<div>标签，而状态机无法做到这一点。你可以制作能够计数到特定已知数量标签的状态机，例如恰好3、4或57个，但你无法制作能够计数未知数量标签的状态机N。 - Sean Werkema

8

一个语法是单词可以放置的正式定义。例如，在英语语法中形容词在名词之前，但在西班牙语语法中跟随名词。无上下文含义意味着语法在所有情境中都适用。有上下文含义则意味着在某些情境中有额外的规则。

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

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}

- agent-j

这是一个易于理解的答案。 - A Person

但是无上下文并不意味着正则。匹配括号的语言是无上下文的，但不是正则的。 - Taemyr

需要补充的是，正则表达式（除非您添加类似于Perl中存在的扩展）等同于正则语法，这意味着它们不能描述任意深嵌套的结构，例如任意深度平衡的括号或HTML元素的开闭标签。 - reinierpost

7

使用正则表达式解析XML和HTML的另一个实际原因与计算机科学理论无关：你的正则表达式要么会变得非常复杂，要么就是错误的。

例如，编写一个正则表达式来匹配某些内容可能看起来很好，但实际上很难实现。

<price>10.65</price>

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

它必须允许元素名称之后的空白字符出现在开始和结束标签中
如果文档处于命名空间中，它应该允许使用任何命名空间前缀
它可能需要允许并忽略开始标签中出现的任何未知属性（取决于特定词汇的语义）
它可能需要在十进制值之前和之后允许空白字符（再次取决于特定 XML 词汇的详细规则）
它不应匹配看起来像元素但实际上位于注释或 CDATA 部分的内容（如果存在恶意数据试图欺骗解析器的可能性，这变得尤为重要）
如果输入无效，它可能需要提供诊断信息。

当然，这取决于您所应用的质量标准。我们在Stack Overflow上看到很多问题，人们不得不以特定的方式生成XML（例如，在标签中没有空格），因为它被一个要求以特定方式编写的应用程序读取。如果您的代码具有任何形式的持久性，那么重要的是它能够处理以XML标准允许的任何方式编写的输入XML，而不仅仅是您在测试代码时使用的一个示例输入文档。

- Michael Kay

4

所以其他人已经对大多数这些东西给出了简要定义，但我真的不认为它们涵盖了为什么正则表达式是什么样子。

有一些很好的资源可以了解有限状态机是什么，简单来说，计算机科学中的一篇重要论文证明了正则表达式的基本语法（标准的那种，由grep使用，而不是扩展的那种，比如PCRE）总是可以转化为一个有限状态机，意味着你总是处于一个“盒子”中，并且有限的方法可以移动到下一个盒子。简而言之，你只需查看当前字符，就可以始终知道下一步该做什么。（是的，即使是像“至少匹配4次，但不超过5次”这样的情况，你仍然可以创建这样的机器）（值得注意的是，我在这里描述的机器在技术上只是有限状态机的一种子类型，但它可以实现任何其他子类型，所以...）

这很棒，因为你可以非常高效地评估这样的机器，即使对于大输入也是如此。研究这些问题（当我喂给算法的东西数量变大时，我的算法会如何表现）被称为研究技术的计算复杂性。如果你熟悉微积分中处理函数在无限接近时的行为方式，那基本上就是这样。

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

现在，很明显为什么你不能使用这样的机器来解析任意的XML：你可以有无限的标签嵌套，在正确解析时需要无限数量的状态。但是，如果允许递归替换，一个PCRE是Turing complete：所以它完全可以解析HTML！即使不允许，一个PCRE也可以解析任何上下文无关的语法，包括XML。所以答案是“是的，你可以”。现在，可能需要指数时间（你不能使用我们漂亮的有限状态机，所以你需要使用一个能够回溯的大型高级解析器，这意味着一个精心设计的表达式将在大文件上花费几个世纪的时间），但是仍然是可能的。

但我们快速谈一下为什么这是一个糟糕的主意。首先，尽管你会看到很多人说"哦天啊，正则表达式太强大了"，但事实并非如此。它们只是简单而已。这种语言非常简单：你只需要知道一些元字符及其含义，就能（最终）理解其中的任何内容。然而，问题在于你只有这些元字符可用。你看，它们可以做很多事情，但它们旨在简洁地表达相对简单的事物，而不是试图描述一个复杂的过程。

XML确实很复杂。在其他答案中很容易找到一些例子：你不能匹配注释字段内的内容等等。用编程语言表示所有这些需要付出努力，即使有变量和函数的好处！尽管PCRE具有各种功能，但无法与之相提并论。任何手工实现都会有bug：扫描大量元字符以检查匹配的括号是困难的，而且你不能像注释代码一样注释你的代码。定义一种元语言，并将其编译成正则表达式会更容易：在那时，你可能会选择使用编写元编译器的语言来编写一个XML解析器。这对你来说更容易，运行速度更快，总体上更好。

要了解更多关于这方面的有趣信息，请查看此网站。它以通俗易懂的方式很好地解释了所有这些内容。

- Calum McConnell

3

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

理论：

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

现实生活中的日常工具（商标）在shell中：

你可以使用以下之一：

xmllint，通常与libxml2一起默认安装，xpath1（检查我的封装器以获得换行符分隔的输出

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

Ruby nokogiri. Check this example

PHP DOMXpath. Check this example

检查：使用正则表达式与HTML标签

- Gilles Quénot

2

从纯理论意义上讲，正则表达式无法解析XML。它们的定义方式使它们无法记忆任何先前状态，从而阻止正确匹配任意标签，并且它们无法深入到任意嵌套的层级，因为嵌套必须内置在正则表达式中。

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

例如，考虑以下内容：

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

这将找到下一个正确形成的XML标签或注释，并且只有在其整个内容正确形成时才会找到它。（此表达式已在使用Boost C++的正则表达式库的Notepad++中进行了测试，该库与PCRE非常接近。）

以下是它的工作原理：

第一部分匹配一个注释。这是必要的，因为它需要首先处理任何被注释掉的代码，否则可能会导致问题。
如果不匹配，它将寻找标签的开始。请注意，它使用括号来捕获标签的名称。
该标签要么以/>结束，从而完成标签，要么以>结束，在这种情况下，它将继续检查标签的内容。
它将继续解析，直到遇到<，此时它将递归回表达式的开头，以便处理注释或新标签。
它将继续循环，直到到达文本的末尾或无法解析的<。匹配失败当然会导致它重新开始整个过程。否则，<可能是当前迭代的闭合标签的开始。使用闭合标签内的反向引用<\/\1>，它将匹配当前迭代（深度）的开放标签。只有一个捕获组，所以这个匹配是一个简单的事情。这使得它独立于所使用的标签名称，尽管如果需要，您可以修改捕获组以仅捕获特定的标签。
此时，它要么退出当前递归，进入下一级，要么结束并匹配成功。

这个例子通过使用仅否定<或>的字符组，或者在注释的情况下使用[\S\s]来解决处理空白或通过字符组识别相关内容的问题。它将匹配任何内容，包括回车和换行符，即使在单行模式下，直到遇到-->为止。因此，它会简单地将所有内容视为有效，直到遇到有意义的内容。

对于大多数情况而言，像这样的正则表达式并不特别有用。它只会验证XML是否正确形成，但实际上只能做到这一点，并且没有考虑属性（尽管这很容易添加）。之所以如此简单，是因为它忽略了现实世界中的问题，比如标签名称的定义。如果要适应实际使用，它将变得更加复杂。总的来说，真正的XML解析器要优秀得多。这个解析器可能最适合用于教授递归的工作原理。

长话短说：在实际工作中使用XML解析器，在玩弄正则表达式时使用这个。

- buchWyrm

4

这个说法：“只有输入是格式良好的才能匹配此正则表达式”是不正确的。它没有检查名称是否是有效的XML名称，也没有检查属性，实体和字符引用，也没有处理CDATA或处理指令。当你说这已经被测试过时，我非常怀疑它是否已经在类似XML一致性测试套件的任何东西上进行了测试。这就是我见过的所有尝试使用正则表达式处理XML的问题：它们可以处理少量的输入，但不能处理任何可以合法传递到应用程序中的XML。 - Michael Kay

3

此外，有些格式正确的输入却无法匹配正则表达式。例如，在结束标记中的名称后面不允许出现空格。这些问题大多都很容易解决，但是一旦你修复了所有问题，最终得到的结果可能就完全无法使用了。当然，真正的难点在于你不仅希望解析器提供一个是/否的答案，还希望它将信息传递给能够有用地处理该信息的应用程序。 - Michael Kay

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Jessop · Accepted Answer

关注这个:

有限状态自动机（即正则表达式的底层数据结构）除了当前状态外没有内存，如果您有任意深度的嵌套，则需要一个大小任意大的自动机，这与有限状态自动机的概念相冲突。

正则表达式的定义等价于这样一种事实：可以通过一个有限状态自动机（每个模式对应一个不同的自动机）测试字符串是否匹配该模式。有限状态自动机没有内存-没有堆栈、没有无限的纸带可供涂鸦，它只有有限数量的内部状态，每个状态都可以从被测试的字符串中读取一个输入单元，并使用它来决定下一个要移动到哪个状态。作为特殊情况，它有两个终止状态：“是，匹配成功”和“否，未匹配成功”。

另一方面，HTML具有可以任意嵌套的结构。要确定文件是否为有效的HTML文件，需要检查所有的关闭标记是否与先前的开放标记匹配。要理解它，您需要知道正在关闭哪个元素。如果没有任何记住已看到的开放标记的手段，那么就没有机会。

但请注意，大多数 "正则表达式 "库实际上允许比严格的正则表达式定义更多的内容。如果它们可以匹配反向引用，那么它们已经超出了正则语言。因此，为什么不应该在HTML上使用正则表达式库的原因比HTML不是正则表达式更复杂一些。