11

私は現在、スキャナージェネレーターに取り組んでいます。ジェネレーターはすでに正常に動作しています。しかし、文字クラスを使用すると、アルゴリズムが非常に遅くなります。

スキャナー ジェネレーターは、UTF8 でエンコードされたファイル用のスキャナーを生成します。文字の全範囲 (0x000000 から 0x10ffff) をサポートする必要があります。

任意の演算子「.」などの大きな文字セットを使用する場合 または Unicode プロパティ {L}、nfa (および dfa) には多くの状態 (> 10000) が含まれています。そのため、nfa から dfa への変換と最小の dfa の作成には長い時間がかかります (出力の最小の dfa に数個の状態しか含まれていない場合でも)。

これが、nfa の文字セット部分を作成する私の現在の実装です。

void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters)
{
transitions[startStateIndex] = CreateEmptyTransitionsArray();
foreach (int character in characters) {
    // get the utf8 encoded bytes for the character
    byte[] encoded = EncodingHelper.EncodeCharacter(character);
    int tStartStateIndex = startStateIndex;
    for (int i = 0; i < encoded.Length - 1; i++) {
        int tEndStateIndex = transitions[tStartStateIndex][encoded[i]];
        if (tEndStateIndex == -1) {
           tEndStateIndex = CreateState();
               transitions[tEndStateIndex] = CreateEmptyTransitionsArray();
        }                   
        transitions[tStartStateIndex][encoded[i]] = tEndStateIndex;
        tStartStateIndex = tEndStateIndex;
    }
    transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex;
}

必要な状態のみを作成するために関数をより効率的に実装する方法を知っている人はいますか?

編集：

より具体的には、次のような関数が必要です。

List<Set<byte>[]> Convert(Set<int> characters)
{
     ???????
}

文字 (int) を UTF8 エンコーディング byte[] に変換するヘルパー関数は、次のように定義されます。

byte[] EncodeCharacter(int character)
{ ... }
4

5 に答える 5

3

それを処理する方法はいくつかあります。それらはすべて、アルファベット全体をまったく列挙するのではなく、データ構造で一度に文字のセットを処理することに要約されます。また、妥当な量のメモリで Unicode 用のスキャナを作成する方法でもあります。

文字セットを表現および処理する方法については、多くの選択肢があります。私は現在、境界条件と対応するターゲット状態の順序付きリストを保持するソリューションに取り組んでいます。各接合点でアルファベット全体をスキャンする必要がある場合よりも、これらのリストの操作をはるかに高速に処理できます。実際、Python で許容できる速度で実行できるほど十分に高速です。

于 2010-08-24T16:04:35.790 に答える
2

Google RE2 や TRE などの正規表現ライブラリが何を行っているかを見てください。

于 2010-08-22T20:03:34.393 に答える