Please answer all questions in the spaces provided (three sides). Text books may not be used. Max 35.
The Hublic Polydaze wreak havoc with this course. Here is the sort of test that would have been set today. See whether you can solve these problems. I shall post solutions early next week. You do not have to hand it in (unless you want to do so), and there will be no entry on your course record.
This test is intended to check your understanding of important concepts in formal language theory and the construction of grammars, with some questions relating back to earlier sections. It should probably take you about half an hour.
1. Who says it's hard to spot for my tests? What are your student number and surname? [1]
2. A language L restricted by a grammar G is defined by L(G) = {N, T, S, P}.
(a) What do you understand by the terms Sentential Form and Sentence? [3]
(b) What do you understand by the terms Terminal and Non-Terminal? [3]
3. (a) What is meant by the statement "a grammar is ambiguous"? [2]
(b) Demonstrate that the following grammar that describes phrases like "lucky girl" or "poor silly twisted boy" is ambiguous. [4]
Phrase = Adjectives Noun.
Adjectives = Adjectives Adjectives
| "silly" | "twisted" | "lucky" | "clever" | "poor" | ε .
Noun = "boy" | "girl" .
(c) Give an equivalent grammar that describes the same phrases but is not ambiguous. [4]
4. A grammar for expressions like the one you extended in the practical should be familiar
Expression = Term { "+" Term | "-" Term } .
Term = Factor { "*" Factor | "/" Factor } .
Factor = "a" | "b" | "c" | "(" Expression ")" .
Suppose we also wanted our grammar to be able to describe expressions in which entities could be raised to a power - an operation denoted by "^", and exemplified by a ^ b or (a + b) ^ c or a ^ b ^ c * d .
The exponentiation operator (as "^" is called) is a high precedence operator and associates from right to left so that a ^ b ^ c means a ^ (b ^ c) and not (a ^ b) ^ c. Suggest how this operator would be incorporated in an extension of the grammar above. [5]
5. (a) What is meant by the statement "a non-terminal is nullable"? [2]
(b) In the grammar defined by the following productions, identify (giving reasons) the nullable non- terminals. [3]
A = B "a" | C { D } .
B = [ A "b" ] .
C = B { "a" } .
D = "a" B "c" .
5. Develop a Cocol grammar for describing a list of Boolean expressions, like those you should remember from Boolean Algebra courses you may have taken. 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
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. [8]
COMPILER Bool $CN
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
TOKENS
variable = letter .
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Bool = { Expression "=" } EOF .
Expression =
END Bool.