Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

LL(1) cannot be ambiguous

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.

like image 614
Prasoon Saurav Avatar asked Apr 17 '10 08:04

Prasoon Saurav


1 Answers

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.

like image 140
BCS Avatar answered Jan 27 '23 06:01

BCS