Hand in this prac before lunch time on your next practical day, correctly packaged in a transparent folder with your solutions and the "cover sheet". Please do NOT come to a practical and spend the first hour printing or completing solutions from the previous week's exercises. Since the practical will have been done on a group basis, please hand in one copy of the cover sheet for each member of the group. These will be returned to you in due course, signed by the marker.
In this 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 sheet:
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 15 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
The first few tasks do not need you to use a computer, nor should you. Do them by hand.
As an example of applying an analysis to a grammar expressed in EBNF, let us consider how we might describe the theatrical production of a Shakespearian play with five acts. In each act there may be several scenes, and in each scene appear one or more actors who gesticulate and make speeches to one another (for the benefit of the audience, of course). Actors come onto the stage at the start of each scene and come and go as the scene proceeds - to all intents and purposes between speeches - finally leaving at the end of the scene (in the Tragedies some may leave dead, but even these usually revive themselves in time to go home). Plays are usually staged with an interval between the third and fourth acts.
Actions like "speech", "entry" and "exit" are really in the category of the lexical terminals which a scanner (in the person of a member of the audience) would recognize as key symbols while watching a play. So one description of such a staged play might be on the lines of
Play = Act Act Act "interval" Act Act .
Act = Scene { Scene } .
Scene = { "speech" } "entry" { Action } .
Action = "speech" | "entry" | "exit" | "death" | "gesticulation" .
This does not require all the actors to leave at the end of any scene (sometimes this does not happen in real life either). We could try to get this effect by writing
Scene = { "speech" } "entry" { Action } { "exit" } .
but note that this context-free grammar cannot force as many actors to leave as entered - in computer language terms the reader should recognize this as the same problem as being unable to specify that the number of formal and actual parameters to a procedure agree.
Analyze this grammar in detail. If it proves out to be non-LL(1), try to find an equivalent that is LL(1), or argue why this should be impossible.
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.
Hand in your solutions to tasks 1 through 3 before continuing.
There are several files that you need, zipped up this week in the file PRAC22.ZIP (Java version) or PRAC22C.ZIP (C# version)
Copy the prac kit into a newly created directory/folder in your file space in the usual way:
j:
md prac22
cd prac22
copy i:\csc301\trans\prac22.zip
unzip prac22.zip
You will find the executable version of Coco/R and batch files for running it, frame files, and various sample programs and grammars, including ones for the grammars given in tasks 1, 2 and 3.
After unpacking this kit attempt to make the parsers as you did last week. Ask the demonstrators to show you how to get Coco/R to show you 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.
Develop a Cocol grammar BOOL.ATG for describing a list of Boolean expressions like those you should remember from your Boolean Algebra course in CSC 201. In this context, allow your Boolean expressions to be terminated with an = operator, and to include parentheses, single-letter variables, the constants FALSE and TRUE (sometimes written as 0 and 1), and the operators AND (written either as AND or "&" or as a "dot", or simply omitted), OR (written either as OR or as "|" or as a "plus") and NOT, written either as a prefix NOT or as a suffix apostrophe. So some examples of Boolean expressions might be (these are in the file BOOL.TXT)
a AND B OR (C OR NOT D) = a . b + (c + d') = a b + (c + d') =
NOT (a OR b) AND TRUE = (a + b)' . 1 = (a + b)' AND 1 =
b AND NOT C AND D = b . c' . d = b c' d =
Note that there is a precedence ordering among Boolean operators - parentheses take precedence over NOT, which takes precedence over AND, which takes precedence over OR.
Test your parser out on some examples like those just shown.
And here is something to think about. Draw out the parse tree that would correspond to the expression NOT (A OR B). Then draw out the parse tree that would correspond to NOT A AND NOT B. De Morgan will tell you that these expressions mean the same thing. Do you get the same tree in each case? Discuss the implications.
Develop a Cocol grammar that describes programs written in the PVM code that you struggled with in Practical 20. That should be pretty easy, but be careful to describe the language as tightly as possible. Then, just to make the language more attractive, suppose you had been able to use optional alphanumeric labels in your code as the destinations of branching instructions - as exemplified here:
DSP 2
LOOP LDA 1
INPI
LDL 1
BZE EXIT
BRN LOOP
EXIT LDL 1
PRNI
BRN 2
HALT
Of course our parser-only system won't actually be able to assemble the code. In a few weeks time we might extend it further to do that - for the moment simply describe the language.
Wait! we are not finished yet. You might have noticed that the assembler you used last week also generated a .COD file which, for the example above, would have looked like this
ASSEM
BEGIN
{ 0 } DSP 2
{ 2 } LDA 1
{ 4 } INPI
{ 5 } LDL 1
{ 7 } BZE 11
{ 9 } BRN 2
{ 11 } LDL 1
{ 13 } PRNI
{ 14 } BRN 2
{ 16 } HALT
END.
What you might not have noticed was that this .COD file could also be assembled by the assembler - the addresses in { braces } were treated as comments. Now that you have been told this, ensure that the language you describe can handle this feature as well.
The grammar for expressions in Parva employs very few levels of operator precedence, corresponding exactly to the levels found in Pascal and its derivatives. Modify the Parva grammar from last week's practical so that it recognizes expressions whose precedence rules are equivalent to those found in C# or Java.
Being a kindly old soul, this week's prac kit contains a correct version of Parva.atg that you can use if you did not get your own solution completed.
Something else to think about. Why do you suppose languages derived from C have so many levels of precedence and the rules they have for associativity? What do all these levels offer to a programmer that languages modelled on Pascal might appear to withhold? Do Pascal-like languages really withhold these features?
Hand in sheet:
Task 1 - Shakespearian plays Which, if any, alternatives break the LL(1) rules and why? Can you find an equivalent grammar that does obey the LL(1) constraints? If so, give it. If not, explain why you think it canot be done. Task 2 - 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 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.