views:

245

answers:

1

How can it be shown that no LL(1) grammar can be ambiguous?

I know what is ambiguous grammar but could not prove the above theorem/lemma.

+2  A: 

I think it's nearly a direct result of the definition of LL(1). Try proof by contradiction; assume that you have an LL(1) grammar that is ambiguous and look for something you can show to be true and not true. As a starting point "what do you always know as you process input?"

As this seems like a homework problem and I actually haven't finished the problem any more than I sketched out above, I'll stop there.

BCS
BTW, I'm not *sure the conjecture is correct, but it does seem reasonable.
BCS