Please answer all questions in the spaces provided (four sides). Text books may not be used. Max 30
This test is intended to check your ability to wite simple Coco/R specifications and your understanding of LL(1) rules. It should only take you about 35 minutes at the most. Textbooks may not be used.
1. (a) Oh dear. I need reminding yet again. Please give your firstname / surname / student number? [1]
(b) Is your answer to (a) an acceptable example of a Regular Expression? If not, why not? [1]
2. 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 } . // additive
Term = Factor { ( "*" | "/" ) Factor } . // multiplicative
Factor = Primary [ "^" Expression ] . // exponentiation
Primary = "a" | "b" | "c" .
END Expression.
(a) Convince me that this is an ambiguous grammar [3].
(b) Is it an LL(1) grammar? Why? [1]
(c) Can you find a suitable grammar that is unambiguous? (Give the new productions) [3]
3. You are referred to the Parva grammar on a separate page.
Suppose that next year you are chosen to act as a tutor for this course and that a student comes to you proudly showing a revised grammar which contains a new statement type, among other changes:
PRODUCTIONS
Parva = "void" "main" "(" ")" Block .
Block = "{" { Declaration | Statement } "}" .
Declaration = ConstDeclaration | VarDeclarations .
Statement = Block | Assignment | ";"
| IfStatement | WhileStatement | DoWhileStatement
| ReturnStatement | HaltStatement
| ReadStatement | WriteStatement .
DoWhileStatement = "do" { Statement } "while" "(" Condition ")" ";" .
What advice would you give this student as to whether this was correct, better/worse than the original, or had unexpected features that they might not have thought of? [5]
4. Suppose you are asked to extend the description of Parva to allow a programmer to incorporate "inline" PVM assembler statements, as exemplified by
pvm {
PRNS "Assigning -9 to variable 2"
LDA 2
LDC -9
STO
}
Here is a new statement definition that attempts to allow this (you would obviously also need a trivial change to the production for Statement to be able to make this into a "useful production").
InlineStatement
= "pvm" "{"
{ identifier [ "+" | "-" ] [ number | stringLit ] }
"}" .
Does this production really describe the new statement type properly? If not, suggest how it should be improved by giving a better production or productions. [6]
5. As is very common, the production above makes use of the EBNF "meta brackets" { } and [ ]. How would you rewrite your (improved) production or productions describing the InlineStatement without making use either of these forms of meta brackets? [4]
6. A daring extension to Parva would be to allow the use of the float type, in addition to int and bool. This would require you to be able to describe literal constants like 12.34 or 1.2E4 or 12E-5. Where and how would you have to change the Cocol specification of Parva to be able to recognise literals, statements, declarations and expressions that incorporate these extensions? [6]
COMPILER Parva $CN
CHARACTERS
lf = CHR(10) .
backslash = CHR(92) .
control = CHR(0) .. CHR(31) .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
stringCh = ANY - '"' - control - backslash .
charCh = ANY - "'" - control - backslash .
printable = ANY - control .
TOKENS
identifier = letter { letter | digit | "_" } .
number = digit { digit } .
stringLit = '"' { stringCh | backslash printable } '"' .
charLit = "'" ( charCh | backslash printable ) "'" .
COMMENTS FROM "//" TO lf
COMMENTS FROM "/*" TO "*/"
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
Parva = "void" identifier "(" ")" Block .
Block = "{" { Statement } "}" .
Statement = Block | ConstDeclarations | VarDeclarations | Assignment | ";"
| IfStatement | WhileStatement | ReturnStatement | HaltStatement
| ReadStatement | WriteStatement .
ConstDeclarations = "const" OneConst { "," OneConst } ";" .
OneConst = identifier "=" Constant .
Constant = number | charLit | "true" | "false" | "null" .
VarDeclarations = Type OneVar { "," OneVar } ";" .
Type = BasicType [ "[]" ] .
BasicType = "int" | "bool" .
OneVar = identifier [ "=" Expression ] .
Assignment = Designator "=" Expression ";" .
Designator = identifier [ "[" Expression "]" ] .
IfStatement = "if" "(" Condition ")" Statement .
WhileStatement = "while" "(" Condition ")" Statement .
ReturnStatement = "return" ";" .
HaltStatement = "halt" ";" .
ReadStatement = "read" "(" ReadElement { "," ReadElement } ")" ";" .
ReadElement = stringLit | Designator .
WriteStatement = "write" "(" WriteElement { "," WriteElement } ")" ";" .
WriteElement = stringLit | Expression .
Condition = Expression .
Expression = AddExp [ RelOp AddExp ] .
AddExp = [ "+" | "-" ] Term { AddOp Term } .
Term = Factor { MulOp Factor } .
Factor = Designator | Constant
| "new" BasicType "[" Expression "]"
| "!" Factor | "(" Expression ")" .
AddOp = "+" | "-" | "||" .
MulOp = "*" | "/" | "&&" .
RelOp = "==" | "!=" | "<" | "<=" | ">" | ">=" .
END Parva.
Home © P.D. Terry