This should take no longer than 30 minutes and is simply intended to probe whether you have understood the material in the prac questions. YOU MAY NOT USE YOUR TEXTBOOK, NOTES OR A COMPUTER. Answer on the questions sheet (3 sides).
1. You were expecting this one, I bet! What are your name (surname) and student number? [1]
2. What do you understand by the term equivalent grammars? Give a short, precise definition! [2]
3. Part of the grammar for the extended Parva language you met in the practical might have been expressed as follows:
PRODUCTIONS
Parva = "void" "main" "(" ")" Block .
Block = "{" { Statement } "}" .
Statement = ( Block | WhileStatement | IfStatement | DoWhileStatement
| ReadStatement | WriteStatement | Assignment
| ReturnStatement | EmptyStatement
| ConstDeclaration | VarDeclarations
) .
IfStatement = "if" "(" Condition ")" Statement
{ "elsif" "(" Condition ")" Statement }
[ "else" Statement ] .
WhileStatement = "while" "(" Condition ")" Statement .
RepeatStatement = "do" Statement "while" "(" Condition ")" ";" .
What (if anything) would be the effect of replacing the productions as follows? Are the productions equivalent? If not, what are the differences in practice? [5]
Parva = "void" "main" "(" ")" Block .
Block = "{" { Declaration | Statement } "}" .
Declaration = ConstDeclaration | VarDeclarations .
Statement = ( WhileStatement | IfStatement | DoWhileStatement
| ReadStatement | WriteStatement | Assignment
| ReturnStatement | EmptyStatement
) .
IfStatement = "if" "(" Condition ")" Block
{ "elsif" "(" Condition ")" Block }
[ "else" Block ] .
WhileStatement = "while" "(" Condition ")" Block .
RepeatStatement = "do" Block "while" "(" Condition ")" ";" .
4. Show how one might specify a numeric literal in Cocol, allowing for the possibility of numbers of any of the following forms [4]
123 1.23 1. .23 1.2E12 1.2E-12 1E6 1E-6 .234E6 .234E-6
CHARACTERS
digit = "0123456789" .
TOKENS
number =
5. Modify the productions given as the first set in Question 3 so as to add a SwitchStatement to Parva on the lines of the ones found in C# or Java. A (silly) example of such a statement is as follows: [6]
switch (x + 10) {
case 10 :
write("reached case 10"); return;
case 20:
case 30:
if (x != 20) write("x must be 10");
else write("x = " , x); break;
default :
write("x cannot be 0, 10 or 20");
break;
} // switch
6. In the practical you were invited to develop a grammar that would describe a list of academic staff, with provision made for titles, initials, names and degrees. A set of productions for this might have been the following
PRODUCTIONS
Staff = { Person } EOF .
Person = [ Title ] FullName { "," Degree } "." .
FullName = NameLast { NameLast } .
NameLast = initial { initial } name | name .
Title = "Professor" | "Dr" | "Mr" | "Mrs" | "Ms" | "Miss" | "Mx" .
Degree = "BA" | "BSc" | "BCom" | "BMus" | "BEd" | "BSocSci"
| "BSc(Hons)" | "BCom(Hons)" | "MA" | "MSc" | "PhD" .
END Staff.
(a) Give a precise, mathematical, definition of the concept "nullable non-terminal". [2]
(b) Identify - giving reasons - the nullable non-terminals in the above set of productions (name and initial are, of course, terminals). [4]
(c) The PRODUCTIONS section above makes use of the EBNF "meta brackets" { } and [ ] in the production rules. How would you write alternative productions for Staff, Person, FullName and NameLast which made no use of parentheses ( ) or of either of the { } or [ ] form of meta brackets or of the Kleene Closure symbol * ? [6]