解析HTML的最佳正则表达式是什么(尽管你不应该这样做)?是否存在完美的正则表达式?

5

好的,我们都知道使用正则表达式解析HTML会招致可怕的后果。这一点非常清楚。而且有一些很好的回答解释了为什么你不应该这样做。我接受了这些回答,并在问题上多次发布了这些链接。

但是让我们将这个问题放在以下范围内:我们没有其他选择,只能使用正则表达式来解析HTML。为什么?并不重要。但是暂时假设我们的开发人员想要失去理智,尝试最好的方法来做到不可能的事情。如果这让你感到震惊,请认为这是一个理论问题。无论你喜欢什么,只要考虑使用正则表达式解析HTML的想法,即使你不应该这样做。

在这里,我们看到一个说法,即这是不可能的,至少不能完美地完成。但是下面有一个非常明智的评论来自@NikiC:

这个答案从错误的论点中得出了正确的结论(“使用正则表达式解析HTML是一个坏主意”)。当人们现在说“正则表达式”(PCRE)时,大多数人指的是可以很好地解析上下文无关文法(实际上这是微不足道的),也可以解析上下文相关文法(参见https://dev59.com/DWs05IYBdhLWcg3wIObS#7434814)。
事实上,你可以用现代正则表达式做一些非常强大的事情,即使有些冗长。但许多人把这个问题说得像停机问题一样:你可以尝试,但总会有另一个情况,你的解决方案会失效。 所以问题来了,它有点复杂。
  • 是否可能生成一个完美的正则表达式来解析HTML?
    • 如果是这样,证明是建设性的吗?我们只是知道我们可以吗,还是已经完成了?
  • 如果不可能,那么最准确的正则表达式是什么?

1
网页上HTML页面的问题主要在于缺乏验证,如果HTML得到验证,那么我们就可以为该特定HTML版本创建一个正则表达式。如果您需要一个特定的已验证HTML(如XHTML 1.0),那么没有什么能阻止我们这样做 :) - Hawili
@Hawili 我很乐意使用XHTML。只是有很多人在那里扔出“不可能”的词。甚至有一个网站主题是“把你的正则表达式带给我,我会用我的HTML打破它”。我也看到了一些聪明的例子,比如经典的<div title="blah >" id="tricky"> - Nick
8
@ngmiceli说:这不是声称正则表达式不能解析HTML,而是事实。正则表达式可以描述类型3的Chomsky语言(正则语言),而HTML(以及大多数其他编程/标记语言)是类型2的Chomsky语言(上下文无关)。前者是后者的子集。因此,正则表达式只能描述HTML的一个子集。“Big-foot”是一种主张。这是一个事实。 虽然PCRE能够做比纯粹的正则表达式更多的事情,但通过使用其高级特性,您仍将编写某种上下文无关的解析器,它也只能解析有效的HTML(因此需要X/HTMLtidy预处理)。 - Regexident
是的,你可以编写一个正则表达式来解析HTML,假设所有的HTML文档都有一些上限长度。如果你将其扩展到PCRE,我相信你可以解析任意长度的HTML,但我不确定。 - Snowball
1
我不完全确定为什么这个被关闭了。我只是想知道是否可能。这是一个事实,而不是主观讨论。提供的答案回答了我的问题。在我看来,它似乎非常可靠。 - Nick
显示剩余7条评论
1个回答

19

首先让我们明确一点:

正则表达式与HTML解析不兼容并非是一个断言。跟我重复一遍:“不是一个断言”。

这是一个经过科学证实和广为人知的事实。此外,世界也不是在7天内创造出来的,大脚怪也不存在。讨论结束。


我們將此問題限定在以下範圍內:除了正則表達式,我們沒有其他選擇來解析HTML。為什麼?這並不重要。有趣的是,你寫了"這不重要"。事實上,"為什麼"才是決定你計劃做什麼的部分可能或完全不可能的關鍵。如果有一件事很重要,那就是"為什麼"。如果"為什麼"是"驗證",那麼答案就是:根據定義,不可能。驗證需要100%的語言覆蓋率。而正則表達式作為上下文無關語法的子集,因此不能覆蓋100%。然而,如果"為什麼"是"提取",那麼使用正則表達式可以得到相當好的結果。永遠不會100%可靠,但對於大多數情況而言足夠好了。事實上,現代正則表達式可以做出一些非常強大的事情,即使寫法相當冗長。
这种正则表达式的长度、冗余和复杂性表明,虽然用正则表达式描述有效的电子邮件地址并非不可能,但至少是相对困难的,并且实际上更像是一个暴力字典列表,而不是一个干净的语法。顺便说一下:日期字符串验证更糟糕。首先是闰年。
为了说明我对“验证”和“提取”的区别:
要验证一个简单的电子邮件地址,需要一个巨大的6400多个字符的正则表达式。
然而,从电子邮件地址中“提取”域名只需要简单的@([^\s]+)(?<=@)[^\s]+就可以覆盖几乎(如果不是完全)100%。假设字符串被隔离并已知为有效的电子邮件地址。
“生成解析HTML的完美正则表达式是否可能?”你基本上自己回答了这个问题:“不可能”。
那么,这个证明是否具有建设性?我们只知道我们可以吗,还是已经完成了?

这并不是因为“没有人能做到吗?”而是因为“已经被数学证明是不可能的!”。QED

如果不可能,那最准确的是什么?

鉴于根据定义它是不可能的,唯一正确的答案是“没有一个”。

用于解析所有(或尽可能多的)HTML的正则表达式的最佳近似是类似于x | y | z | …的无限长的正则表达式模式,其中x、y、z…是HTML语法的所有(蛮力强制)可能构成,在逻辑上连接在一起,形成了无限长的逻辑OR。它将是一个适当的正则表达式(甚至符合正则表达式的最真实条件),覆盖HTML的所有部分(毕竟它列出并匹配所有可能的字符串),只是理论上可能(或者至少是可行的,就像图灵机一样),但实际上完全无用


Regex可以描述第三类乔姆斯基语言(正则语言),而HTML(以及大多数其他编程/标记语言)是第二类乔姆斯基语言(上下文无关)。正则语言是上下文无关语言的一个子集。类型n的语法总是可以覆盖类型(n-x)的语言的子集,但永远不可能覆盖全部。因此,正则表达式只能描述HTML的一个子集。大脚怪是一种说法。这是一个事实。

严格的左或右扩展正则表达式没有平衡或嵌套的理解(既不是"S→aSa"也不是混合线性"S→aA,A→Sb,S→ε")。因此,你无法解析HTML。

"S→aSa"(平衡嵌套)的一个快速示例:

<div>
    <div>
        ...
    <div>
<div>

没错,HTML/XML 的核心与正则表达式不兼容。从一开始就是个相当糟糕的位置,不是吗?使用正则表达式解析 HTML 实际上是在其核心部分腐败。设计有缺陷,注定会失败。

对于 "S→aA,A→Sb,S→ε"(计数):

无法验证每行正确匹配的 <td> 数量:

<table>
    <tr>
        <td>1</td>
        <td>2</td>
        <td>3</td>
        <td>4</td>
    </tr>
    <tr>
        <td>1</td>
        <td>2</td>
        <td>3</td>
        <td>4</td>
    </tr>
</table>

请注意:一旦您减少对语言“X”的识别范围,您就不再是在识别语言“X”,而是一个新的自包含子集语言“Y”。
在语言领域中,要么全有,要么全无。没有中间状态。
现在有人说PCRE可以做到这一点!是的,那就是无上下文语法。
但是,它不再是正则表达式,因此无法通过测试:
“我们别无选择,只能使用正则表达式。”
而且,仍然是错误的工具。针对这些任务有专门的解析器。使用它们。
邮件匹配的正则表达式(由OP链接)难以阅读,更难以维护。
(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(
?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]
|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)
?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]) ... (6400+ chars)

以下是同一规范的一部分,以适当的无上下文语法形式呈现:

 address     =  mailbox                      ; one addressee
             /  group                        ; named list
 group       =  phrase ":" [#mailbox] ";"
 mailbox     =  addr-spec                    ; simple address
             /  phrase route-addr            ; name & addr-spec
 route-addr  =  "<" [route] addr-spec ">"
 route       =  1#("@" domain) ":"           ; path-relative
 addr-spec   =  local-part "@" domain        ; global address
 local-part  =  word *("." word)             ; uninterpreted
                                             ; case-preserved
 domain      =  sub-domain *("." sub-domain)
 sub-domain  =  domain-ref / domain-literal
 domain-ref  =  atom                         ; symbolic reference

有些人在面对HTML时,会想到“我知道了,我会使用正则表达式。”现在他们有了两个指标级的问题。

那么告诉我,为什么有人会真的远到决定使用甚至想要做得更像呢?


1
@ridgerunner: 正则表达式是PCRE的子集。 PCRE的扩展正则表达式是无环文法(就像您链接中所述)而不是正则表达式。虽然它们在技术上可以完全解析类型-2语言,但PCRE在处理HTML规范中的所有变化和常常不清楚/模糊的标准等解析复杂性时将会是错误的工具。即使仅仅因为与专门的无环文法解析器相比不易读懂(请参见电子邮件验证)。虽然理论上可以破解盐SHA512,但尝试这样做是否切实可行? 能够技术上做到X并不意味着应该这样做。 - Regexident
3
语义学!在讨论“正则表达式”时,我指的是现代所有语言中都具备的“regex”模式匹配功能,这些功能在 Friedl 的(优秀的)书中得到了详细介绍。其中更强大的工具能够准确、快速、高效地处理嵌套结构。你所提到的理论“REGULAR”表达式已经不再使用。对于任何敢于将“REGEX”和“HTML”一起提及的问题,所引起的负面反应都是不合理的。 - ridgerunner
2
我并没有说所有现代正则表达式引擎都支持递归(但是强大的Perl、PHP和.NET确实支持)。我说的是所有现代正则表达式引擎都是非[REGULAR](http://kore-nordmann.de/blog/do_NOT_parse_using_regexp.html#comment_40)的(而且已经很长时间了)。 - ridgerunner
“能够做到X并不意味着应该这样做。”这句话似乎是一种奇怪且没有建设性的说法,与此相应的关于PCRE的补充部分也是如此。据我所见,没有人声称应该这样做;问题的标题明确表示“(即使你不应该)”;需要说多少次才行? - Don Hatch
也许我比较慢(或者是没听懂笑话?),但我已经读了最后一句话“为什么地球上的任何人都会真正远到决定使用甚至想要做得更像?”10次,但我仍然没有成功解析它。也许我需要一个正则表达式? - Don Hatch
显示剩余6条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接