解析HTML的最佳正则表达式是什么(即使你不应该)？有一个完美的吗？

Question

好吧,我们都知道尝试使用Regex解析HTML 会带来Cthulhu的愤怒.很好.对于你为什么不应该这样做,有一些很好的回应.我接受这些,并且不止一次在问题上发布这些链接.

但是让我们把这个问题放在以下范围内:除了Regex之外,我们没有解析HTML的选项.为什么？没关系. 但是,假设我们的开发者目前想要失去他们对Tony the Pony的想法,并尽可能地做出不可能的事情.如果这让你大吃一惊,那么假设这个问题是理论性的.无论什么漂浮你的船.只考虑用正则表达式解析HTML的想法,即使你不应该.

在这里,我们看到一种声称,它是不可能做到的,至少是完美的.但是@NikiC下面有一个非常明智的评论:

这个答案从错误的参数中得出了正确的结论("用正则表达式解析HTML"这是一个坏主意)("因为HTML不是常规语言").大多数人现在所说的"正则表达式"(PCRE)不仅可以解析无上下文的语法(实际上是微不足道的),而且能够解决上下文敏感的语法(参见https://stackoverflow.com/) a/7434814/1222420)

事实是,即使相当冗长,你也可以使用现代正则表达式来做一些非常强大的事情.但是很多人认为这个问题听起来像是停机问题:你可以尝试,但总会有另一种情况,你的解决方案会破坏.

所以这就是问题,而且它有点像两个部分.

• 是否有可能为解析HTML生成一个完美的正则表达式？
  • 如果是这样,证明是否具有建设性？我们只知道我们可以,或者已经完成了吗？
• 如果不可能,那么最准确的是什么？

Answer 1

首先让我们直截了当:

正则表达式"与HTML解析不兼容是不是一个要求.在我之后重复:" 不是索赔 ".

这是一个科学证明和众所周知的事实.更进一步,世界不是在7天内创造的,大脚也不是真实的.讨论结束.

但是让我们把这个问题放在以下范围内:除了Regex之外,我们没有解析HTML的选项.为什么？没关系

有趣的是你写的并不重要.鉴于," 为什么 "实际上是使你计划做的部分可能或完全不可能的原因.如果这里有一件事重要,那就是" 为什么 ".

如果" 为什么 "是" 验证 ",则答案是按照定义:不可能.验证要求不低于100%的语言覆盖率.而正则表达式,作为无上下文语法的子集,因此无法覆盖100%.根据定义.

如果" 为什么 "是" 提取 ",那么使用正则表达式可以获得相当好的结果.从不100%可靠,但对大多数情况来说足够好.

事实是,即使相当冗长,你也可以使用现代正则表达式来做一些非常强大的事情.

这种模式的绝对长度,冗余和复杂性表明,虽然在正则表达式中描述有效的电子邮件地址可能并非不可能,但它至少是不成比例的困难,并且实际上更像是一个强力字典列表,而不是一个干净的语法.虽然我们正在努力:日期字符串验证更糟糕.闰年只是开始.

将" 验证 "和" 提取 "区分开来:

要验证简单的电子邮件地址,需要一个单一的6400+字符长正则表达式.

要从电子邮件地址" 提取 "域名,但是简单@([^\s]+)或(?<=@)[^\s]+将覆盖几乎(如果不完全)100%.假设字符串是隔离的并且已知是有效的电子邮件地址.

是否有可能为解析HTML生成一个完美的正则表达式？

你基本上通过写"完美"来回答这个问题:不.

如果是这样,证明是否具有建设性？我们只知道我们可以,或者已经完成了吗？

这不是"只是没有人设法做到了吗？" 但更多关于"它在数学上被证明是不可能的!".QED

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

鉴于它的定义不可能,唯一正确的答案是"无".

用于解析所有(或尽可能多)HTML的正则表达式的最佳近似将是一个无限长的正则表达式模式,沿着x|y|z|…x,y,z的行...是所有(强制强制)HTML链接语法的可能产生在一个无限长的逻辑OR中.这将是一个正确的正则表达式(即使是最正式的正则表达式),覆盖所有HTML(它列出并因此匹配所有可能的字符串),只在理论上可行(或至少可行,就像图灵机一样)和几乎完全没用.

正则表达式可以描述类型3乔姆斯基语言(常规语言),而HTML(和大多数其他编程/标记语言)是类型2乔姆斯基语言(无上下文).在正规语言是一个子集上下文无关语言.类型-n的语法总是可以覆盖类型 - (nx)语言的子集,但绝不能涵盖所有类型的语法.因此,正则表达式只能描述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时会想"我知道,我会使用正则表达式".
现在他们有两个公尺f*cktons的问题.

所以告诉我.为什么到目前为止,任何人都会真的走得更远甚至决定使用甚至想要看起来更像？