Please answer all questions in the spaces provided (three sides). Text books may not be used. Max 35.
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]
63T0884 Terry Be careful to answer the questions accurately ...
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]
A sentential form is the goal or start symbol, or any string that can be derived from it:
Sentential form = σ | S ⇒* σ ∧ σ √ (N ∪ T )*
A sentence is a string derivable from S that contains only terminals.
Sentence = w | S ⇒* w ∧ w √ T *
(b) What do you understand by the terms Terminal and Non-Terminal? [3]
Terminals are the atomic (indivisible) elements of a language that appear in sentences. Non- terminals are useful descriptors of syntactic elements that are useful in describing the "phrase structure" of sentences - ideas like "function call" or "variable declaration" if one is talking about computer languages, or "qualified noun" or "dependent clauses" if one is talking about English sentences. Non-terminals and terminals may typically appear in the interior nodes of parse trees, but leaf nodes of such trees will contain terminals.
In terms of L(G) we simply have that a is a terminal if a √ T and A is a non-terminal if A √ N.
3. (a) What is meant by the statement "a grammar is ambiguous"? [2]
There is a very simple way to express this - a grammar is ambiguous if at least one sentence in the language that it defines can be parsed in at least two ways (that is can have more than one parse tree rooted in the goal symbol and with identical leaf nodes). Note that we are talking about a single grammar - we are not talking about two equivalent but distinct grammars that might each be able to describe the same sentences.
(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" .
To answer this sort of question you must be able to draw two parse trees (or specify two distinct expansions from the goal symbol in some other way) that lead to the same sentence. There are many examples one can use here, and most people could come up with one. The real menace is not the ε as such (though that does not help) - it is that the option
Adjectives = Adjectives Adjectives
can lead to another string like
Adjectives = Adjectives Adjectives Adjectives
in two ways - either by applying the option again to the leftmost Adjectives or to the rightmost Adjectives. So here is an example where we can draw two distinct trees (without cluttering it up with ε, although examples with an ε are acceptable too:
Phrase Phrase
┌───────────────────┐ ┌─────────────────────────┐
│ │ │ │
Adjectives Noun Adjectives Noun
┌──────────────────┐ │ ┌────────────────┐ │
│ │ │ │ │ │
Adjectives Adjectives │ Adjectives Adjectives │
┌───────────┐ │ │ │ ┌───────────┐ │
│ │ │ │ │ │ │ │
Adjectives Adjectives │ │ │ Adjectives Adjectives │
│ │ │ │ │ │ │ │
"poor" "silly" "twisted" "boy" "poor" "silly" "twisted" "boy"
(c) Give an equivalent grammar that describes the same phrases but is not ambiguous. [4]
This is really very easy! One solution is:
Phrase = { Adjectives } Noun.
Adjectives = "silly" | "twisted" | "lucky" | "clever" | "poor" .
Noun = "boy" | "girl" .
But be careful not to write, as you might be tempted to do
Phrase = { Adjectives } Noun.
Adjectives = "silly" | "twisted" | "lucky" | "clever" | "poor" | ε.
Noun = "boy" | "girl" .
which is actually ambiguous once more. Curly braces around { Adjectives } already imply an ε option, and you don't need/want to have two ambiguous ways of doing this!
Another grammar might be a recursive one on the lines of one suggested in the book somewhere:
Phrase = Adjective Phrase | Noun.
Adjective = "silly" | "twisted" | "lucky" | "clever" | "poor" .
Noun = "boy" | "girl" .
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]
The hint was given that this is a high precedence operator. It's higher than * and /, but lower than (), and the correct solution is to introduce another level into the hierarchy. To get the correct "right associativity" requires an option in a right recursive production
Expression = Term { "+" Term | "-" Term } .
Term = Factor { "*" Factor | "/" Factor } .
Factor = Primary [ "^" Factor ] .
Primary = "a" | "b" | "c" | "(" Expression ")" .
Now as an interesting exercise you might like to ponder why you cannot write, instead
Expression = Term { "+" Term | "-" Term } .
Term = Factor { "*" Factor | "/" Factor } .
Factor = Primary [ "^" Expression ] .
Primary = "a" | "b" | "c" | "(" Expression ")" .
and you might also like to ponder whether the following alternative is acceptable:
Expression = Term { "+" Term | "-" Term } .
Term = Factor { "*" Factor | "/" Factor } .
Factor = { Primary "^" } Primary .
Primary = "a" | "b" | "c" | "(" Expression ")" .
5. (a) What is meant by the statement "a non-terminal is nullable"? [2]
Students tend to submit solutions like: "A is nullable if it has a production rule like A = a | ε ", or a similar restricted example. But it's better to say, more simply
A is nullable if A ⇒* ε
as the production rules for A may not have any explicit ε in them, but possibly specify a list of alternative sentential forms from which it is eventually possible to derive an empty string - this might involve chasing through several steps before it becomes apparent!
In English - a non-terminal A is nullable if it is possible to apply productions to the sentential forms derived from A in such a way that a null sentence can be derived.
(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" .
Most people quickly see that B is obviously nullable. Since C can derive an empty string from B followed by an empty string from { "a" }, C is also nullable. Less obvious, perhaps, is that A is also nullable. as the rule A = C { D } can lead to an empty string as well.
6. 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]
Of course this is merely a simple variation on the CALC.ATG grammar you had seen several times.
COMPILER Bool $CN
/* Boolean expression parser - give your name and what it does!
P.D. Terry, Rhodes University, 2015 */
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
TOKENS
variable = letter .
COMMENTS FROM "(*" TO "*)" NESTED
COMMENTS FROM "/*" TO "*/" NESTED
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Bool = { Expression "=" } EOF .
Expression = Term { Or Term } .
Term = Factor { [ And ] Factor } .
Factor = "NOT" Factor | Primary { "'" } .
Primary = True | False | variable | "(" Expression ")" .
True = "TRUE" | "1" .
False = "FALSE" | "0" .
And = "AND" | "&&" | "." .
Or = "OR" | "||" | "+" .
END Bool.