[解決済み] HTML/XMLの解析に正規表現が使えない理由：素人目にもわかる正式な説明

質問

SOでは、正規表現による(X)HTMLやXMLのパースに関する質問がない日はありません。

を思いつくのは比較的簡単ですが、その一方で の例を思いつくのは比較的簡単ですが、このタスクに正規表現が使えないことを実証するために を使うか、あるいは 式のコレクション で概念を表現しても、SOではまだ 形式的な なぜこれが不可能なのかを平易な言葉で説明したものは、SOではまだ見つかりませんでした。

私がこのサイトでこれまでに見つけた唯一の正式な説明は、おそらく極めて正確ですが、独学でプログラマをやっている人にとってはかなり不可解なものでもあります。

ここでの欠陥は、HTML が Chomsky Type 2 文法 (文脈自由文法) であり、RegEx が Chomsky Type 2 文法であることです。 文法）であり、RegEx が Chomsky Type 3 文法（正規表現）であることです。

または

正規表現は正規の言語にしかマッチしませんが、HTMLは文脈自由言語です。 は文脈自由言語です。

または

有限オートマトン(正規表現の基礎となるデータ構造)には は、その状態以外にメモリを持たないので 任意に深いネストを行う場合、任意に大きなオートマトンが必要になります。 これは有限オートマトンの概念と矛盾しています。

または

正則言語のPumping lemmaは、それができない理由です。 ということです。

[公平を期すために：上記の説明の大部分はwikipediaのページにリンクしていますが、これらは答えそのものよりずっとわかりやすいものではありません]。

そこで質問です。 なぜ (X)HTML/XML を解析するために正規表現を使用することができないかについて、上記の正式な説明の平易な用語による翻訳を誰か提供してくれませんか？

EDITです。 最初の回答を読んだ後、私は明確にするべきだと思いました：私はまた、簡単に言えば、"翻訳"を探しています。 を説明します。 例えば、回答の最後には、読者は、「通常の言語」と「文脈自由文法」が何を意味するのか、大まかな考えを持つべきです...。

どのように解決するのですか？

これに集中してください。

有限オートマトン(正規表現の基礎となるデータ構造)は、その状態とは別にメモリを持ちません。 は、その状態以外にメモリを持たず、もし任意の深さの入れ子があれば 任意に深いネストを行う場合、任意に大きなオートマトンが必要になります。 これは有限オートマトンの概念と矛盾しています。

は 定義 は、文字列がパターンにマッチするかどうかのテストが有限オートマトン (パターンごとに異なるオートマトン) によって実行されるという事実と等価である。有限オートマトンにはメモリがない。スタックもヒープも、走り書きをするための無限のテープもない。有限オートマトンは有限個の内部状態を持ち、それぞれがテストされる文字列から1単位の入力を読み取り、それを使って次に移るべき状態を決定することができるだけである。特殊なケースとして、「はい、一致しました」と「いいえ、一致しませんでした」の 2 つの終了状態があります。

一方、HTML は任意の深さにネストすることができる構造を持っています。あるファイルが有効なHTMLかどうかを判断するには、すべての閉じタグが前の開きタグと一致するかどうかを確認する必要があります。それを理解するためには、どの要素が閉じられているのかを知る必要がある。どのような開始タグを見たかを "remember"する手段がなければ、チャンスはないのです。

しかし、ほとんどの "regex" ライブラリは、実際には正規表現の厳密な定義以上のことを許可していることに注意してください。後方参照をマッチさせることができるのであれば、それは正規言語を超えたものです。したがって、HTML上で正規表現ライブラリを使用すべきではない理由は、HTMLが正規表現ではないという単純な事実よりも少し複雑です。