parsing - 発生してはならない人為的な LR 文法の競合

Question

引用符で囲まれた文字列が終端記号であると想定される、次のような LR 文法の試みを検討してください。

S: E
E: ("y" | "z") X A
E: ("y" | "z") X B
X: "x"
X:  X "x"
A: "a"
B: "b"

これは競合のない LR(1) 文法であるように思われます。

S: E
E: ("y" | "z") X (A | B)
X: "x"
X:  X "x"
A: "a"
B: "b"

それでも、私は（？）現実世界のパーサーは機械的にそれを

S: E
E: U X A
E: V X B
U: "y"
U: "z"
V: "y"
V: "z"
X: "x"
X:  X "x"
A: "a"
B: "b"

ここでU、とVは、解析ツリー内の子によって直接置換されるシンボルです。

結果の文法は LR(∞) です。LR(k < ∞) の reduce-reduce 競合があります - 実際にはそうすべきではないという事実にもかかわらず!

ここで、この例をもっと複雑にすることが可能であることに気付きました (たとえば、論理和だけでなく反復も使用します)。実際、私の知る限り、そのような状況を検出することは、2 つの文脈自由文法の同等性をテストすることになります。これは (私の記憶が正しければ) 決定不可能な問題です。

私の質問は：

0 に答える 0