python - 早期パーサー再帰

Question

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

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

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

E : [[E,E],[ident]]

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

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

score 1 · Accepted Answer

はい、次のようなルールのグループで予想される問題があります。

X1 ::= X2

X2 ::= X3

...

Xn ::= X1

この場合、Earley チャートに既に追加した状態をチェックしていないと、アルゴリズムが無限再帰ループに入る可能性があります。

上記の場合、規則 E ::= EE の展開が入力によって制限されるため、無限ループに入ってはなりません。ここで実装を確認してください：

私はすでにこの実装を使用しており、正常に動作します。

1 に答える 1