4

制限付きのユーザー定義の置換ルールを許可するテキスト パーサーを作成しようとしています。

つまり、順序が重要で、行番号を維持する必要がある DOS ASCII ファイルからコードを読み込んでいます。この入力を使用して、ユーザー定義の置換ルールを適用します (この文字列をその文字列と交換し、この文字列の後にその文字列が続く場合は、この変換を実行するなど)。

出力はフォーマットされた DOS ASCII ファイルでもあります。

ルールのほとんどは、tat タイプの置換の代わりに tit を簡単に置き換えますが、将来の任意の時点で A の後に B が続く場合などのルールを定義したい状況があり、このルールを適用します。

これを行うには、構造体のツリーを使用しています。

struct node {
    list<string> common;  // the text which is not affected by conditions
    string condition;     // matching this string selects the left, otherwise the right
    node *lptr, *rptr;    // pointers to the child nodes, if needed
};

このようなルールに遭遇したときはいつでも、ルールが省略され適用された状態で出力を維持し、明確に解決されるまでどちらを使用するかの決定を遅らせることができます。

これは多少メモリを無駄にしますが、入力データを 2 回渡す必要がないようにするには最適な方法のようです (入力データのサイズは不明ですが、おそらく 1 メガ未満です)。

もちろん、このタイプの別のルールが 1 つまたは両方の子ノード内でトリガーされるようなケースが存在する可能性があるため、ツリー構造になっています。

子が親の前に決定されなければならないという制限はありません。親は子の 1 つのブランチでのみ決定可能である可能性があります。EOF に遭遇すると、未決定の子が誤った方向に決定されます。

したがって、ノードを巻き戻したり折りたたんだりするときに注意する必要があることは明らかです。

この一般的な問題に対するより簡単な解決策はありますか? 私のツリーが示すよりも効率的な方法で標準ライブラリ コンテナーを使用する方法はありますか?

4

3 に答える 3

0

「テキストパーサー」とは、コマンドへの反応を簡素化するために、同じ意味の単語やフレーズを要約しようとしていることを意味すると仮定します。

その場合、古いテキスト アドベンチャー プログラムのように、ルールのルックアップ テーブルを使用する単純な左右のパーサーがここで機能します。

問題のドメインを誤解していない限り、ソリューションは非常に過剰に設計されているようです。

于 2012-05-23T21:38:25.940 に答える
0

NFA と DFA、つまり非決定論的有限状態オートマと決定論的有限状態オートマを見たいと思うかもしれません。これら 2 つのアプローチは、パーサーを作成するための最も一般的で、多くの場合非常に効果的な方法です。

ノードにデータを保存する必要は実際にはありません。そうしないと、データが渡されてメモリが浪費されます。これを行うためのより良い方法は、現在の解析状態を追跡するために変数 (int state = 0 など) を割り当てることです。現在の状態と入力に基づいて、アルゴリズムは状態を変更します。状態は常に前進しますが、特定の条件が一致しない場合 (「バックトラッキング」と呼ばれる)、前の状態に戻るようにアルゴリズムに指示できます。

たとえば、「ab」と「ac」が 2 つの有効な入力である場合、「ac」を解析するとき、アルゴリズムは次のようになります。

char is 'a' ==> go to state.checkB
char is not 'b' ==> go back to state.checkA
checkB was already done ==> go to state.checkC
char is 'c' ==> DoSomething();

すべてを完全に説明するには、大量の記事とグラフが必要です。

于 2012-05-23T19:49:13.880 に答える
0

正規表現を試す必要があるようです。ライブラリの選択に関するディスカッションへのリンクは次のとおりです: C++ RegEx Library Choice。ブーストは人気のあるものです。

また、問題に取り組むために別の言語を使用することを検討しましたか? Python には、正規表現 (import re) 用のライブラリを含む、便利なライブラリの優れたベースがあります。操舵室にある場合は、C++ ソリューションよりも簡単な場合があります。

最後に、入力ファイルのカスタム形式ではなく、「定義済み」のテキスト形式を使用することを検討してください。XML は適切な選択です。XML ツリーでルールをネストする方が簡単な場合があります。C++ では、Expat XML パーサーを使用できます (Python は xml.etree.ElementTree になります)。

于 2012-06-14T19:50:26.280 に答える