Ccs 305:Introduction To Compiler Construction Question Paper
Ccs 305:Introduction To Compiler Construction
Course:Bachelor Of Science In Computer Science
Institution: Maseno University question papers
Exam Year:2016
SECTION A:ANSWER ALL QUESTIONS
Question one(30 marks)
a)Given the grammar G:
E------>E+T
E------>T
T------>T*F
T------>F
F------>(E)
F------>a
Derive the leftmost parse of the sentence a*(a+a),hence draw the resulting parse tree(8mks)
b)Code optimization attempts to improve the time and space requirements of a program.Enumerate five common ways that can be used to implement code optimization. (5mks)
c)Use appropriate symbolic notation to explain the components of a context-free grammar.(5mks)
d)Explain the purpose of a symbol table in the compilation process,by stating typical attributes that can be defined for variables,procedures and functions (5mks)
e)State and briefly explain five types of errors that can be encountered during the compilation phases (7mks)
SECTION B:ANSWER ANY TWO QUESTIONS
Question two(20 Marks)
Describe the different phases of compiler,clearly explaining the activities undertaken in each phase.(20mks)
Question three(20 Marks)
a)Consider the language L consisting of all strings w over the alphabet {c,h} such that w contains hhh or cccc(i.e at least 3 h in sequence,or at least 4 c in sequence,or both).For example ,the strings chchhh,cccchc,hhhcccch,hhh,etc. belong to the language L.
i)Construct a regular expression for L(4mks)
ii)Construct from the regular expression an NFA recognizing L(5mks)
iii)Construct a DFA recognizing L,either by deriving from the NFA of question (ii),or by constructing one directly.(6mks)
b)The following priduction rules represent a regular grammar
S----->aA
A----->aA
A------>bB
B------>bB
B------>£
i)Determine the regular language defined by the above grammer.(3mks)
ii)List four strings of at least five terminals that can be accepted by the language (2mks)
Question four(20 Marks)
a)Explain how a shift-reduce parse operates,clearly describing the role of stack,and various actions performed during the parsing process.(6mks)
b)Use a simple context-free production to explain how handles are generated,then state their importance in shift-reduce parsing.(3mks)
c)Given the production of a context-free grammar G:
E------>E+E
E------>E*E
E------>(E)
E------>i
i)Derive a top-down rightmost derivation of G (3mks)
ii)Use a table containing stack values,input string and action values to show the steps performed when analyzing the input string:i +i * (i)(8mks)
Question five(20 Marks)
a)Distinguish between recursive descent parsers and non recursive descent parsers (2mks)
b)Suppose you are given a context free grammar G with the following productions
E------>TE'
E'------>+TE'|£
T------>FT'
T'------>*FT'|£
F----->(E)|i
i)Generate the FIRST sets and FOLLOW sets for all non terminals of G(6mks)
ii)Construct the predictive parsing table for G(6mks)
iii)Use the generated parsing table to determine if the sentence i+i*i can be formed from the grammar G(6mks)
More Question Papers