バック ポインターを使用して Earley パーサーをコーディングしましたが、null 許容文法をうまく処理できません。私は Aycock & Horspool 2002 のソリューションも実装しました。これは、PREDICT が null 可能である場合に非終端トークンをスキップするようにするものです。残念ながら、これは、トークンがイプシロンに到達するために必要な特定のパスを正確に示していません。
私の考え（かなりばかげています）は次のとおりです。
null 許容の非終端記号ごとに、その非終端記号がイプシロンに到達するためのパスのリストを作成します。
null 許容の非終端記号をスキップするたびに、NULL と呼ばれるバック ポインターを追加します。
ツリーを展開しているときは、NULL に遭遇するたびに、その null 許容非終端のリスト内のパスごとに 1 つのツリーのリストを作成します。
最後に、ツリーのリストを調べて、重複を取り除きます。
これにより、アルゴリズムの時間の複雑さが大幅に増加すると思いますが、可能なすべての解析ツリーを生成するためのより効率的な方法は考えられません。
Aycock & Horspool 2002 を実装して解析ツリーを作成するより効率的な方法を提案できる人はいますか?