5

カスタム式を含む文字列があり、解析して評価する必要があります。

例えば：

(FUNCTION_A(5,4,5) UNION FUNCTION_B(3,3)) 
INTERSECT (FUNCTION_C(5,4,5) UNION FUNCTION_D(3,3))

FUNCTION_X は、C# で実装され、IList を返す関数を表します。UNION または INTERSECT は、これらの関数から返されるリストに適用する必要があるカスタム関数です。

Union と Intersect は を介し​​て実装されEnumerable.Intersect/Enumerable.Unionます。

解析と評価をエレガントで拡張可能な方法で実装するにはどうすればよいでしょうか?

4

1 に答える 1

5

これは、式がどれほど複雑になるか、使用できる演算子の数、およびさまざまな変数の整数によって異なります。どちらの方法でも、最初にミニ言語の文法を決定する必要があります。

単純な文法の場合は、カスタムパーサーを作成するだけです。多くの計算機や同様のアプリケーションの場合、再帰下降パーサーは文法を処理するのに十分な表現力があり、直感的に記述できます。リンクされたウィキペディアのページには、サンプルの文法とそのためのCパーサーの実装が記載されています。Eric Whiteには、C＃での再帰下降パーサーの構築に関するブログ投稿もあります。

より複雑な文法の場合は、これを自分で作成する作業をスキップして、lex / yaccタイプのレクサーおよびパーサーツールセットを使用することをお勧めします。通常、これらへの入力としてEBNFまたは同様の構文の文法を指定すると、入力を解析するために必要なコードが生成されます。パーサーは通常、トラバースできる構文ツリーを返し、入力ストリーム内の各トークン（ツリー内の各ノード）にロジックを適用できるようにします。C＃については、GPLexとGPPGを使用しましたが、 ANTLRなどの他のものも利用できます。

基本的な構文解析の概念

一般に、入力内の各アイテムを意味のあるトークンに分割し、それらのトークンに基づいてツリーを構築できるようにする必要があります。ツリーが構築されたら、ツリーをトラバースして、各ノードで必要なアクションを実行できます。の構文ツリーはFUNCTION_A(5,4,5) UNION FUNCTION_B(3,3)次のようになります。ノードタイプは大文字で、値は括弧で囲まれています。

                        PROGRAM
                           |
                           |
                         UNION
                           |
            ------------------------------
           |                              |
  FUNCTION (FUNCTION_A)          FUNCTION(FUNCTION_B)
        |                                 |
  -------------                       ----------
 |      |      |                     |          |
INT(5) INT(4) INT(5)                INT(3)     INT(3)

パーサーは、aが見つかったときに、ユニオンなどに2つのアイテムを提供する必要があることを知るのに十分スマートUNIONである必要があります。このツリーが与えられると、ルート（PROGRAM）から開始し、深さ優先走査を実行します。ノードでのアクションは、UNION最初にすべての子を訪問し、次に結果を結合することです。ノードでのアクションは、FUNCTION最初にすべての子を訪問し、それらの値を見つけて、それらの値を関数のパラメーターとして使用し、次にそれらの入力で関数を評価して値を返すことです。

これは、思いつく可能性のあるすべての式について、すべてのトークンに対して継続されます。このように、パーサーに適切なツリーを生成させるために時間を費やし、各ノードが必要なアクションを実行する方法を知っている場合、設計は非常に拡張可能であり、設計された文法に一致するすべての入力を処理できます。

于 2012-10-18T15:44:36.720 に答える