parsing - LR パーサーに関する質問

Question

1. 「右端の導出を逆に」と言う代わりに、「左端のリダクション」と言わないのはなぜですか? 同じ意味ですか？読んでいて非常に紛らわしいです。

2. クロージャ セットとは何ですか? また、解析プロセスでどのように役割を果たしますか? 私がインターネットで見つけた一連の講義ノートは、それが何であり、何をするのかを既に知っていることを前提としています。

Answer 1

2 番目の質問に答えるために、「クロージャ セット」はパーサー構築プロセスの一部であり、パーサーに存在する「状態」を識別するために使用されます。状態が識別され、パーサーが構築されると、クロージャー セットはそれ以上の役割を果たしません。つまり、クロージャー セットは実際の解析プロセスでは役割を果たしません。

「クロージャ セット」とは、1 つまたは複数の初期部分解析項目からクロージャによって構築される部分解析項目のセットです。それぞれの固有のクロージャー セットは、1 つの状態にマップされます。閉包集合構築の規則は次のとおりです。集合に「X → α _ A β」という形式の項目が含まれ、文法に「A → δ」という形式の規則が含まれる場合、項目「A → _ δ」をアイテムセット。任意のアイテム セットについて、アイテムを追加できなくなるまでアイテムを繰り返し追加して、クロージャーを計算する必要があります。また、これは先読みを無視します (LR(k) 構築に関連しますが、LALR(1) または SLR(1) 構築には関連しません)。

文法に到達可能な個別のクロージャ セットをすべて決定したら、各セットに一意の「状態」シンボル (通常は単なる整数) を割り当てます。これは、解析時に実行時にパーサー スタックで操作されるトークンです。入力。クロージャ セットの情報は解析にはまったく使用されませんが、正しく指定されていない文法に対して不適切な動作をするパーサーをデバッグするのに役立つ場合があります。