Complier Construction Question Paper
Complier Construction
Course:Bachelor Of Science In Information Technology
Institution: Kca University question papers
Exam Year:2009
UNIVERSITY EXAMINATIONS: 2008/2009
THIRD YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 3104: COMPLIER CONSTRUCTION
DATE: AUGUST 2009 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE
a) Define what a language processor is. [2 Marks]
b) Define the following terms and phrases as used in compiler construction
i). Assembler
ii). Compiler
iii). Interpreter
iv). Token
v). Cross compiler
[10 Marks]
c) Use a flowchart to explain the job of a scanner [4 Marks]
d) What sets of strings do the following RE generate:
i). (abc)
ii). M r | M s
iii). (foo|bar)*
iv). (foo|bar)(foo|bar)*
v). (0|1|2|3|4|5|6|7|8|9)*
vi). 0|(1|..|9)(0|1|..|9)* [6 Marks]
2
e) Briefly explain the two styles of implementing the symbol table [4 Marks]
f) Identify the problems associated with Manual Memory Management [4 Marks]
QUESTION TWO
a) In compiler construction, the end result of syntax analysis is IR.
i). Why is IR used? [3 Marks]
ii). What do we seek from a good IR? [3 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 THREE
a) Scanning and Parsing are usually separated in the context of compiler construction. Give two
reasons why scanning is not part of parsing? [4 Marks]
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
E = T { "+" T }.
T = F { "*" F }.
F = id.
[4 Marks]
d) Explain why the following grammar is not regular
E = F { "*" F }.
F = id | "(" E ")".
[4 Marks]
e) Give one limitation of regular grammar [2 Marks]
3
QUESTION FOUR
a) i) Explain the function of the Symbol Table, and two responsibilities of the same. [6 Marks]
ii) How is it implemented [2 Marks]
b) The parser is associated with checking the syntactic correctness of statements. However the code
has to still go through the semantic processing analysis.
Explain the tasks of semantic processing [6 Marks]
c) 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]
QUESTION FIVE
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]
More Question Papers
Exams With Marking Schemes