問題タブ [dfa]

Google で検索してみましたが、必要なものを見つけるための適切な検索フレーズを取得できないと思います。afterNET IRC サーバーに精通している場合、8 ボールであるコマンド「.8」があります。はい/いいえの質問だけではありません。いつ、どこで、色など、質問で使用する特定の単語に基づいて、さまざまな回答が得られます。

このようなものを作りたいのですが、どこから始めればよいかわかりません。最近、DFA (Deterministic Finite Automata) を勉強しましたが、そこから始めるべきですか? 人々が使用する単語のすべての可能な組み合わせをスクリプト化したいわけではないことは理解していますが、(IRC サーバーの 8ball プログラムのように) 少し現実的に感じられ、より多くの「単語」に拡張可能なシステムがあればいいと思います。 ' いつでも。

ヘルプ/リンクをありがとう！

正規表現のリストを受け入れ、これらの正規表現をそれぞれ対応する最終状態に認識する最小のDFAの画像を生成するツールはありますか？

次のようになります。http：//i.imgur.com/Vxw9X.jpg 写真は、おそらく教師自身が作成したスタンフォード大学のコンパイラクラスから取得したものです。このFAはPascalトークンのサブセットを処理し、番号付き/文字付きの状態は最終状態です。

DFAの実際のコードは必要ありません。それがどのように見えるかを示すだけです。

そのようなツールがない場合、この種のグラフを作成するにはどうすればよいですか？それを行う特殊なPythonGUIライブラリの種類はありますか？

無制限の文字列シーケンスと、優先度順に並べられた多数の正規表現があります。シーケンス内の各文字列について、最初に一致する正規表現と一致する部分文字列を見つける必要があります。文字列はそれほど長くはありませんが (<1Kb)、正規表現の数は数百から数千までさまざまです。

この仕事を効率的に行う Java ツールを探しています。この手法は、DFA を先に構築する必要があると思います。

私の現在のオプションは JFLEX です。JFLEX で回避できない問題は、ルールに優先順位がなく、JFLEX がテキストの最も長い部分に一致するルールを探すことです。

私の質問は、私の問題が JFLEX で解決できるかどうかです。そうでない場合は、別のJavaツール/テクニックを提案できますか?

すべての状態を一連の状態として入力として受け取るプログラムがあります。次に取得される入力は、一連の状態の最初の状態であり、次に一連の最終状態です。

次は、状態間で私がとる遷移のセットです。

例えば：q0,1,q1

これは、入力 1 で q0 から q1 への遷移があることを意味します。

状態ごとに遷移が入力されます。

しかし、ここで私が直面しているのは、参照がランダムな方法でジャンプアップできることです。つまり、トランジションは、重複しない文字のトランジションの数になる可能性があるため、この原因は、各状態のハッシュマップオブジェクトを動的に維持したいということです。

どうすればこれを達成できますか？

Lexer DFA で「コードが大きすぎます」というエラーが発生する

ANTLR 3 を使用して Java Server Pages を解析しようとしています。

Java には、1 つのメソッドのバイト コードに対して 64k の制限があり、ANTLR によって生成された Java ソースをコンパイルするときに、「コードが大きすぎます」というエラーが発生し続けます。

場合によっては、レクサーを妥協することで修正できました。たとえば、JSP は XML の「名前」トークンを使用しますが、これにはさまざまな文字を含めることができます。「名前」トークンでは ASCII 文字のみを受け入れることにしました。これにより、一部のテストが大幅に簡素化され、レクサーでコンパイルできるようになりました。

しかし、これ以上手を抜くことはできないところまで来ましたが、DFA はまだ複雑すぎます。

私はそれについて何をすべきですか？

複雑な DFA の原因となるよくある間違いはありますか?

おそらく予測に役立つセマンティック述語または固定先読みに依存して、DFAの生成を禁止する方法はありますか?

この字句解析器を手で書くのは簡単ですが、ANTLR をあきらめる前に、明らかなことを見落としていないことを確認したいと思います。

バックグラウンド

ANTLR 3 レクサーは、DFA を使用して、入力をトークン化する方法を決定します。生成された DFA には、 というメソッドがありspecialStateTransition()ます。このメソッドにはswitch、DFA の各状態のケースを含むステートメントが含まれています。各ケース内にはif、状態からの遷移ごとに 1 つの一連のステートメントがあります。各ifステートメントの条件は、入力文字をテストして、遷移に一致するかどうかを確認します。

これらの文字テスト条件は非常に複雑になる場合があります。通常、次の形式をとります。

lexer に小さな変更を加えたように見えるだけで、1 つの遷移に対して数十回の比較が行われ、各状態に対して複数の遷移が行われ、多数の状態が発生する可能性があります。考慮されている状態のいくつかは、私のセマンティック述語のために到達できないと思いますが、セマンティック述語は DFA によって無視されているようです。(ただし、読み間違えている可能性があります。このコードは、私が手で書くことができるものではありません!)

Jsp2x ツールで ANTLR 2 の文法を見つけましたが、その構文木に満足できず、ANTLR のスキルをリフレッシュしたいので、自分で書いてみようと思いました。私は ANTLRWorks を使用しており、DFA のグラフを生成しようとしましたが、ANTLRWorks にはそれを妨げるバグがあるようです。

文字列を渡されたときに「はい」または「いいえ」を返すリモート「エージェント」があります。このエージェントとの通信にはコストがかかるため、正と負のフィードバックを与えられた正規表現を反復的に構築できるライブラリを見つけたいと思っています。これにより、送信側で回答をキャッシュできます。

たとえば、エージェントに「良い」と問い合わせて、「はい」を受け取ったとします。最初に派生した正規表現は「良い」はずです。

次に「goop」でクエリを実行し、「yes」を受け取ったとします。派生した正規表現は、「good|goop」ではなく「goo[dp]」になると思います。

などなど。

派生した正規表現では、バックトラッキングやその他の派手な非線形時間操作は必要ありません。おそらく、生成された正規表現は内部の DFA になります。これを実行できる c/c++ 正規表現ライブラリを知っている人はいますか? あるいは、これがばかげた考えである理由と、実際の問題に対するより良い解決策も役立ちます。

有限数の一致を持つ特定の正規表現へのすべての一致のセットを見つける方法を知りたいです。

例えば：

^これらの例はすべて、次で始まり、次で終わると想定できます$

また、正規表現の一意の解を取得する方法があるかどうか、または正規表現に有限の解があるかどうかを判断する方法があるかどうかにも興味があります。

アルゴリズムが任意の正規表現を解析できればいいのですが、十分に強力な正規表現のサブセットであれば問題ありません。

この問題に対する PHP ソリューションに興味がありますが、他の言語でも問題ありません。

編集：

形式理論のクラスで、正規表現 (およびその他の正規言語) の実装に使用できるDFAについて学びました。正規表現を DFA に変換できれば、解決策はかなり簡単に思えますが、その変換はかなり難しいように思えます。

編集2：

すべての提案に感謝します。この質問に「答える」ために取り組んでいる公開 github プロジェクトに関する私の投稿を参照してください。

通常、DFAは、指定された文字列が特定の言語で存在するかどうかを確認するために使用されます。たとえば、_ab1cはCの変数の言語に存在します。

私は何をしていますか？ しかし、この質問で述べたように、私はすべてのコメント、文字列などをトレースするためにDFAを使用しています。

調子はどう？ 特定の文字列/プログラムの//コメントをトレースする例を考えてみましょう。

このために、私が持っている場合、

私の質問は...

この方法で//コメントの終了と開始をマークするためにDFAを使用できますか、またはCFGなどの他の方法に従う必要があります。

すなわち

私の声明：DFAを使用して、特定の言語をチェックするだけでなく、特定の文字列内の特定の言語に属する特定の文字列を追跡することもできます。（証明：上記の方法による）。

上記のステートメントは正しいですか？

この質問で述べたように、DFA を使用してすべてのコメント、文字列などを追跡しています。この DFA は 11 の状態で終了しました。

今、Java でキーワードを認識する DFA を作成しようとしています。

考え：

最初は pos=0 です。pos は遷移ごとに 1 ずつインクリメントされます。

iskeyword() は私自身の関数です。

isalnum() は、将来の要件に応じて、任意のユーザー定義関数に置き換えることができます。

(実際の DFA には存在しますが、関連のない多くのトランジションとセルフ ループは提供されません)。

(q0) -- !isalnum(pos)-------> (q1) ---iskeyword(pos,pos+len)---> (pos+=len)(q2)----- ! isalnum(pos)-------->(q3[読み取ったキーワードをBOLDにする])---iskeyword(pos,pos+len)-->(q2).

少なくとも 4 つの州が必要です。上記の方法は、通常の DFA の実装とはかなり異なります。

私の質問は....

1. 上記の方法でよろしいでしょうか？それに従うのは正しいですか？（それが機能する場合）
2. 上記の方法でこれを実装する必要がある場合、どうすればそれを行うことができますか? 読みやすさを向上させるために別の DFA を構築しますか? または、このDFAをコメント、文字列を認識するDFAと組み合わせることができますか（状態の数を減らすため）

(ab u aab u aba)*

私はそれをしましたが、その正しさについてのフィードバックが欲しいです:

正しければ: (ab u aab u aba)* をさらに単純化できますか?

そうでない場合: 何を見逃しましたか?

編集: 3 つの最終状態すべてから初期状態に戻る e トランジションが欠落しているようです。e トランジションで古い初期状態に移動する初期および最終の新しい状態が必要です。（クリーネスタールール）。

PS と を単純化することもできます(a u b)*aababか(a u b)*a(a u b)(a u b)(a u b)(a u b)。

単純化/最小化する方法がない場合、非常に長いDFAになるため、私が尋ねる理由...