🏀 👇🏻 👉 HTTP要求を解析するための状態マシンの作成 🙌 🤒 🧑

確定的な有限状態マシンを使用して、入力シーケンスを解析する非常に高速な方法を実装できます。入力シーケンスのパスは1つだけで、各ステップでのアクションは最小限です。残念ながら、このモデルには制限があります-既存の非決定性有限状態マシン（正規表現、文法）のDFAを常に構築できるとは限りません。または、ビルドが可能であっても、オートマトンの状態が多すぎる場合があります。

それにもかかわらず、DCAに基づいてHTTP要求のパーサーを作成しようとすることにしました。主なタスクは、HTTPリクエストの正確さをチェックするだけでなく、HTTPリクエストフィールドの特定の値に対応する入力行の要素を選択することです。オートマトンは、BNFルール（分散）RFC2616から生成する必要があります。すべてがC＃で実装され、出力マシンもC＃で実装されています。マシンが任意の言語で生成する準備ができている場合、どのような形式でも問題ではないことは明らかです。

DFAを生成するために、次の一連のアクションが実装されています。

1. BNFルールの分析

2. NCAの作成

3. NKAをDKAに変換

4. DKAの最小化

5.ソーステキストと変換テーブルを含むファイルの作成

Ironyを使用してBNF文法を解析しました。ABNF文法はRFC5234で詳しく説明されています。構文ツリーによると、プログラムはトムソンの規則に従ってNKAを構築します。 NFAをDFAに変換して最小化するために標準アルゴリズムが使用されましたが、それらについても説明しません。

HTTPメッセージは比較的単純なオブジェクトであるため、パーサーの出力はHTTPヘッダーに対応するフィールドを持つクラス（これで十分です）です。通過中にマシンがメッセージを解析するために、クラス変数を変更する単純なアクションが生成中にDCAの必要な状態に追加されます。たとえば、Hostヘッダーの値を取得する必要があります。クラスには、ヘッダーの開始と終了の2つの変数があります。マシンがHostフィールドの値を超えたときにトリガーされる状態では、これらの変数を変更するアクションが追加されます。 DKA自体では、実際には、どの州が何に責任があるのかを判断することは不可能です。そのため、NKAの作成時に状態がマークされ、これらのラベルが保存され、オートマトンのすべての変換が行われます。状態のマーキングとアクションの目的を簡素化するために、変数の名前が設定され、変数が受け取る値を指定する単純な言語が作成されました。このデータに基づいて、パーサーが作業の結果を入れるクラスが生成されます。

同様のアプローチが正規表現で使用されます（ただし、すべての実装がDCAへの変換を行うわけではありません）。しかし、マシンに直接アクセスできるため、多くの興味深い最適化を行うことができます。たとえば、Content-Lenghtフィールドにはメッセージ本文の長さが含まれています;このフィールドでは、数値への変換はマシンで直接行われます;出力では、int ContentLenghtクラスのフィールドがあります。別の興味深い最適化、たとえば、HTTP要求に対して一連のメソッド（GET、HOST ...）が定義されています。パーサーの出力で、メソッドに対応する定数をすぐに取得できます。そして、これらすべてをワンパスで。

また、パーサーが入力としてバイトの配列を受け入れることも非常に重要です。これは、文字列がC ++のようにバイトの配列ではないC＃のような現代の言語に特に当てはまります。

一般的に、システムは次のとおりです。 BNF文法と、出力で取得するクラスの説明があります。これらはすべてジェネレータの入力に送られ、DFAをC＃で取得します。既製のマシンを使用すると、次のように作業できます。

dfa.SetDefaultValue(); 
      

        
        
        
      

     dfa.Parse(message0, 0, message0.Length); 
      

        
        
        
      

     dfa.SetArray(message0); 
      

        
        
        
      

     
      

        
        
        
      

     Console.WriteLine("Method: {0}", dfa.Method); 
      

        
        
        
      

     Console.WriteLine("Request-URI: |{0}|", dfa.RequestUri.ToString()); 
      

        
        
        
      

     Console.WriteLine("Host: |{0}|", dfa.Host.ToString()); 
      

        
        
        
      

     Console.WriteLine("Content-Type: |{0}|", dfa.ContentType.Value.ToString()); 
      

        
        
        
      

     Console.WriteLine("Content-Length: {0}", dfa.ContentLength); 
      

        
        
        
      

     Console.WriteLine("Referer: |{0}|", dfa.Referer.ToString());

実際には、HTTP要求のDKAには、1K〜2Kの後に、150Kの状態を最小化するために含まれます。第一に、1K-2Kが実際の使用に十分許容できることは明らかです。第二に、150Kの状態であり、計算にはいくらかのメモリと時間が必要です（少なくとも私の実装では）-分x-tsat。

パーサーの速度は非常に速く、このアプローチの正式な概算は〜* O（n）であり、根本的に改善することはおそらく難しいでしょう。実際、私のマシンのC＃のパーサーは、長さ1Mの220バイトのメッセージを3.3秒で解析できました。

プロジェクトのソースコードが利用可能です： code.google.com/p/siprevo

ジェネレーターの出力でコードを正確にしようとしましたが、ジェネレーター自体はわずかに（控えめに言っても）ドラフト形式でした。このようなシステムは、わずかにグリッチを起こすことがほとんどなく、動作するか動作しないかのどちらかです（この場合は動作します）。

更新：別のユーティリティの形のマシンの「コンパイラ」が ここにあります。

HTTP要求を解析するための状態マシンの作成

More articles: