This should take no longer than about 35 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. 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.
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)? [7]
3. Consider the following (silly) grammar
Goal = { A } [ B ] { 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. [3]
(b) For your equivalent grammar, indicate which are the nullable non-terminals. [2]
4. Consider the following grammar expressed in EBNF for describing the progress of an excellent compiler course offered at a University Near You:
Course = Introduction Section { Section } Conclusion .
Introduction = [ "lecture" "handout" ] .
Section = { "lecture" | "practical" "test" | "tutorial" | "handout" } "test" .
Conclusion = [ "panic" ] "examination" .
(a) Is this an LL(1) grammar? If not, where does it break the rules? [3]
(b) If it breaks the rules, do you suppose a recursive descent parser would have trouble recognizing the history of a course? Explain. [2]
(c) Do you think it is possible to complete the course described by this grammar without attending any lectures? (Explain your reasoning.) [2]
(d) (Bonus mark) But why are too many of you missing too many of my lectures? [1]
5. Grammars don't get much simpler than this next one - at least to write down. It has one nonterminal A and two terminals ( and )
A = "(" A ")" A | e .
(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]
6. Repeat question 5 for a grammar that looks rather similar but does not have an e:
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]
7. 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]