問題タブ [earley-parser]

バック ポインターを使用して Earley パーサーをコーディングしましたが、null 許容文法をうまく処理できません。私は Aycock & Horspool 2002 のソリューションも実装しました。これは、PREDICT が null 可能である場合に非終端トークンをスキップするようにするものです。残念ながら、これは、トークンがイプシロンに到達するために必要な特定のパスを正確に示していません。

私の考え（かなりばかげています）は次のとおりです。

null 許容の非終端記号ごとに、その非終端記号がイプシロンに到達するためのパスのリストを作成します。

null 許容の非終端記号をスキップするたびに、NULL と呼ばれるバック ポインターを追加します。

ツリーを展開しているときは、NULL に遭遇するたびに、その null 許容非終端のリスト内のパスごとに 1 つのツリーのリストを作成します。

最後に、ツリーのリストを調べて、重複を取り除きます。

これにより、アルゴリズムの時間の複雑さが大幅に増加すると思いますが、可能なすべての解析ツリーを生成するためのより効率的な方法は考えられません。

Aycock & Horspool 2002 を実装して解析ツリーを作成するより効率的な方法を提案できる人はいますか?

この投稿http://compilers.iecc.com/comparch/article/02-04-096 に出くわしました。Earley 解析を使用する 2 つの Eiffel コンパイラがあると書かれています。投稿はかなり古いです。どの Eiffel コンパイラが Earley パーサーを使用しているか、またそれらがまだ使用されているかどうかを知っている人はいますか? リンクは大歓迎です。

課題で、次のような関数の CFG を作成するように依頼されました。

def f(x, y): x + y を返す

def g(x, y): x – y を返す

def h(x, y, z): x + y % z を返す

def w(x, y, z): x * y – z を返す

と

def h1(x, y, z): return (x + y) % z

def h2(x, y, z): x + y % z を返す

通常の CFG として作成しようとしましたが、関数定義と関数本体に対してはできませんでした。この種の CFG をどのように開始すればよいかよくわかりません。

私は現在、英語処理用の独自のライブラリを実装することに懸命に取り組んでいます。本当の課題は、豊富な理論資料をすべて調べて、すべてを生産の軌道に乗せる方法を理解することです。

私はこれまでにいくつかの進歩を遂げました。文末検出器と Early パーサーを実装しました。しかし、実際には、端末辞書に特定の単語を含めない限り、パーサーはそれを認識してグラフを作成できません。

より明確にするには、次の CFGrammar の例を確認してください。

その結果、Earley パーサーが「up to」のような未知の 2 語 PP に出くわした場合、それを認識してチャートを作成することに失敗します。

したがって、構文パーサーの前に、文を処理してから関連データをパーサーに転送する何かが必要だと思います。主なアイデアは、POS タグ付けの段階で辞書が動的に構築され、Earley パーサーが単語を認識できるようになるというものです。

トークナイザーとレクサーを実装しました。出力として、次のような S-Expression ツリーを取得しました。

しかし、隠れマルコフ モデルや、最も可能性の高い状態シーケンスを見つけるための Viterbi アルゴリズムやパラメーター推定のための Baum-Welch アルゴリズムなどのアルゴリズムには精通しています。

Earley パーサーと HMM に基づく POS タグ付けをリンクする方法を教えてください。または、おそらく、私は間違った方向に向かっているので、どこが間違っているかを指摘してください。今、私は少し混乱しています。ありがとうございました！

ほとんどの IDE と同様に、IntelliSense を備えたテキストエリアを作成しています。私のアプローチは、earley パーサー アルゴリズムを使用することです。

私はEarly-parser-js ライブラリを使用しています。

以下は文法です：

さて、テキストエリアに「she」と書くと、コードは「eats」、「fish」、「fork」などの次の可能なノードを提案するはずです。