サンプルデータからのパーサー文法の作成

Question

私は、文法を作成するのに役立つものが何であるかを見て回りました。さまざまなIDEがありますが、文法ファイル自体で動作するテキストエディタのようです。私は、データ中心のアプローチから何かを探しています。だから、パーサーと解析したいデータの例がたくさんあるとしましょう。だから、私はそのサンプルデータを処理し、そこから直接文法を定義したいと思っています。

このようなことをする既存のソフトウェアはありますか？私はより明確にしようとするつもりだ

...

私は、ユーザーがデータサンプルにロードされた場所になります言及していたデータ中心のアプローチ。次に、フィールドであることを示す項目を選択するか、項目を選択して区切り記号などとしてマークします。

ほとんどのIDEとは対照的に、文法言語自体で書くためのテキストエディタがあります。

Answer 1

任意の有限の文字列が通常の言語を構成します。そのような言語を受け入れるNFAを書くことは自明である。これから、サブセット構成を使用してDFAを生成し、DFAが区別不能関係の等価クラスごとに1つの状態だけを必要とするという事実を使用して、DFAを最小化することができます。したがって、完全にアルゴリズム的なプロセスです...正規表現や文法を取得することは、同様に簡単です。

言われているように、あなたは文字列を生成する文法を生成したい場合、おそらく他のもの...あなたの問題は悪い考えです。任意の有限集合の文字列に対して、無限に多くの文法がそれらと他の文字列を生成します。目標のデータセットをヒットしている限り、他の文字列を生成することができるという事実に由来する数字の無限です。あなたの質問は本質的に、「シーケンスa1、a2、...、an、...の始まりが与えられれば、次のn個の要素が何であるか」ということです。 答えが必要な場合を除き、これは不可能です。この場合は、常にDFAから始めて、これを一般化する方法を提案することができます（つまり、より多くの文字列のみを受け入れることができます）。例えば、通常の文法では、新しい文字列を導入するのは簡単です...最初の答えを開始場所として使用します。しかし、NFAからDFAへの変換は、漸近的に指数関数的に非効率的である可能性があることに注意してください。

Answer 2

私はあなたをFSAに制限するのではなく、文法がないかどうかにかかわらず文法に制限したいと思います。私はhttp://en.wikipedia.org/wiki/Grammar_inductionを見ることをお勧めします。そこにアルゴリズム（申し訳ありませんが、ソフトウェアではない）のいくつかの議論があるようです。