"*？"の実装（怠惰な "*"）コンビナトリアルGLRパーサーの正規表現パターン

Question

私はコンビナトリアルGLRパーサーを実装しました。それらの中には、指定された文字または文字の範囲を消費するパーサがあります：

• char(·)
• many(·) 0から無限回まで指定されたパーサを繰り返すコンビネータ。

例："char('a').many()"は、任意の数の文字列（"a" -s）と一致します。

しかしmany(·)コンビネータは、たとえば、char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}')は（">>"はパーサのシーケンシャルチェーンである場合）に成功し、全体"{{foo}}some{{bar}}"文字列を消費します、貪欲で、そう。

many(·)の遅延バージョンを実装したいと思います。前の例で使用していたのは"{{foo}}"だけです。どうやってやるの？

編集：

屋すべてのIを混同されることがあります。私のプログラムでは、パーサは「ステップ」を受け取り、「ステップ」のフォレストを返す関数（またはC++の点では「ファンクタ」）です。 「ステップ」は、OK型（パーサが入力の一部を正常に消費したことを意味します）とFAIL型（パーサがエラーに遭遇したことを意味します）の可能性があります。より多くの種類のステップがありますが、それらは補助的です。

Parser = f(Step) -> Collection of TreeNodes of Steps. 

は、だから私は、解析する際に、入力、I：

• 必要な文法を表す複雑な構文解析機能を取得するために、単純な定義済みのパーサ機能を作曲します。

• フォームからの最初のステップ。

• 複雑なパーサー関数に最初のステップを与えます。

• フィルタツリーノードはOKのものだけを残します（入力にエラーがあった場合は最小限のFAIL-sを指定します）。

• 残ったステップの情報を収集します。

Answer 1

正規表現<.*?>と入力<a>bc<d>efを考えてみましょう。これで<a>が見つかり、他の一致はありません。

正規表現<.*?>eと同じ入力を考えてみましょう。これは<a>bc<d>eでしょうか？

これはジレンマを引き起こします。ユーザのために、コンビネータ>>の動作を2つのオペランドの観点から理解したいと考えています。しかし、最初のパーサーが何を見つけるかという観点から、2番目のパーサの動作を生成する方法はありません。各パーサは嗜好によって順序付け全て構文解析の配列、はなく、すべてのパーサーの順不同のセットを生成するため

つの答えです。貪欲なマッチングは、最長から最短のソートされたマッチを返します。貪欲でない、最短から最長。

Answer 2

GLRパーサは入力の可能なすべての解析を生成しませんか？あいまいさを解決することは、あなたが好む解析を選ぶことです。そうするために、パース・フォレストの要素は、どのようなコンビネータがそれを生み出したのか、熱心であるか、または怠惰であるかによって分類する必要があると私は考えています。 （すべての入力を見る前に、曖昧さを段階的に解決することはできません）。

（この回答は、私の曖昧な記憶とGLR解析の曖昧な可能性のある誤解に基づいています。

Answer 3

私はプログラム変換システムの言語フロントエンドとして15年間GLRパーサーを実装し、使用してきました。

「コンビナトリアルGLRパーサー」は何であるか分かりません。私はあなたの表記になじみがないので、私はそれをどのように解釈するのかよく分かりません。私はこれが何らかのカルト関数の表記法だと思いますか？すべての可能を生産、確かに、

char = "a" ; 
char = char "a" ; 

GLR法：私はあなたのコンビネータルールが「charは（ 『A』）は、多くは」ルールを文法に対応し、端末の文字、という点で文法をdefininingと同等であると想像しています解析する。 GLR解析の重要な洞察は、すべての可能な解析の擬似並列処理です。あなたの "コンビネータ"が複数のパースを提案できれば（すなわち、文法規則が上記と同等のものを生成する）、実際にそれらをGLRパーサに接続すれば、それらはすべて試行され、タイル張りのプロダクションのシーケンステキストは生き残ります（すべての有効な構文解析、例えばあいまいな構文解析を意味する）が生き残ります。

実際にGLRパーサーを実装している場合は、このすべての可能なパースの集合が非常にはっきりしているはずです。あなたが実装したことがGLRパーサーではないというヒントではないという事実。

他の解析技術と同様に、GLRパーサーによるエラー回復が可能です。私たちがやっていることは、エラーが発生する前にライブ解析のセットを保持することです。エラーが見つかったときに、GLR構文解析機構は、（擬似並列で、適切に曲がっていればこれを簡単にする）a）トークンを削除する、b）本質的にFOLLOW（x）であるすべてのトークンを挿入する、 xはライブパースです。本質的には、トークンを削除するか、ライブパースで期待されるトークンを挿入します。次に、GLRパーサを再び緩めます。有効な解析（修復など）のみが生き残ります。現在のトークンを処理できない場合、削除されたトークンを持つストリームを処理するパーサは存続します。最悪の場合、GLRパーサーのエラー回復はすべてのトークンをEOFに投げ捨てることになります。これに深刻な欠点は、GLRパーサの実行時間がエラーの解析中にかなり急激に増加することです。ある場所に多くのものがある場合、エラー復旧時間は屋根を通過することができます。

Answer 4

貪欲でない機能は、曖昧さ回避の仕組みにすぎません。あなたが本当に一般化されたパーサー（その結果を生み出すために曖昧さ回避を必要としない）を持っているなら、 "非欲張り"は無意味です。演算子が「非貪欲」であるか否かに関わらず、同じ結果が返されます。

非曖昧な曖昧さ回避動作は、一般化されたパーサーによって提供される完全な結果セットに適用できます。左から右への作業で、貪欲でない演算子に対応するあいまいなサブグループをフィルタリングし、最短一致を使用して、残りの入力の解析に成功しました。