parsing - この文法は LR(1) ですか?

Question

この文法があいまいであるかどうかについて少し混乱しています

C' -> C
C -> d C u C
C -> d C
C -> ε

このためにDFAを構築しようとしましたが、これは次のいずれかの状態で得られます。

C -> d C DOT u C, $
C -> d C DOT, $

これは shift-reduce の競合ではないので、文法が LR(1) ではないということでしょうか? それとも、$ と u の両方が C の次のセットに含まれているため、関係なく削減されますか?

score 3 · Accepted Answer

シフト削減の競合があります。これは、シフトを選択することによって生成されるステートマシンです。競合は状態 4 にあります。ステートマシン

あなたの質問は少しずれていることを指摘しておきます。文法は明確であり、それでも LR(1) ではありません。

しかし、これは確かにあいまいです。文字列を考えてみましょうddudu。左端の 2 つの派生物は次のとおりです。

C'->C->dCuC->ddCuCuC->dduCuC->ddudCuC->dduduC->ddudu
C'->C->dCuC->ddCuC->dduC->ddudCuC->dduduC->ddudu

これらの存在は、文法が曖昧であると言います。

一般的な文法があいまいであることを証明することは決定不可能な問題です。それに対するアルゴリズムはあり得ません。幸いなことに、これを整理するのはそれほど難しくありません。

1 に答える 1