UNIVERSITY EXAMINATIONS: 2010/2011
THIRD YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 3104: COMPILER CONSTRUCTION
DATE: AUGUST 2011 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
Question One
a) Define a CFG and describe its importance in Computer Science (3 Marks)
b) Here is a context-free grammar for syntactically correct infix algebraic expressions in the variables
x, y and z:
a) S → x
b) S → y
c) S → z
d) S → S + S
e) S → S – S
f) S → S * S
g) S → S / S
h) S → ( S )
Show how the above grammar can generate the following expression.
( x + y ) * x – z * y / ( x + x ) (6 Marks)
c) Define recursively the collection of regular languages over an alphabet Σ (8 Marks)
d) i) What are terminal or non-terminal symbols of a grammar (2 Marks)
ii) Consider a grammar defined by the following two rules. Specify the terminal and non-
terminals.
a) x can become xa
b) x can become ax (2 Marks)
e) The English sentence “John hit the ball” may be analyzed by bottom-up parsing. In this case, the
most fundamental units (ignoring conjugation and declension) are the words: “John”, “hit”, “the”
and “ball”.
A simplified grammar for English, sufficient for this sentence, is:
1. A sentence can be a noun phrase followed by a verb phrase (S → NP VP)
2. A noun phrase can be a noun by itself (NP → N)
3. A noun phrase can also be a determiner followed by a noun (NP → Det N)
4. A verb phrase can be a verb followed by a noun phrase (VP → V NP)
5. Nouns, determiners and verbs are all words (N → word, Det → word, V → word)
Using the above productions, construct the parse tree for the sentence above
Proceed as follows, first complete the table below followed by the construction of the tree
Rules used Words Parsed Sentence Now
5 John and ball are Nouns, The is a determiner and hit is
a verb
N V Det N
(9 Marks)
Question Two
a) Give and describe Four categories of LR parsers under Bottom-up parsers (4 Marks)
b) The most common bottom-up parsers are the shift-reduce parsers. Give Four actions of these
parsers (4 Marks)
c) Write the algorithm of a Shift-reduce parser (3 Marks)
d) Take the grammar:
Sentence –> NounPhrase VerbPhrase
NounPhrase –> Art Noun
VerbPhrase –> Verb | Adverb Verb
Art –> the | a | …
Verb –> jumps | sings | …
Noun –> dog | cat | …
And the input:
the dog jumps
Parse the above input using Shift-reduce parser (4 Marks)
e) Given the grammar:
<Expression> –> <Term> | <Term> + <Expression>
<Term> –> <Factor> | <Factor> * <Term>
<Factor> –> [ <Expression> ] | 0…9
and input (2 * [ 1 + 3 ]), work out shift-reduce parsing. (5 Marks)
Question Three
a) Define a top-down parser. Why are top-down parsers called LL parsers? (4 Marks)
b) i) Consider the following small grammar:
a) S → F
b) S → ( S + F )
c) F → a
and the following input:
( a + a )
Given that the parsing table for this grammar looks as follows:
( ) a + $
S 2 – 1 – –
F – – 3 – –
i) Show the workout for parsing the above input (6 Marks)
ii) Generate the production rules as the output stream (2 Marks)
c) Define Lexical analysis (2 Marks)
d) In the context of compiler construction and in particular, syntax analysis define the following terms
i). Recognition
ii). Parsing
iii).Unambiguous grammar: (6 Marks)
Question Four
a) Describe any two top-down parsers (8 Marks)
b) Write procedures to represent the following grammar
S => Ba | c
S => Ds | e (4 Marks)
c) Given the following grammar, convert it to a CFG in preparation to parsing a string using topdown parser
E=>E+E
E=>E*E
E=>(E)
E=>ID
(8 Marks)
Question Five
a) Given the following grammar and subsequent input, workout its parsing using Bottom Up Parser
(12 Marks)
1. S = E
2. E = E + E
3. E = E * E
4. E = num
5. E = id
Input to parse:
id1 + num * id2
b) With reference to type sytem, differentiate
i) Type inference and type checking (4 Marks)
ii) name equivalence and structural equivalence (4 Marks)
