1

ウィキペディアのGLRの説明によると、「非決定論的で曖昧な文法を処理します」。ぶら下がっているelse問題 のように、あいまいな文法を視覚化することはできますが、あいまいではない非決定論的なCF文法とは何ですか？

4

1 に答える 1

3

LR（k）以外の文法はほとんど決定論的ではありませんが、必ずしもあいまいではありません。明らかな例は、2つの方法で解析できる、非常に大きな構成があり、どちらが正しいかは、大きな構成の後の何かに依存する場合です。例えば：

S ::= A x | B y
A ::= A a | a
B ::= B a | a

ただし、このような非決定性の文法は、大きな構成を解析する2つの方法を組み合わせることができる場合（S ::= A x | A y同じ言語を解析する決定性の方法である上記の文法の場合と同様）、決定性になるように作り直すことができます。

さらに興味深いのは、本質的に非決定論的である言語です。つまり、言語に決定論的な文法はありません。そのためには、後に続くものと一致する必要がある任意の大きな構造の中に何かが存在する必要があります。例えば：

S ::= X x | Y y
X ::= a X a | x
Y ::= a Y a | y
于 2012-08-12T19:57:05.303 に答える