UNIVERSITY EXAMINATIONS: 2012/2013
EXAMINATION FOR THE BACHELOR OF SCIENCE IN
INFORMATION TECHNOLOGY
BIT 3104 COMPILER CONSTRUCTION
DATE: AUGUST, 2013 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and Any Other TWO Questions
QUESTION ONE
a) i) When programming occasionally the computer generate bugs.
Describe three types of errors that may arise during programming. [6 marks]
ii) Of the errors that you have listed above, which ones does the compiler handle
and which ones doesn’t handle. [3 marks]
b) Define what a token is and describe 3 categories of tokens. [4 marks]
c) Describe the work of the lexical analysis. [2 marks]
d) Define what are regular expressions and THREE possible operations carried on them
[4 marks]
e) Describe the component of a Grammar and Outline Chomsky Hierarchy of Grammars
[6 marks]
f) Outline the requirement for a grammar to satisfy a CFG. [3marks]
g) 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
top-down 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]
