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
    Commented Oct 7, 2016 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.
    Commented Oct 7, 2016 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
    Commented Oct 7, 2016 at 19:37
  • $\begingroup$ A definition of the syntactic constraints that make grammars LL(k) is conspicuously missing from the Wikipedia article :-( $\endgroup$ Commented Oct 7, 2016 at 22:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.