正则表达式和HTML不混合的根本原因是什么？它背后的理论？

Question

首先,我不能做任何事情,只能参考我认为最有名的SO帖子:

现在,它甚至是StackOverflow的问题吗？我不知道,但我会试试......

我会从个人的角度讲.虽然我从来没有这样做,但我知道在我必须解析HTML的那一天,我肯定不会使用正则表达式; 我将尝试找到一个HTML解析库.精细.

但我不知道为什么.

有一次,我决定用Java进行CSS验证.我知道"通过胆量",正则表达式不会削减它,所以我使用了Parboiled.

我不知道为什么.

"为什么"让我烦恼.我根本不是正念法的新手.我只是不能在正则表达式引擎之间划清界限,也不能做.

我的问题如下:这条线是什么？必须存在输入的基本特征,以便在数学上证明任何正则表达式引擎都无法可靠地确定成功和失败？

你能给出一个简单的理论输入,这个输入会使正则表达式引擎能够提供可靠的"匹配/不匹配"答案吗？如果是,这种输入的定义特征是什么？

编辑为了这个讨论,我将添加一个帖子在SO上建议的任务(我现在找不到链接,抱歉)这比HTML简单,但我不会使用正则表达式:shell命令行解析.

就shell而言,这些是等价的:

alias ll="ls -l"
alias ll=ls\ -l
alias l"l"=ls' -'l
"alia"s l"l= "ls\ -l

Shell引用机制如此众多,以至于我只会在这种情况下创建一个Parboiled语法......但这是"出于我的勇气".因为我觉得它可能更容易......但这并不能证明这对正则表达式来说是不可行的.

Answer 1

正则表达式可以确定常规语言.但HTML不是常规语言.它是一种无上下文的语言.无上下文语言是常规语言的超集.

基本上任何可以在其中具有递归元素的语言都不是常规的.常规语言必须"平坦",因此不能嵌套.例如,在HTML中,一个<div>可以嵌套在另一个中,并且它们可以嵌套的深度没有限制.正则表达式无法处理的是这种类型的通用嵌套.

这是误导.术语含糊不清.最初术语"正则表达式"具有特定含义.编程语言发明了正则表达式引擎.但是这些引擎的功能增强(反向引用,外观,递归模式......).原始的"常规语言"都是可识别的,这已经不再适用了.例如`/ ^(a*)b\1 $ /`识别字符串`b`,`aba`,`aabaa`,`aaabaaa`,...; 不正常的语言.如果你真的想要,我认为你可以写一个正则表达式来测试HTML有效性.(你没有.)在实践中,会有一个库,但在你的情况下,正则表达可能更容易. (5认同)
请注意,虽然有'html`标签(可能是一个错误？),但我没有特别提到HTML; 另外,一些正则表达式引擎允许递归(例如,PCRE和`(？R)`;即使这样,一些输入也会逃避这些引擎确定成功和失败的能力.这就是我不知所措的地方. (3认同)
我同意这个答案是简化.在所有流行的编程语言中实现的正则表达式比常规语言更匹配.它以反向引用开始(虽然这对嵌套结构没有帮助),并以PCRE中的递归结束(如fge所述)和.NET中的平衡组.显然(根据OP关联主题的评论),PCRE甚至是图灵完整的.问题当然是大量有效的语法变体(甚至没有提到无效的HTML). (2认同)