HTML/XML文書の解析はどのように機能しますか？

Question

私は他人に非常に頻繁に言われるように言われました。HTML、XMLなどの言語で書かれた文書を解析（または解析）するために正規表現を使用しないでください。 。

代わりに何をするべきか尋ねられたら、通常は、PHP拡張やJSフレームワークなどのドキュメントを解析するためにライブラリを参照します。ほとんどの場合、ドキュメントオブジェクトモデルに依存しているようです。

私の質問は、プログラムやスクリプトでこれを行う方法ではありません。現実の状況では、別の時間にホイールを発明しようとせず、使用可能なフレームワークの1つを使用します。

私が知りたいことは - これらのフレームワークはどうしていますか？または、私はそれをどのようにしてなしでフレームワーク（仮説的に）ですか？私は特定の言語について話しているわけではありません。文書から情報を抽出する理論に興味があります。

Answer 1

XMLを解析するには、「コンテキストフリー言語」と呼ばれるものを認識できるツールが必要です。正規表現は、文脈自由言語のサブセットである通常の言語を認識します。

正規言語が決定性有限オートマトン（のDFA）によって認識される正規言語を認識

。 DFAは、状態間の遷移エッジと入力バッファ（解析する文字列）のセットです。 DFAは開始状態で開始します。 DFAは、入力バッファの先頭にある文字を読み取ります。これは、どのトランジションにかかるかを示します。これにより、DFAが次の状態に移行し、プロセスが繰り返されます。 DFAが入力文字に遭遇した場合、その文字は変換されず、終了します（入力が認識されませんでした）。 DFAが指定された終了状態に達すると、入力が認識された

最も重要なことは、DFAがどのような状態になったのかを覚えていないことです。次へ行く。これにより、DFAは、一致するXMLタグなどの特定のタイプの言語を認識することができなくなります。

PCREのような正規表現の実装には、便宜上（ '+'、 '？'、および文字クラスなど）、正規表現の機能を変更するもの（先読みや逆参照など） 。これらの正規表現はDFAよりも強力ですが、これらの拡張正規表現だけでXMLパーサを構築することは困難または不可能です。

認識文脈自由言語

文脈自由言語はプッシュダウンオートマトンによって認識されています。これらはDFAのように機能しますが、スタックが追加されています。プッシュダウンオートマトンは、入力の最初の文字であるとをスタックの先頭に使用してトランジションを選択します。各ステップで、マシンは1つの入力文字を消費し、スタック上の値をプッシュするか、1つをポップするか、スタックに何もしません。

プッシュダウンオートマトンはスタックを使ってどこにいたのかを覚えておくことができ、XML（またはほとんどのプログラミング言語）の解析に適しています。

XMLを解析

パーサは、プッシュダウンオートマトン、あなたがDFAを設計することにより、通常の言語を認識しないのと同じ方法を設計することにより構築されていません。コンテキストフリーの文法は、文脈自由な言語を記述するためのより良い方法です。彼らは通常Backus-Naur Form（BNF）で書かれています。ここではXMLのサブセットのための簡単なBNF文法です：

Tags ::= Tag Tags | <nothing> 

Tag ::= "<" /[a-zA-Z]+/ Attributes ">" Document "</" /[a-zA-Z]+/ ">" 

Attributes ::= Attribute Attributes | <nothing> 

Attribute ::= /[a-zA-Z]+/ "=" "\"" /[a-zA-Z0-9 ]+/ "\"" 

この文法は非端末（「タグ」、「タグ」、「属性」、および「属性」）で構成されています。ルールの右側に非終端記号が現れるところでは、可能な定義（|で区切られた）のいずれかに置き換えることができます。引用符と正規表現のテキストは端末であり、入力と正確に一致しなければなりません。

タグ非終端記号は開始タグと終了タグを認識し、その間に非タグタグを付けます。パーサが開始タグを認識するたびに、もう一方の側で終了タグを見つけることが期待されます。タグは1つのタグを認識し、タグをもう一度認識します。この再帰的な定義により、パーザは無限の数のタグを認識することができます。

パーサージェネレータは、文脈自由文法をプッシュダウンオートマトンに変えて入力言語を認識させるツールです。パーサーを構築するには、複雑さが掛かりますが、文法を正確に指定することには多くの課題があります。あなたが手でステートマシンを構築せずに、または文脈自由文法を書くことでパーサを書くことができ

を解析するための

その他の方法。通常、これは、再帰的降下パーサまたは解析される言語に関する特別な知識を持つ正規表現を使用する手作業によるパーサのいずれかで行われます。再帰的降下パーサは文脈自由文法のように見えますが、いくつかの重大なパフォーマンス上の問題や機能上の制限があります。正規表現とBNF文法のハイブリッドのように動作する構文文法（PEG）も解析されています。 Wikipediaのこれらすべてのテクニックに関するすばらしい記事と、あらゆる種類のパーサーを構築するための多くのツールがあります。