UNIVERSITY EXAMINATIONS: 2011/2012
THIRD YEAR EXAMINATION FOR THE BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 3104 COMPILER CONSTRUCTION
DATE: AUGUST, 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
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:
i. S → x
ii. S → y
iii. S → z
iv. S → S + S
v. S → S – S
vi. S → S * S
vii. S → S / S
viii. 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) What are terminal or non-terminal symbols of a grammar. (2 Marks)
e) Consider a grammar defined by the following two rules. Specify the terminal and
non- terminals.
i). x can become xa
ii).x can become ax (2 Marks)
f) 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:
i. A sentence can be a noun phrase followed by a verb phrase (S → NP VP)
ii. A noun phrase can be a noun by itself (NP → N)
iii. A noun phrase can also be a determiner followed by a noun (NP → Det N)
iv. A verb phrase can be a verb followed by a noun phrase (VP → V NP)
v. 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
(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:
1. S → F
2. S → ( S + F )
3. F → a
and the following input:
( a + a )
Given that the parsing table for this grammar looks as follows:
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 top-down 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) Differentiate between type inference and type checking (4 Marks)
c) Differentiate between name equivalence and structural equivalence (4 Marks)
