There is no day on SO that passes without a question about parsing (X)HTML or XML with regular expressions being asked.
While it's relatively easy to come up with examples that demonstrates the non-viability of regexes for this task or with a collection of expressions to represent the concept, I could still not find on SO a formal explanation of why this is not possible done in layman's terms.
The only formal explanations I could find so far on this site are probably extremely accurate, but also quite cryptic to the self-taught programmer:
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)
or:
Regular expressions can only match regular languages but HTML is a context-free language.
or:
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.
or:
The Pumping lemma for regular languages is the reason why you can't do that.
[The majority of the above explanation link to wikipedia pages, but these are not much easier to understand than the answers themselves].
What is a translation in layman's terms of the formal explanations given above of why it is not possible to use regex for parsing (X)HTML/XML?
I am looking for a translation that also briefly explains the concepts it tries to translate: at the end of an answer, the reader should have a rough idea --for example--of what "regular language" and "context-free grammar" mean.
ベストアンサー1
Concentrate on this one:
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 definition正規表現のテストは、文字列がパターンに一致するかどうかのテストが有限オートマトン (パターンごとに 1 つの異なるオートマトン) によって実行できるという事実に相当します。有限オートマトンにはメモリがありません。スタックもヒープも、書き込み用の無限のテープもありません。有限の数の内部状態だけがあり、各内部状態はテスト対象の文字列から入力の単位を読み取り、それを使用して次にどの状態に移行するかを決定します。特別なケースとして、2 つの終了状態があります。「はい、一致しました」と「いいえ、一致しませんでした」です。
一方、HTML には、任意の深さにネストできる構造があります。ファイルが有効な HTML かどうかを判断するには、すべての終了タグが前の開始タグと一致していることを確認する必要があります。それを理解するには、どの要素が閉じられているかを知る必要があります。これまでに見た開始タグを「記憶する」手段がなければ、チャンスはありません。
ただし、ほとんどの「正規表現」ライブラリは、実際には正規表現の厳密な定義以上のものを許可していることに注意してください。後方参照に一致できる場合、正規言語を超えています。したがって、HTML で正規表現ライブラリを使用すべきでない理由は、HTML が正規ではないという単純な事実よりも少し複雑です。