mac*_*mac 110 regex language-agnostic
在没有关于解析(X)HTML或XML并且询问正则表达式的问题的情况下,SO上没有任何日子.
虽然相对容易想出用于演示此任务的正则表达式的不可行性的示例或用表达概念的表达式集合,我仍然无法在SO上找到为什么在外行人中无法做到这一点的正式解释条款.
到目前为止我在这个网站上找到的唯一正式解释可能非常准确,但对于自学成才的程序员来说也很神秘:
这里的缺陷是HTML是Chomsky Type 2语法(无上下文语法)而RegEx是Chomsky Type 3语法(正则表达式)
要么:
正则表达式只能匹配常规语言,但HTML是无上下文的语言.
要么:
有限自动机(它是正则表达式下面的数据结构)除了它所处的状态之外没有内存,如果你有任意深度的嵌套,你需要一个任意大的自动机,它与有限自动机的概念相冲突.
要么:
常规语言的Pumping引理是你不能这样做的原因.
[公平地说:以上大多数解释链接到维基百科页面,但这些并不比答案本身更容易理解].
所以我的问题是:有人可以提供一个外行人的上述正式解释的翻译,为什么不可能使用正则表达式来解析(X)HTML/XML？
编辑:在读完第一个答案之后,我认为我应该澄清:我正在寻找一个"翻译",它也简要地解释了它试图翻译的概念:在答案的最后,读者应该有一个粗略的想法 - 例如 - "常规语言"和"无语境语法"是什么意思......
Ste*_*sop 105
专注于这一个:
有限自动机(它是正则表达式下面的数据结构)除了它所处的状态之外没有内存,如果你有任意深度的嵌套,你需要一个任意大的自动机,它与有限自动机的概念相冲突.
正则表达式的定义等同于以下事实:对于字符串是否匹配模式的测试可以由有限自动机(每个模式的一个不同自动机)执行.有限的自动机没有内存 - 没有堆栈,没有堆,没有无限的磁带可供涂鸦.它只有有限数量的内部状态,每个状态都可以读取被测字符串的输入单位,并用它来决定下一个移动到哪个状态.作为特殊情况,它有两种终止状态:"是,匹配"和"否,不匹配".
另一方面,HTML具有可以任意嵌套的结构.要确定文件是否为有效HTML,您需要检查所有结束标记是否与之前的开始标记匹配.要理解它,您需要知道哪个元素正在关闭.没有任何办法"记住"你看到的开口标签,没有机会.
但请注意,大多数"正则表达式"库实际上不仅允许正则表达式的严格定义.如果他们可以匹配反向引用,那么他们已经超越了常规语言.所以你不应该在HTML上使用正则表达式库的原因比HTML不规则的简单事实要复杂一些.
Kob*_*obi 54
HTML不代表常规语言的事实是一个红色的鲱鱼.正则表达式和常规语言听起来有点相似,但不是 - 它们确实有相同的起源,但学术"常规语言"与当前引擎的匹配能力之间存在显着的距离.事实上,几乎所有现代正则表达式引擎都支持非常规功能 - 一个简单的例子就是(.*)\1.它使用反向引用来匹配重复的字符序列 - 例如123123,或bonbon.匹配递归/平衡结构使这些更加有趣.
维基百科在拉里·沃尔的一句话中说得很好:
"正则表达式"[...]仅与实际正则表达式略有关系.尽管如此,这个术语随着模式匹配引擎的功能而增长,所以我不打算在这里尝试对抗语言需求.然而,我会将它们称为"正则表达式"(或"regexen",当我处于盎格鲁 - 撒克逊的情绪时).
正如你所看到的,"正则表达式只能匹配常规语言",只不过是一种常见的谬误.
不将HTML与正则表达式匹配的一个很好的理由是"仅仅因为你不能意味着你应该".虽然可能 - 但这种工作只有更好的工具.考虑到:
通常,如果不将其整体解析,则无法匹配部分数据.例如,您可能正在查找所有标题,并最终在注释或字符串文字中进行匹配.<h1>.*?</h1>可能是寻找主标题的大胆尝试,但它可能会发现:
<!-- <h1>not the title!</h1> -->
甚至:
<script>
var s = "Certainly <h1>not the title!</h1>";
</script>
最后一点是最重要的:
可以在杰夫阿特伍德的博客中找到关于该主题的一个很好的总结,以及关于何时混合使用正则表达式和HTML的重要评论:解析Html The Cthulhu Way.
在大多数情况下,最好在库可以为您提供的DOM结构上使用XPath.不过,对于流行的观点,有一些情况我强烈建议使用正则表达式而不是解析器库:
鉴于以下几个条件:
Ian*_*uro 18
因为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的结束标记告知该div的结束标记bar.那是因为他们无法说"好吧,我现在已经进入了两个div中的第二个,所以我看到的下一个div关闭让我退出一个,之后的那个是第一个的关闭标记" .程序员通常通过针对特定情况设计特殊情况的正则表达式来做出响应,然后一旦在内部引入更多标签就会中断,foo并且必须以极大的成本及时和挫败地解散.这就是为什么人们对整件事感到生气.
常规语言是可由有限状态机匹配的语言.
(了解有限状态机,下推式机器和图灵机基本上是四年制大学CS课程的课程.)
考虑下面的机器,它识别字符串"hi".
(Start) --Read h-->(A)--Read i-->(Succeed)
\ \
\ -- read any other value-->(Fail)
-- read any other value-->(Fail)
这是一个识别常规语言的简单机器; 括号中的每个表达式都是一个状态,每个箭头都是一个过渡.构建这样的机器将允许您针对常规语言测试任何输入字符串 - 因此,正则表达式.
HTML要求您了解的不仅仅是您所处的状态 - 它需要您之前看到的历史记录,以匹配标记嵌套.如果向计算机添加堆栈,则可以完成此操作,但它不再是"常规".这称为下推式机器,可识别语法.
不使用正则表达式解析 XML 和 HTML 的另一个实际原因与计算机科学理论完全无关：您的正则表达式要么非常复杂，要么是错误的。
例如，写一个正则表达式来匹配都很好
<price>10.65</price>
但是如果你的代码是正确的，那么：
它必须在开始和结束标记中的元素名称之后允许空格
如果文档在命名空间中，那么它应该允许使用任何命名空间前缀
它可能应该允许和忽略出现在开始标签中的任何未知属性（取决于特定词汇的语义）
它可能需要在十进制值之前和之后允许空格（同样，取决于特定 XML 词汇表的详细规则）。
它不应该匹配看起来像一个元素但实际上在注释或 CDATA 部分中的东西（如果有恶意数据试图欺骗您的解析器的可能性，这变得尤其重要）。
如果输入无效，它可能需要提供诊断。
当然，其中一些取决于您应用的质量标准。我们在 StackOverflow 上看到很多问题，人们必须以特定方式生成 XML（例如，标签中没有空格），因为它正在被需要以特定方式编写的应用程序读取。如果您的代码具有任何种类的寿命，那么重要的是它应该能够处理以 XML 标准允许的任何方式编写的传入 XML，而不仅仅是用于测试代码的一个示例输入文档。
正则表达式是具有有限(通常相当小)数量的离散状态的机器.
要使用任意语言元素嵌套来解析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"");
}
";
}
| 归档时间： |
|
| 查看次数： |
24789 次 |
| 最近记录： |