为什么使用正则expression式来parsingHTML / XML是不可能的:用外行人的forms作出正式的解释

在SO上没有一天没有问题parsing(X)正则expression式被问到的HTML或XML。

虽然提出示例说明这个任务的正则expression式不可行,或者用一组expression式来表示这个概念,但是我仍然无法find一个正式的解释,为什么这是不可能的条款。

在这个网站上我能find的唯一正式的解释可能是非常准确的,但对于自学成才的程序员来说也是相当隐晦的:

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

要么:

正则expression式只能匹配常规语言,但HTML是一种上下文无关的语言。

要么:

有限自动机(它是正则expression式下面的数据结构)除了它所处的状态之外没有内存,如果有任意深度的嵌套,则需要一个任意大的自动机,它与有穷自动机的概念相冲突。

要么:

正规语言的抽象引理是你不能这样做的原因。

[公平地说:大多数上述解释链接到维基百科页面,但这些并不比答案本身更容易理解]。

所以我的问题是: 有人可能提供一个非专业人士的正式解释为什么不可能使用正则expression式来parsing(X)的HTML / XML的翻译的翻译?

编辑:在阅读第一个答案后,我想我应该澄清:我正在寻找一个“翻译”,也简要解释了它试图翻译的概念:在答案的最后,读者应该有一个大概的想法 – 例如 – “正规语言”和“上下文无关语法”是什么意思

集中在这一个:

有限自动机(它是正则expression式下面的数据结构)除了它所处的状态之外没有内存,如果有任意深度的嵌套,则需要一个任意大的自动机,它与有穷自动机的概念相冲突。

正则expression式的定义等同于这样一个事实,即一个string是否匹配模式的testing可以通过有限自动机来执行(每个模式一个不同的自动机)。 一个有穷自动机没有记忆 – 没有堆栈,没有堆,没有无限的磁带涂鸦。 它只有一个有限数量的内部状态,每个内部状态都可以从被testing的string中读取一个input单位,并用它来决定移动到下一个状态。 作为特殊情况,它有两个终止状态:“是,那匹配”和“不,不匹配”。

另一方面,HTML具有可以任意嵌套的结构。 要确定文件是否为有效的HTML,您需要检查所有结束标签是否与之前的开始标签匹配。 要了解它,你需要知道哪个元素正在closures。 没有任何手段来“记住”你看过的开放标签,没有机会。

但是请注意,大多数“正则expression式”库实际上允许的不仅仅是正则expression式的严格定义。 如果他们能够匹配反向引用,那么他们已经超越了常规语言。 所以你不应该在HTML上使用正则expression式的原因比HTML不规则这个简单的事实复杂一点。

HTML不代表普通语言的事实是一个红色的鲱鱼。 正则expression式和正则语言听起来很相似 ,但不是 – 它们确实有着相同的起源,但是学术的“正规语言”与目前的引擎匹配能力之间有着明显的距离。 实际上,几乎所有的现代正则expression式引擎都支持非常规特性 – 一个简单的例子是(.*)\1 。 它使用反向引用来匹配重复的字符序列 – 例如123123bonbon 。 recursion/平衡结构的匹配使得这些更加有趣。

维基百科把这个很好地放在拉里·沃尔的引用中:

“正则expression式”与真正的正则expression式只有微小的关系。 尽pipe如此,这个词已经随着我们的模式匹配引擎的能力而增长,所以我不打算在这里反对语言的必然性。 但是,我通常会把它们称为“正则expression式”(regexen)(当我处于盎格鲁 – 撒克逊式的情绪时)。

正如你所看到的,“正则expression式只能匹配正则语言”,只不过是一种普遍的谬误。

那么,为什么不呢?

不把HTML与正则expression式匹配的一个好理由是“仅仅因为你可以不意味着你应该”。 虽然可能是有可能的 – 但只有更好的工具才行 。 考虑到:

  • 有效的HTML比您想象的更难/更复杂。
  • 有效的HTML有很多种types – 例如,在HTML中有效,在XHTML中是无效的。
  • 无论如何 ,在互联网上发现的大部分自由forms的HTML都是无效的 。 HTML库在处理这些问题方面也做得很好,并且经过了许多这些常见的案例的testing。
  • 通常情况下,如果不对整个数据进行parsing,就不可能匹配部分数据。 例如,您可能正在查找所有标题,并最终在注释或string文字内进行匹配。 <h1>.*?</h1>可能是寻找主标题的大胆尝试,但可能会发现:

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

    甚至:

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

最后一点是最重要的:

  • 使用专用的HTMLparsing器比任何你能想到的正则expression式都要好。 通常情况下,XPath允许更好的expression方式来查找所需的数据, 使用HTMLparsing器比大多数人意识到的要容易得多

关于这个主题的一个很好的总结,以及关于混合正则expression式和HTML的一个重要的评论可能是适当的,可以在杰夫阿特伍德的博客: parsingHtml The Cthulhu Way中find 。

什么时候使用正则expression式来parsingHTML更好?

在大多数情况下,最好在库中的DOM结构上使用XPath。 尽pipe如此,反对stream行的意见,有几个案件,当我强烈build议使用正则expression式而不是parsing器库:

鉴于以下几个条件:

  • 当你需要一次性更新你的HTML文件时,你知道结构是一致的。
  • 当你有一个非常小的HTML片段。
  • 如果不处理HTML文件,而是处理类似的模板引擎(在这种情况下可能很难findparsing器)。
  • 当你想要改变HTML的一部分,但不是所有的 – parsing器,据我所知,不能回答这个请求:它将parsing整个文档,并保存整个文档,改变你不想改变的部分。

因为HTML可以无限制地嵌套<tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>和正则expression式无法真正对付这个问题,因为它不能跟踪它下降到什么程度的历史。

一个简单的结构,说明了难点:

 <body><div id="foo">Hi there! <div id="bar">Bye!</div></div></body> 

通用的基于正则expression式的提取例程中,99.9%将无法正确地给我在ID foodiv内的所有内容,因为他们无法从bar div的结束标记中告知该div的结束标记。 那是因为他们没有办法说:“好吧,我现在已经下降到了两个div的第二个,所以我看到的下一个div把我带回来,之后的那个就是第一个” 。 程序员通常会针对具体情况devise特殊的正则expression式,然后在foo内引入更多的标签,然后不得不花费巨大的时间和沮丧来解决这个问题。 这就是为什么人们对整个事情感到愤怒。

常规语言是可以由有限状态机匹配的语言。

(了解有限状态机,下推机和图灵机基本上是大学四年级CS课程的课程。)

考虑下面的机器,它识别string“嗨”。

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

这是识别正规语言的简单机器; 括号中的每个expression式都是一个状态,每个箭头都是一个转换。 像这样构build一台机器将允许您testing任何inputstring对正常语言 – 因此,一个正则expression式。

HTML需要你知道的不仅仅是你所处的状态 – 它需要你以前见过的历史logging,以匹配标签嵌套。 如果将堆栈添加到机器上,则可以完成此操作,但不再是“常规”。 这被称为下推机器,并识别语法。

正则expression式是具有有限(通常相当小)数量的离散状态的机器。

要parsingXML,C或其他任意嵌套语言元素的语言,您需要记住自己有多深。 也就是说,您必须能够计算大括号/括号/标记。

你无法用有限的记忆计数。 可能会有更多的支撑水平比你有状态! 你可能会parsing一些限制嵌套层数的语言子集,但是这将是非常单调乏味的。

语法是一个正式的定义,可以去哪里。 例如,形容词先in English grammar名词,而后跟名词en la gramática española 。 上下文无关意味着在所有情况下普遍的语法。 上下文相关意味着在某些情况下还有其他规则。

在C#中,例如, using System;using System;不同的东西using System; 在文件的顶部,比using (var sw = new StringWriter (...)) 。 一个更相关的例子是代码中的以下代码:

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