2

前文

エラー回復機能を備えた GLR パーサーを作成しました。エラーが発生すると、次の代替手段に分割されます。

  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";

中程度の最新のデスクトップ コンピューターでは、「メモリ不足」で失敗します。

質問

入力エラーが発生した場合に選択肢の数を減らす方法は?

4

1 に答える 1

3

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

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

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

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

于 2010-12-09T18:18:43.600 に答える