UNIVERSITY EXAMINATIONS: 2012/2013
THIRD YEAR EXAMINATION FOR THE BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
COMPILER CONSTRUCTION
DATE: DECEMBER, 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE
a) When programming occasionally the computer generate bugs. Describe three types of
errors that may arise during programming. (6 Marks)
b) Of the errors that you have listed in (a) above, which ones does the compiler handle
and which ones doesn’t handle. (3 Marks)
c) Define what a token is and describe 3 categories of tokens. (4 Marks)
d) Describe the work of the lexical analysis. (2 Marks)
e) Define what are regular expressions and THREE possible operations carried on them
(4 Marks)
f) Describe the component of a Grammar and Outline Chomsky Hierarchy of Grammars
(6 Marks)
g) Outline the requirement for a grammar to satisfy a CFG (3 Marks)
h) Draw an AST for the following expression (100-200)*300 (2 Marks)
QUESTION TWO
a) With reference to Bottom-up Passing, explain four Parsing actions
(4 Marks)
b) Differentiate between LR(0) and LR(1) parsers. (2 Marks)
c) Differentiate between terminal and non terminal symbols. (4 Marks)
d) Given the following grammar, write the methods for parsing a genereal input.
A = B a.
B = { b } c | [ d ] | e.
C = D e | f.
D = { d }.
(10 Marks)
QUESTION THREE
a) Given the following grammar
S = A B | S A B.
A = a | a a b.
B = b | b b a.
Use it to pass the following input string
a b b a a b # (# represent the end of file)
(6 Marks)
b) In the context of compiler construction and in particular, syntax analysis define the
following terms
i). Recognition
ii). Parsing
iii). Unambiguous grammar (6 Marks)
c) Differentiate between bottom-up and top-down parsing. (4 Marks)
d) Describe the recursive descent parser and the main Idea behind it. (4 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)
