Nondeterministic, unamigious Grammar?

Question

According to wikipedias GLR description, they "handle nondeterministic and ambiguous grammars." I can visualize an ambiguous grammar, like the dangling else problem, but what's a nondeterministic CF grammar which isn't ambiguous?

Answer 1

Pretty much any non LR(k) grammar is non-deterministic, but not necessarily ambiguous. The obvious is example is when you have some abitrarily large construct that can be parsed two ways, and which is correct depends on something AFTER the large construct. eg:

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

However, such non-deterministic grammars can often be reworked so as to be deterministic, if the two ways of parsing the large construct can be combined (as with S ::= A x | A y for the above grammar which is a deterministic way of parsing the same language.)

More interesting is LANGUAGES that are inherently non-deterministic -- that is there is no deterministic grammar for the language. For that there needs to be something inside the arbitrarily large construct that needs to match what comes after. eg:

S ::= X x | Y y
X ::= a X a | x
Y ::= a Y a | y