Computer Science 301 - 2017 - Practical 4

Hand in sheet -  Group members surnames, please


Task 1 - Self-describing ENBF

  Does the grammar as supplied obey the LL(1) constraints?  Why/Why not?

  How do you define a terminal to allow internal lowlines (underscores) but not allow one or more at the end?

  Comment on whether the suggested changes to the productions for QualifiedNoun introduce non-LL(1)
  conformance or ambiguity.

Task 2 - Ambiguity

  Is the grammar for Roman number sqquences an LL(1) grammar?  Justify your answer.

  Is the suggested grammar ambiguous?   Justify your answer.

  If the grammar is unsuitable according to the answers to the first questions, find a better grammar that does
  not suffer from the problems you have identified?

Task 3 - Palindromes

   Does grammar 1 describe palindromes?       If not, why not?

   Is it an LL(1) grammar?          If not, why not?

   Does grammar 2 describe palindromes?       If not, why not?

   Is it an LL(1) grammar?          If not, why not?

   Does grammar 3 describe palindromes?       If not, why not?

   Is it an LL(1) grammar?          If not, why not?

   Does grammar 4 describe palindromes?       If not, why not?

   Is it an LL(1) grammar?          If not, why not?

   Can you find a better grammar to describe palindromes?  If so, give it, if not, explain why not.

Task 4

   Which of the following statements are true?  Justify your answers.

     (a) An LL(1) grammar cannot be ambiguous.

     (b) A non-LL(1) grammar must be ambiguous.

     (c) An ambiguous language cannot be described by an LL(1) grammar.

     (d) It is possible to find an LL(1) grammar to describe any non-ambiguous language.