一般に、文脈自由文法が明確かどうかは判断できないことを私は知っています。ただし、これは、文脈自由文法のサブセットについてこれを決定できないことを意味するものではありません。
文法は、入力テキストを構文木に変換するために使用されます。与えられた入力に対して複数の構文木を生成できる場合、その文法はあいまいです。
LR パーサー アルゴリズムは、最初に文法を LR パーサー テーブルに変換します。その後、LR パーサー オートマトンを使用して、LR パーサー テーブルを使用して特定の入力ストリームを解析ツリーに処理します。通常、最初のステップはパーサー ジェネレーターによって実行され、2 番目のステップは解析操作ごとに実行されます。
LR パーサー テーブル構築アルゴリズムを考えてみましょうconstruct(G) = T | error。アルゴリズムは文脈自由文法を受け取りますG。テーブルの構築が成功すると、競合のない LR パーサー テーブルTが返されます。テーブルの構築に失敗した場合、エラーが返されます。このようなアルゴリズムの例は、SLR、LALR、および CLR です。アルゴリズムの失敗の典型的な例は、shift-reduce および reduce-reduce の競合です。
有限の入力ストリームと競合のない LR パーサー テーブルの場合、LR パーサー オートマトンは、指定された入力ストリームから 1 つの解析ツリーを決定論的に導出するか、入力ストリームが文法と一致しない場合にエラーを返すことができます。解析ステップは次のように形式化できますparse(T, I) = O | error。ここTで、 は競合のない LR 解析テーブル、Iはトークンの入力ストリームO、単一の解析ツリーです。入力ストリームが文法に一致しない場合、エラーが返されます。
質問
上記のステートメントを要約すると、競合のない LR パーサー テーブルに何らかの方法で変換できる文法は明確です。ただし、アルゴリズムがエラーを返した場合、これは文法があいまいであるかどうかについてのステートメントを意味するものではありません。したがって、LR テーブル構築アルゴリズムは、文脈自由文法のサブセットが明確であるかどうかを半決定します。これは正しいです？
私の結論が失敗する可能性のあるいくつかのステップを次に示します。
- LR テーブル構築アルゴリズムが終了しない可能性があります
- LR パーサー オートマトンが終了しない可能性があります
- LR テーブル構築アルゴリズムが正しくないため、LR パーサー オートマトンは、構築元の文法とまったく同じセットの入力ストリームを受け入れないか、文法とは別の解析ツリーを導出します。
私の知る限り、上記のどれも一般的な LR テーブル構築アルゴリズムには当てはまりません。
これについて明確な声明を見つけることができなかったので、説明と、この質問が議論され、明確に回答されている参考文献をいただければ幸いです。
私の結論が正しければ、LR パーサーはその言語で書かれたすべてのプログラムを適切に解析できるようにするため、この質問はプログラミング言語を設計する際に非常に重要だと思います。文法が明確であることを保証する他の方法はありますか?