7

HTMLやXMLなどの言語で書かれたドキュメントを解析（または「解析」）するために正規表現を使用しないでください。名前が付けられた理由はさまざまであり、ここではそれほど重要ではありません。

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

私の質問は、プログラムやスクリプトでこれを行う方法ではありません。実際の状況では、私は別の機会に車輪を発明しようとはせず、利用可能なフレームワークの1つを使用するだけです。

私が知りたいのは、これらのフレームワークはどのようにそれを行うのかということです。または、フレームワークなしで（仮想的に）それをどのように行うでしょうか？私は具体的にどの言語についても話していません。ドキュメントから情報を抽出する背後にある理論に興味があります。

4

1 に答える 1

8

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

正規言語の認識

通常の言語は、決定論的有限オートマトン (DFA) によって認識されます。DFA は、状態間の遷移エッジと入力バッファー (解析している文字列) を持つ一連の状態です。DFA は開始状態で開始されます。DFA は、入力バッファーの先頭にある文字を読み取り、どのトランジションを取るかを指示します。これにより、DFA は次の状態に移行し、プロセスが繰り返されます。DFA がトランジションを持たない入力文字に遭遇した場合、DFA は終了します (入力は認識されませんでした)。DFA が指定された終了状態に達すると、入力が認識されます

覚えておくべき最も重要なことは、DFA は自分がどの州に行ったかを覚えていないということです。つまり、現在どこにいて、次にどこに行くかだけです。これにより、DFA は特定の種類の言語 (一致する XML タグなど) を認識できなくなります。

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

文脈自由言語の認識

コンテキストフリー言語は、プッシュダウン オートマトンによって認識されます。これらは DFA と同じように機能しますが、スタックが追加されています。プッシュダウン オートマトンは、入力の最初の文字とスタックの一番上の値を使用して遷移を選択します。各ステップで、マシンは 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) もあります。ウィキペディアには、これらすべての手法に関する優れた記事があり、あらゆる種類のパーサーを構築するために利用できる多くのツールがあります。

于 2012-04-26T23:54:53.127 に答える