regex - 为什么无法使用正则表达式解析 HTML/XML : a formal explanation in layman's terms

Question

SO 上的每一天都会询问有关使用正则表达式解析 (X)HTML 或 XML 的问题。

虽然相对容易想出 examples that demonstrates the non-viability of regexes for this task或使用 collection of expressions为了表达这个概念，我仍然找不到正式解释为什么这不可能用外行人的术语来完成。

到目前为止，我在这个网站上能找到的唯一正式解释可能非常准确，但对于自学成才的程序员来说也相当神秘:

the flaw here is that HTML is a Chomsky Type 2 grammar (context free grammar) and RegEx is a Chomsky Type 3 grammar (regular expression)

或者:

Regular expressions can only match regular languages but HTML is a context-free language.

或者:

A finite automaton (which is the data structure underlying a regular expression) does not have memory apart from the state it's in, and if you have arbitrarily deep nesting, you need an arbitrarily large automaton, which collides with the notion of a finite automaton.

或者:

The Pumping lemma for regular languages is the reason why you can't do that.

[上面的大部分解释都链接到维基百科页面，但这些并不比答案本身更容易理解]。

上面给出的关于为什么不能使用正则表达式解析 (X)HTML/XML 的正式解释的通俗易懂的翻译是什么？

我正在寻找一种翻译，它还可以简要地解释它试图翻译的概念:在答案的最后，读者应该对“常规语言”和“上下文无关语法”的含义有一个粗略的了解。

Answer 1

专注于这一点:

A finite automaton (which is the data structure underlying a regular expression) does not have memory apart from the state it's in, and if you have arbitrarily deep nesting, you need an arbitrarily large automaton, which collides with the notion of a finite automaton.

正则表达式的定义相当于可以通过有限自动机(每个模式有一个不同的自动机)来执行字符串是否与模式匹配的测试。有限自动机没有内存——没有堆栈，没有堆，没有可以在上面乱写乱画的无限磁带。它所拥有的只是有限数量的内部状态，每个内部状态都可以从正在测试的字符串中读取一个输入单元，并使用它来决定下一步要移动到哪个状态。作为特殊情况，它有两种终止状态:“是，匹配”和“否，不匹配”。

另一方面，HTML 具有可以任意深度嵌套的结构。要确定文件是否是有效的 HTML，您需要检查所有结束标记是否与之前的开始标记匹配。要理解它，您需要知道哪个元素正在被关闭。如果没有任何方法来“记住”您所看到的开始标签，就没有机会。

但请注意，大多数“正则表达式”库实际上不仅仅允许正则表达式的严格定义。如果它们可以匹配反向引用，那么它们就超越了常规语言。因此，为什么不应该在 HTML 上使用正则表达式库的原因比 HTML 不规则这一简单事实要复杂一些。