Hand in the attached answer sheet by the end of the afternoon, or no later than 09h00 tomorrow, packaged in a transparent folder with your "cover sheets" and "assessment sheets". Preferably COPY I:\Csc301\trans\prac22.txt and edit it - far easier for me to read later!
In this short practical you are to
You will need this prac sheet and your text book. As usual, copies of the prac sheet are also available at http://www.cs.ru.ac.za/CSc301/Translators/trans.htm.
When you have completed this practical you should understand
This week you are required to hand in, besides the cover and assessment sheets:
I do NOT require listings of any Java code produced by Coco/R.
Keep the prac sheet and your solutions until the end of the semester. Check carefully that your mark has been entered into the Departmental Records.
You are referred to the rules for practical submission which are clearly stated on page 18 of our Departmental Handbook. However, for this course pracs must be posted in the "hand-in" box outside the laboratory and not given to demonstrators.
A rule not stated there, but which should be obvious, is that you are not allowed to hand in another student's work as your own. Attempts to do this will result in (at best) a mark of zero and (at worst) severe disciplinary action and the loss of your DP. You are allowed - even encouraged - to work and study with other students, but if you do this you are asked to acknowledge that you have done so. You are expected to be familiar with the University Policy on Plagiarism, which you can consult at:
http://www.scifac.ru.ac.za/plag.htm
Consider the following grammar expressed in EBNF for describing the progress of a typical university course:
COMPILER Course
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Course = Introduction Section { Section } Conclusion .
Introduction = "lecture" [ "handout" ] .
Section = { "lecture" | "practical" "test" | "tutorial" | "handout" } "test" .
Conclusion = [ "panic" ] "examination" .
END Course.
Is this an LL(1) grammar? If not, where does it break the rules? Can you find an equivalent LL(1) grammar? Hint: First rewrite the grammar without any parentheses. Introduce more non-terminals to do so.
Consider the following grammar:
COMPILER Home
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Home = Family { Pets } [ Vehicle ] "house" .
Pets = "dog" [ "cat" ] | "cat" .
Vehicle = ( "scooter" | "bicycle" ) "fourbyfour" .
Family = Parents { Children } .
Parents = [ "Dad" ] [ "Mom" ] | "Mom" "Dad" .
Child = "Helen" | "Margaret" | "Alice" | "Robyn" | "Cathy"
| "Janet" | "Anne" | "Ntombizodwa" | "Ntombizanele" .
END Home.
Analyse this grammar in detail.
The following grammar attempts to describe expressions incorporating the familiar operators with their correct precedence and associativity.
COMPILER Expression
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Expression = Term { ( "+" | "-" ) Term } .
Term = Factor { ( "*" | "/" ) Factor } .
Factor = Primary [ "^" Expression ] .
Primary = "a" | "b" | "c" .
END Expression.
Is this an ambiguous grammar? (Hint: try to find an expression that can be parsed in more than one way). Is it an LL(1) grammar? If not, why not, and can you find a suitable grammar that is LL(1)?
Palindromes are character strings that read the same from either end. The following represent various ways of finding grammars that describe palindromes made only of the letters a and b:
(1) Palindrome = "a" Palindrome "a" | "b" Palindrome "b" .
(2) Palindrome = "a" Palindrome "a" | "b" Palindrome "b" | "a" | "b" .
(3) Palindrome = "a" [ Palindrome ] "a" | "b" [ Palindrome ] "b" .
(4) Palindrome = [ "a" Palindrome "a" | "b" Palindrome "b" | "a" | "b" ] .
Which grammars achieve their aim? If they do not, explain why not. Which of them are LL(1)? Can you find other (perhaps better) grammars that describe palindromes and which are LL(1)?
Which of the following statements are true? Justify your answer.
(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.
In the prac kit PRAC22.ZIP which you can find in the usual place you will find the source code of the grammars in tasks 1, 2, 3 and 4. Unpack this kit and attempt to make the parsers. Ask the demonstrators to show you how to get Coco/R to list the FIRST and FOLLOW sets for the non-terminals of the grammar, and verify that the objections (if any) that Coco/R raises to these grammars are the same as you have determined by hand.
Hand in sheet:
Task 1 Is this an LL(1) grammar? If not, why not? If not, what would you change to give an equivalent LL(1) grammar? Task 2 Is this an LL(1) grammar? If not, why not? If not, what would you change to give an equivalent LL(1) grammar? Task 3 Is this an LL(1) grammar? If not, why not? If not, give a suitable set of productions that does conform to LL(1) rules Is the original grammar ambiguous? If so, give an example of an expression that can be parsed in more than one way. Task 4 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 5 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.