I am confused on several areas of this. First, this is so obvious I am finding it hard to prove. Second, what are some definitions, axioms, or lemmas of an ll(k) grammar that I can use to build up a contropositive argument that for any ambiguous grammar it cannot be an LL(k) for any k? I've found this to be my best approach. Feel free to answer as opening or as theoretically as felt necessary, this was poorly explained in lecture and quite frankly any addition theory or hints is appreciated.

  • 1
    $\begingroup$ This may help. $\endgroup$ – Raphael Oct 7 '16 at 18:04
  • 1
    $\begingroup$ Are you asking: given a specific LL(k) grammar, how do I prove that it is unambiguous? Or are you asking: how do I prove that every LL(k) grammar is unambiguous? I recommend that you avoid the word "any", because it is often ambiguous whether that means "there exists" or "for all". Can you edit the question to clarify? Also, where have you looked? Have you looked in a standard automata theory textbook? $\endgroup$ – D.W. Oct 7 '16 at 18:40
  • $\begingroup$ Of course, I am reading Peter Linz, Introduction to formal language automata, however there is not much of a section on compiler theory and this seems to be a prevalent topic in that area. I had 1 page of text to read from and quite frankly, all it explained was that it is more strict than an s-grammar. cs.stackexchange.com/questions/2320/…, cs.stackexchange.com/questions/7518/…, and many more that I don't have room to reference here in the comment box because of character limits. $\endgroup$ – bmc Oct 7 '16 at 19:37
  • $\begingroup$ A definition of the syntactic constraints that make grammars LL(k) is conspicuously missing from the Wikipedia article :-( $\endgroup$ – reinierpost Oct 7 '16 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.