UNIVERSITY EXAMINATIONS: 2011/2012
YEAR III EXAMINATION FOR THE BACHELOR OF SCIENCE IN
INFORMATION TECHNOLOGY
BIT3104 COMPILER CONSTRUCTION
DATE: APRIL 2012 TIME: 2 HOURS
INSTRUCTIONS: Answer Question One and Any other Two Questions
Question One
a) Give two points explaining how the knowledge of compiler construction impacts the following
i). Data structures
ii). Theory of computation
iii).Computer architecture
(6 Marks)
b) Give FOUR features of a good compiler (2 Marks)
c) The structure of a compiler is characterized by two major parts; Front End and Back End.
Describe the functions of each of them (2 Marks)
d) Why do you think OPTIMIZATION as regards compiler construction is Key to a good compiler?
Give TWO points to explain your answer. (4 Marks)
Given the following Grammar
G = (N, T, R, S) where
N = {S}
T ={ (, ) }
i). Derive the sentence of nested parenthesis
ii). Define what a sentential form is
iii).Describe what you understand by the term leftmost derivation
(6 Marks)
e) i) Given S → if E then S else S | if E then S, draw the parse trees associated with parsing the
sentence if E then if E then S else S henceforth define the term ambiguity (4 Marks)
ii) Illustrate how you can eliminate ambiguity in the above sentence (3 Marks)
f) i) Define Left Recursion
ii) Given the following sentence
, rewrite it eliminating direct recursion (3 Marks)
Question Two
a) Given the following grammar (6 Marks)
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)
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 Three
a) Differentiate between name equivalence and structural equivalence (4 Marks)
b) State the information found in the symbol table (5 Marks)
c) What is the function of the hash table? Give an example to illustrate your answer. (4 Marks)
d) Briefly discuss three storage allocation techniques (6 Marks)
e) Define the term scope
3
Question Four
a) Scanning and Parsing are usually separated in the context of compiler construction. Give two
reasons why scanning is not part of parsing? (4 Mark)
b) i) Define the grammar of letters and that of digits using normal English language (4 Marks)
ii) Give the definition of an Identifier (2 Marks)
c) Given the following grammar, transform it to regular grammar (4 Marks)
E = T { “+” T }.
T = F { “*” F }.
F = id.
d) Explain why the following grammar is not regular (4 Marks)
E = F { “*” F }.
F = id | “(” E “)”.
e) Explain one limitation of regular grammar (2 Marks)
Question Five
a) Define the phrase syntax-directed translation. (2 Marks)
b) Redundancy elimination is done by determining that two computations are equivalent and
eliminating one. Describe FOUR types of Redundancy Elimination (8 Marks)
c) The Goal for fast execution of a program is to store as much data as possible in registers. This
however has limitations. Describe Two limitations/considerations (4 Marks)
d) Describe SIX typical information that is stored in Stack frames (6 Marks)
