e4exp
commented
3 years ago - はじめに
パーサーが誤った入力を受け取った場合、シンタックスエラーの存在を示す必要があります。 エラーはさまざまな方法で処理できます。 最も簡単な方法は、エラーが見つかったこと、どこで見つかったか、その時点で期待されていたことを報告して、中止することです。 もう一つの方法は、入力をすべて解析し、できるだけ多くのエラーを報告しようとするものです。 LL(k)法とLR(k)法は、実行可能な接頭辞の特性を持っているため、非常に効率的にシンタックスエラーを検出することができます。 LL(k)パーサーやLR(k)パーサーは、この性質を利用して、一般的ではあるが適切なエラーメッセージを生成することができる。 Parsing Expression Grammars (PEG) [2]は，プログラミング言語の構文を記述するための形式論である． PEGは，記述されている言語のトップダウンパーサの形式的な記述とみなすことができます． PEGは，正規表現（拡張正規表現）の構文に基づいた具体的な構文を持っています． 文脈自由文法（CFG）とは異なり、PEGは順序付き選択演算子を使用することで、文法の言語の定義における曖昧さを回避します。 より具体的には、PEGは制限付き（または局所的）バックトラックを持つ再帰降順パーサーの仕様と解釈できます。 これは，ある選択肢が入力プレフィックスを認識するとすぐに，その選択肢の他の選択肢は試しませんが，ある選択肢が入力プレフィックスを認識できないと，パーサーは次の選択肢を試すためにバックトラックします。 一方で，PEGはトップダウンパーサーの特定のクラスの形式化と解釈することができます[2]． 一方で，PEGは予測型トップダウンパーサーによく適用されるエラー処理技術を使用することができません． なぜなら，これらの技術はパーサーがバックトラックなしで入力を読むことを前提としているからです[3]． バックトラックのないトップダウンパーサーでは、次の入力シンボルが受け付けられなくなった時点で、シンタックスエラーを通知することができます。 PEGでは，エラーの原因と発生位置の特定がより複雑になります． なぜなら，解析中の失敗は必ずしもエラーではなく，パーサーが先に進めず，別の場所で別の選択をすべきことを示しているだけだからです． Ford[3]は，PEGにおけるエラー報告の限界を指摘し，PEG用のパーサジェネレータに，エラー報告を改善するためのヒューリスティックを組み込んでいます。 このヒューリスティックは、バックトラックのないトップダウンパーサーに実装されているエラー報告技術をシミュレートしたものです。 これは、入力の中で最も失敗した位置と、その時点でパーサーが期待していたことを追跡し、エラーが発生した場合にユーザーに報告するというものです。 最も失敗した位置と文脈を追跡することで、他のトップダウンパーサーが自動的に作成するエラーメッセージと同様のエラーメッセージを生成するPEGが得られます。 エラーが発生した位置、その位置の入力に何があったか、パーサーが何を期待していたかをユーザーに伝えます。 本論文では、入力の現在の位置と、解析プロセスに関連した何らかの変更可能な状態にアクセスする可能性を示す意味的なアクションを利用することで、文法作成者が、エラー報告技術を実装していないPEGの実装でも、この技術を利用できることを示します。
また、プログラミング言語に見られる標準的な例外処理メカニズムにヒントを得て、ラベル付き失敗という概念に基づいた、PEGにおけるエラー報告のための補完的なアプローチを提案します。 ラベル付きPEGでは、単に失敗するのではなく、throw演算子を用いてさまざまな種類の失敗ラベルを生成することができます。 それぞれのラベルは、より具体的なエラーメッセージに結びつけることができます。 PEG は順序付き選択演算子を変更することで、そのようなラベル付き失敗をキャッチすることもできる。 我々は、ラベル付き失敗を通常のPEGのセマンティクスの拡張として公式化した。 ラベル付きPEGでは、ローカルバックトラックを持つトップダウンパーサーのためのいくつかの代替エラー報告技術を表現することができます。 また、予測構文解析をPEGに符号化することができ、強力な予測構文解析戦略であるLL(＊)構文解析のための方法を示します。 本論文の残りの部分は以下のように構成されています。 セクション2では、PEGにおけるエラー処理の問題を説明し、失敗追跡ヒューリスティックの詳細を説明し、それを直接サポートしていないPEGの実装でどのように実現できるかを示します。 セクション3では、バックトラックを備えたトップダウンパーサーのエラー報告に関する関連研究を議論します。 セクション4では、ラベル付き失敗の概念を導入して公式化し、エラー報告のためにそれをどのように使用するかを示します。 セクション5では、失敗追跡ヒューリスティックに基づいてパーサーが生成したエラーメッセージと、ラベル付き失敗に基づいてパーサーが生成したエラーメッセージを比較し、セクション6では、ラベル付き失敗がセクション3の技術の一部や予測構文解析をどのようにコード化できるかを示します。
PEG（Parsing Expression Grammars）は、トップダウンパーサーを表現するものです。 残念ながら，従来のトップダウンパーサで使われていたエラー報告の技術は，Parsing Expression Grammars (PEG) に基づくパーサには直接適用できないため，何らかの方法でシミュレーションする必要があります。 PEGの形式論では意味作用は考慮されていませんが、実際のPEGの実装では意味作用が追加されており、これらの意味作用によってエラー報告ヒューリスティックをシミュレートする方法を示します。 また、より良いエラーメッセージを得るために、ラベル付き失敗という補完的なエラー報告戦略を提案します。 このアプローチは、プログラミング言語の例外処理にヒントを得たもので、PEGに様々な種類の失敗を定義させ、各順序選択演算子がどの種類の失敗をキャッチするかを指定します。 ラベル付き失敗は、より良いエラー報告のために文法に注釈をつけたり、決定論的パーサーコンビネータで使われるエラー報告戦略の一部を表現したり、PEGで予測的なトップダウン解析を符号化したりする方法を提供します。