問題タブ [dfa]

F# で記述されたオープン ソース ライブラリをお勧めできますか?FA の構築と基本的なアルゴリズム (NFA から DFA への変換、FA の最小化など) のジェネリック型を提供します。

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

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

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

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

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

編集：

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

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

私は現在、コンパイラとパーサーのアーキテクチャについて読んでいますが、1 つのことについて疑問に思っています... XML、XHTML、HTML、または SGML ベースの言語を使用している場合、ここでのレクサーの役割とトークンは何でしょうか?

トークンは、 lexerによる解析用に準備された単語のようなものだと読んだことがあります。キーワード、名前、リテラル、その他の単語のような文字列が空白で区切られている C、C++、Pascal などの言語のトークンを見つけることに問題はありませんが、XML では問題があります。どんな言葉でも！これは、マークアップ (タグ) がインターリーブされたプレーン テキストのみです。

これらのタグとプレーンテキストの断片がトークンである可能性があると思いました[TXT][TAG][TAG][TXT][TAG][TXT][TAG][TAG][TXT]...。SGML はマークアップ区切り文字の内部にあるものを気にせず<(>まあ、それが見つかったとき、?または!次の文字として特別な処理命令と定義を認識します。コメントもそのグループに属します)、SGML トークナイザーはXML/HTML/XHTML パーサーのベースになります。

しかし、その後、他の構文の一部としてマークアップ内に文字が詰め込まれる可能性があることに気付きました<:エディターはそれを処理し、これらをタグ区切り文字ではなく、属性値の一部として扱います。<&lt;<

レクサーの単純な決定論的有限オートマトン (DFA) によってそのようなマークアップを認識する方法が見当たらないため、少し複雑になります。オートマトンがタグ内にある場合は別のコンテキストが必要であり、属性値に遭遇した場合は別のコンテキストが必要なようです。これには状態/コンテキストのスタックが必要になると思うので、DFA はそれを処理しない可能性があります。私は正しいですか？

あなたの見解は？タグ（マークアップ）とプレーンテキストからトークンを作るのは良いですか？

ここ: http://www.antlr.org/wiki/display/ANTLR3/Parsing+XML
は、ある種の異なる手法を使用しています: それらは<and >(および and も</)/>を個別のトークンとして扱い、タグ内ではGENERIC_IDトークンとして使用します。 .通常、ほとんどの作業をパーサーに移します。しかし、トークナイザーのコンテキストも変更する必要があります。プレーンテキストでは異なるコンテキストを使用し、マークアップでは異なるコンテキストを使用します (しかし、属性値のコンテキストを忘れていたと思います>。

では、SGML に似た言語を解析するための最良のアプローチは何でしょうか? レクサーは本当にそこで使われていますか？はいの場合、どの文字列がトークンを構成していますか?

DFA に関する質問 (Determinant Finite Automata) があります。オートマトンの構築には JFLAP を使用しています。私の命を救うためにこの質問を理解することはできません！ここにあります

「偶数のゼロと奇数の 1 を持つすべての文字列の言語を認識する DFA。」

したがって、アルファベットは {0,1} で、0,1 のみを使用します。そのため、偶数のゼロと奇数の 1 を認識するオートマトンを構築する必要があります。

2つのDFA（決定性有限オートマトンまたは決定性有限状態マシン-これ以降はDFAと呼びます）セットで定義DFA 1：L1 = {Q1、E、D1、s1、F} DFA 2：L2 = {Q2、 E、D2、s2、F}

Qは状態のリストです。例1、2、3、4またはa、b、c、d

Eは言語例です。0、1

DはトランジションセットExです。{（a、0、b）}状態aは0でbになります

sは開始状態です

Fは最終状態です

どのように、排他的に、または2つのDFAL1とL2を使用しますか

DFA を表すのに最適なデータ構造は何でしょうか?

正規表現を DFA に変換し、この特定の機能を Java のライブラリとして作成することを検討しています。

主なことは、正規表現の各エンティティは、 "car" のような単一の文字列値ではなく、値のセットを運ぶということです。私の場合、各エンティティには {car, Honda, 4x4, sedan, ... } などの多くのプロパティがあります (車を検索しているわけではありませんが、これは単なる例です)。

助言がありますか？

上限は 2^n であり、これらが両方とも有限のマシンであることを考えると、n 状態 NFA と 2^n 以下の状態を持つ DFA の両方の交差が有効になるため、そう考えています。

私はここで間違っていますか？

NFA または DFA の遷移テーブルを記述するための標準構文はありますか?

機能と制限に基づいて、DFAエンジンとNFAエンジンの違いについての非技術的な説明を探しています。

おやすみなさい、

トランジションが .NET ディクショナリ構造に格納されている NFA/DFA を実装し、入力単語を受け取り、入力から何らかの方法で派生可能な一連の単語を認識するクラスがあるとします。さらに、オートマトンが、遷移文字のラベルを付け直すだけで、同じ長さの異なる単語に適用できる汎用テンプレートであるとします。実行時に入力単語の文字に従ってトランジションを再ラベル付けできるように、ディクショナリでトランジション関数をエンコードする最良の方法は何ですか?

どうもありがとうございました。