1

無限先読みを備えた理論上の LR パーサーは、文脈自由文法で記述できる (明確な) 言語を解析できますか?

通常、LR(k) パーサーは決定論的文脈自由言語に制限されています。これは、現在適用できる文法規則が常に 1 つだけ存在する必要があることを意味すると思います。つまり、現在の先読みコンテキスト内では、可能な解析方法は 1 つしか発生しません。「Language Implementation Patterns」という本には、「... パーサーは非決定論的であり、どの選択肢を選択するかを決定できない」と記載されています。先読みセットが重複する場合。対照的に、非決定論的パーサーは、複数の選択肢がある場合は 1 つの方法を選択し、決定ポイントに戻って、ある時点で以前に行われた決定を続行することが不可能な場合は、次の選択肢を選択します。

LR(k) パーサーの定義 (ウィキペディアや Dragon Book など) を読むときはいつでも、「k は先読みトークンの数です」または「k > 1」の場合などを常に読みますが、k が無限になる可能性がある場合は決して読みません。 . 無限の先読みは、成功するまですべての選択肢を試すことと同じではありませんか?

LR(k) パーサーと非決定論的パーサーを (暗黙的に) 区別するために、k は有限であると想定されているのでしょうか?

4

2 に答える 2

1

ここで、短い形式で答えるのが難しいいくつかの問題を提起しています。それでもやってみます。

そもそも「無限先読み」とは？そのようなパーサーについて説明している本はありません。これが何であるか明確な考えがある場合は、最初に説明する必要があります。その後、このトピックについて話し合うことができます。今のところ、構文解析理論では、k が有限である LR(k) 文法についてのみ説明します。

通常、LR(k) パーサーは決定論的文脈自由言語に制限されています。これは、現在適用できる文法規則が常に 1 つだけ存在する必要があることを意味すると思います。

これは間違っています。LR(k) 文法には「文法の競合」がある場合があります。ドラゴンブックは、詳細には触れずに簡単に言及しています. 「文法には競合がある可能性がある」とは、一部の文法には競合がなく、他のすべての文法には競合があることを意味します。文法に矛盾がない場合、ルールは常に 1 つだけであり、状況は比較的単純です。

文法に矛盾がある場合、これは、場合によっては複数の規則が適用されることを意味します。ここでは従来のパーサーは役に立ちません。さらに悪いことに、一部の入力ステートメントには、1 つだけでなく一連の正しい解析が含まれている場合があります。文法理論の観点からすると、これらの構文解析はすべて同じ価値と重要性を持っています。

本「Language Implementation Patterns」には、「... パーサーは非決定論的であり、どの選択肢を選択するかを決定できない」と記載されています。

「非決定論的パーサー」が何を意味するのかについて、明確な合意が得られていないという印象があります。私は、非決定論的パーサーは選択肢の 1 つをランダムに選択して続行すると言いがちです。

実際には、競合を解決するための 2 つの戦略のみが使用されます。1 つ目は、コールバック ハンドラでの競合の解決です。コールバック ハンドラは通常のコードです。それを書くプログラマーは、自分のやりたいことを好きなようにチェックします。このコードは、結果のみを返します。つまり、実行するアクションです。最上位のパーサーにとって、このコールバック ハンドラーはブラック ボックスです。ここには理論はありません。

2 番目のアプローチは「バックトラッキング」と呼ばれます。背後にある考え方は非常に単純です。どこに行けばいいのかわからない。では、考えられるすべての代替案を試してみましょう。この場合、すべてのバリアントが試行されます。ここには非決定論的なものは何もありません。バックトラッキングにはいくつかの異なる種類があります。

これで足りなかったらもう少し書きます。

于 2012-06-14T23:40:51.613 に答える
0

非決定性とは、正しい結果を生成するために、有限状態マシンがトークンを読み取り、N>1 の次の状態を持つことを意味します。ノードに同じラベルを持つ複数の発信エッジがある場合、非決定論的 FSM を認識することができます。すべてのブランチが有効である必要はありませんが、FSM は 1 つだけを選択することはできません。実際には、ここで fork して N 個のステート マシンを作成するか、ブランチを完全に試してから戻って、すべての発信 statetransfer がテストされるまで次のブランチを試すことができます。

于 2012-08-12T18:35:57.750 に答える