問題タブ [earley-parser]

Java 出力コードを生成できる、つまり字句解析器とパーサー用の Java コードを生成し、文法規則に対して実行されるアクション (Java コードとして実現) を含めることができるEarley パーサージェネレーターを探しています。

Java コードを生成する 2 つの Earley パーサー ジェネレーター ( PepとPEN ) を調べましたが、いずれもアクションを文法に埋め込むことができないようです。

ウィキペディアで言及されている例を誰かが明確にしてくれれば、とてもうれしいです。

http://en.wikipedia.org/wiki/Earley_algorithm

文法を考えてみましょう:

そして入力：

Earley アルゴリズムは次のように機能します。

これは最初のセット S(0) にすぎませんが、私の質問は、アルゴリズムがステップ (4) で (3) から予測しているのに、(2) からの予測を省略しているのはなぜですか?

誰かがアイデアを理解し、助けてくれることを願っています

NLTKのEarleyパーサーを使用して、次のような文を解析しようとしています。

日付が2010年12月21日より前の場合、シリアル= 10

これを行うには、CFGを作成しようとしていますが、問題は、特定の値ではなく、日付と整数の一般的な形式を端末として使用する必要があることです。プロダクションルールの右辺を正規表現として指定する方法はありますか？これにより、この種の処理が可能になりますか？

何かのようなもの：

これはすべての整数を処理します。

パーサーを手動で作成する必要があります。LL(*) と LR のどちらかを選択できません (Earley を試してみてはいかがでしょうか?)。LL の文法はかなり難しいので、ボトムアップ解析を使用する必要がありますか?

Earley 認識エンジンを作成できました。すべて正常に動作します。私はすべての適切な状況のセットを持っています。しかし、単語が文法で受け入れられるかどうかを判断するためにのみ使用できます。解析するにはどうすればよいですか？何らかの記事や説明が必要です。新しい状況を作成した状況への関連付けを作成する必要があるようです。どんな助けでも大歓迎です。

正確に基づいている私の実装: http://www.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf

文を解析する必要があります。これで、Earleyパーサーとその文法が実装されました。また、文にスペルミスがない場合は、すべてが正常に機能します。しかし、問題は私が扱わなければならない多くの文章が非常に騒々しいことです。解析とエラー修正を組み合わせたアルゴリズムがあるのだろうか？考えられるエラーは次のとおりです。

• 「チェッカー」の代わりに「チェッカー」のタイプミス
• 「スペルチェッカー」の代わりに「スペルチェッカー」のようなタイプミス
• 「アーリーパーサー」の代わりに「アーリーパー」のような収縮

私の質問に答えることができる記事を知っているなら、私はそれにリンクを付けます。

Earley パーサーを高速化するために、算術式のあいまいでない文法を考え出そうとしていますが、問題が発生しているようです。これは与えられたあいまいな文法です

これは、明確にするための私の試みです

すべてをうまく解析しますが、あいまいなものを使用する場合と比較して、大幅な高速化はありません。

文字列がCFGが提供されているCFLの一部であるかどうかを確認するために、さまざまなアルゴリズム（CYKおよびEarley）に出くわしました。簡単に理解して実装できるものを探しています。私が知る必要があるのは、文字列が CFG にあるかどうかです。CFG は通常次の形式で与えられます。

ソリューションは、イプシロン遷移も受け入れることになっています。たとえば、S1-> a | e

何か案は？

Earley パーサーには、単純な循環に関する問題が予想されますか?

私は独自の実装を作成しましたが、これは非常に読みやすく、合計で約 150 行です (もちろん、私が書いたわけではありません)。

http://www.nightmare.com/rushing/python/earley.py

それは私には良さそうに見え、提供されたテストケースで完全に機能しますが、非常に単純な文法

動作しないようです。E が開始非終端記号であり、ident が終端記号であると仮定すると、任意の数の「ident」トークンを生成する必要があります。しかし、この文法、および同様のスタイルの文法は、パーサーによって完全に見落とされます。

これはEarleyアルゴリズムの問​​題ですか（そうではないと思います）、それともこの実装の問題ですか。実装ベースの場合、(比較的) 簡単な解決策はありますか、それともアルゴリズムを再構築する必要がありますか?

Perl の "Marpa" Earley パーサーが非常に優れたエラー レポート機能を備えていることは知っています。

しかし、ドキュメントやグーグルでエラー回復があるかどうかを見つけることができません。

たとえば、ほとんどの C/C++ コンパイラにはエラー回復機能があり、これを使用して複数の構文エラーを報告しますが、他のコンパイラは最初のエラーで停止することがよくあります。

私は実際に自然言語を解析していますが、入力の一部が失敗した後に再同期して解析を再開する方法があるかどうか疑問に思っています。

例、それを理解できる人のために：

ラオス語の音節を解析しています。ラオス語では、いくつかの母音は分音記号であり、別個の文字としてエンコードされ、前の子音の上に表示されます。ラオス語ウィキペディアのランダムな記事を解析しているときに、そのような母音が二重になっているテキストに出くわしました。これはラオス語の正書法では許可されていないため、タイプミスに違いありません。しかし、数文字以内でテキストが再び優れていることがわかります。

とにかく、これは、エラー回復またはトークン ストリームとの再同期に対する私の一般的な関心を刺激した実際の例です。