エラー回復を伴うGLRパーサー：入力にエラーがある場合の代替が多すぎます

Question

前文

エラー回復を伴うGLR-Parserを書きました。エラーに遭遇すると、次の選択肢に分割されます。

1. 予想される要素を入力に挿入し（ユーザーが見逃しただけかもしれません）、通常どおり続行します。
2. 誤った要素を予想される要素に置き換え（ユーザーが間違いを作成したばかりかもしれません）、通常どおりに進めます。
3. 誤った要素をスキップし、次の要素も誤っている場合は、＃2に移動します。

しかし、入力に多くのエラーがある場合（たとえば、ユーザーは誤ってJPEGファイルをパーサーに与えた場合）、多くの代替案が指数関数的に増加します。

例

次の文法に対応するこのようなパーサー：

Program -> Identifier WS Identifier WS '=' WS Identifier
Identifier -> ('a'..'z' | 'A'..'Z' | '0'..'9')*
WS -> ' '*

次のテキストに適用されます。

x = "abc\"def"; y = "ghi\"jkl";

適度に最新のデスクトップコンピューターで「Out Of Memory」で失敗します。

質問

入力のエラーが発生した場合に代替品の数を減らす方法は？

Answer 1

文字レベルでGLR（したがって解析）エラー補正を行うことは可能ですが、問題を悪化させます。

使用するGLRエラー回復手順はトークンで動作するため、それほど悪くはありません。

しかし、入力に膨大な数のエラーがある場合、回復するのはかなり困難です。より洗練されたエラー回復スキームは、基本的にパーサーを使用して有効を識別します サブストリング 入力内の言語の後、結果を得るためにサブストリングにパッチを合わせようとします。それはかなり野心的です。

エラー回復を伴うGLRパーサーを構築しました。私はそれほど野心的ではありませんでした。一般に、パーサーは、ライブパーサーの数が「多数」（たとえば、10,000）を超えるか、遭遇した構文エラーの数（例：10または20）を超えると、ほとんどが中止されます。最後の瞬間に入力ストリームを進めていない場合、パーサーを中止することを検討するかもしれません。これは、ライブパーサーが多すぎる間接的な兆候です。