This should take no longer than about 40 minutes and is simply intended to probe whether you have understood LL(1) grammars and the like. YOU MAY NOT USE YOUR TEXTBOOK, NOTES or COMPUTER. Answer on the questions sheet (4 sides).
1. Sorry, I am getting past it and have forgotten again. What are your name (surname) and student number? [1]
2. Suppose you are asked to extend the description of Parva to allow a programmer to incorporate "inline" PVM assembler statements among other high-level statemente, as exemplified by
if (x > y)
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. You don't have to remember all the PVM opcodes, just use a few of them if you need to make a particular point. [6]
3. Consider the following (silly) grammar
Goal = { A } [ C ] { A C } Goal .
A = x | y .
B = p | q .
C = [ a | b ] .
(a) Write an equivalent grammar that does not use any of the meta-brackets (you may introduce further non-terminals if you wish, but your grammar should retain the non-terminals already present). [3]
(b) For your equivalent grammar, indicate which are nullable non-terminals? [2]
(c) There is an easy way to see that the original grammar is ambiguous. Why is it ambiguous, and how could a simple change remove this ambiguity? [2]
4. Grammars don't get much simpler than this next one - at least to write down. It has one nonterminal A and two terminals, the parentheses ( and ) .
A = "(" A ")" A | ε .
(a) Is it an LL(1) grammar? If not, why not? [4]
(b) What language do you suppose it describes (write down a few strings derived from A and see the hopefully obvious pattern!) [3]
(c) Is it an ambiguous grammar? Explain your reasoning. [2]
5. Repeat question 4 for a grammar that looks rather similar but does not have an ε:
A = "(" A ")" | "(" ")" | A A .
(a) Is it an LL(1) grammar? If not, why not? [2]
(b) What language do you suppose it describes (write down a few strings derived from A and see the hopefully obvious pattern!) [3]
(c) Is it an ambiguous grammar? Explain your reasoning. [2]
6. Time to be more creative.
Steven Spielberg is about to film his latest blockbuster "Elevator 9/11", in which a group of gorgeous Americans (guess what) are trapped in an elevator hundreds of feet above the ground by a group of ugly ... (you guessed right again). He wants to make sure he understands how to arrange for the elevator to get stuck. (So would you if you had the chance to spend a few hours opposite/underneath/on top of some of the hunks and bimbos he has lined up to act for him).
Mr Spielberg has been reliably informed that some high-rise skyscrapers have lifts (elevators) that are based partway up the building, say on level (floor) X. People entering one of these elevators have a choice of pushing an UP key or a DOWN key as many times as they like. If the lift is behaving normally it can go up or down one level for each push of the appropriate key, but it cannot drop below level X, and at the end of the day it is supposed to have returned to level X again. Write down the productions for a simple grammar that will allow Mr S to recognize a sequence of commands that does not trap the lift, such as
UP UP DOWN DOWN or UP UP DOWN UP DOWN UP DOWN DOWN
Sequences that effectively jam the lift, such as
DOWN UP or UP UP DOWN
should be rejected by the grammar. (Hint: Treat UP and DOWN as key words <grin> and THINK before you answer!) [4]
7. Who said that practicals were all plain sailing? Here is an attempt to describe the progress of one of my practicals. This one has only two tasks, which can be attempted in either order after the group has studied the handout and installed the prac kit. Under the guidance of your well-known tutors, each group works away attempting to solve one problem at a time and, at each attempt, may seek help from the pool of tutors. Based on the reputation and skill of the tutors it has been suggested that the scenario can be described as follows, regarding the quoted words as terminals for this purpose.
Practical = "PracTest" GetOrganised Tasks .
GetOrganised = "Handout" "PracKit" .
Tasks = ( Task1 | Task2 ) "Supper" ( Task2 | Task1 ) .
Task1 = { "Try1" { Help } } "Submit1" .
Task2 = { "Try2" { Help } } "Submit2" .
Help = "Marq [ "Damon"] | "Damon" [ " Marq" "Kefentse" ] | "Kefentse" | "Pat" .
(a) Some groups prefer to install the prac kit before reading the handout, but this grammar does not allow that. What would you have to change to permit this freedom (and that means "make the change, not waffle!")? And, of course, some of those students don't bother with getting the handout in any case, I have noticed. Modify the grammar to accept their behaviour as well. [4]
(b) The grammar has been written to try to specify that the two tasks can be done in either order. Does it succeed, or does it need further modification? [3]
(c) While there is clearly a lot of Help to be had, the production for acquiring it seems fairly complicated. Is this an LL(1) grammar? Can you justify your answer? Is it perhaps an ambiguous grammar? Can you justify your answer? Can you simplify the process? [6]
(d) Is it possible to do practicals as described here without any help and/or without even trying? How? Why do some of you ask for so little help? [3]