Compiler Construction Question Paper
Compiler Construction
Course:Bachelor Of Science In Information Technology
Institution: Kca University question papers
Exam Year:2011
UNIVERSITY EXAMINATIONS: 2010/2011
THIRD YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 3104: COMPILER CONSTRUCTION
DATE: APRIL 2011 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE
a) Describe how the following parsers are implemented
i. Graphical
ii. Hybrid
iii. Low Level (6 marks)
b) Regular Languages are described using regular expressions
i. Define what you understand by Regular Language
ii. Regular Expressions (4 marks)
c) What is the meaning of DFA. Using the following symbols to describe the components of DFA
S , S, d , s0 , F (5 marks)
d) Describe the scanning process. (4 marks)
e) Using a preferred algorithm (Flow chart or Pseudocode) write procedure that can be used to
concatenate all the Digits and Letters separately in an input string as given in the following
input example
Input iroew324hoihjo3252oooo
Digits = 3243252
Words=iroewhoihjooooo (8 marks)
f) When automating a scanner, what do you need to consider (3 marks)
2
QUESTION TWO
a) Symbolically define an Digit, letter and Identifier (6 marks)
b) With respect to a programming Language of your choice,
i. write a function that can be used to recognize all words that start with a digit (5 marks)
ii. write a function that can detect whether a word contain the following characters {+,-
,*,%,#,&} (5 marks)
iii. Write a program that would call the above two functions and state whether a given input
string is a valid identifier or not (4 marks)
QUESTION THREE
a) Describe THREE parser Operations (3 marks)
b) Define a CFG (4 marks)
c) Using Normal English where a S->NP VP where NP is Noun Phrase and VP is Verb Phrase,
construct the Parse tree for
The man read this book (7 marks)
d) The most common features of a parser are that it must be sound, complete and terminates.
Describe these features (6 marks)
QUESTION FOUR
a) Given the following grammar of algebraic expressions
1. S ? x
2. S ? y
3. S ? z
4. S ? S + S
5. S ? S - S
6. S ? S * S
7. S ? S / S
8. S ? ( S )
Show how it can generate the following input string
i. ( x + y ) * x - z * y / ( x + x ) (8 marks)
ii. Draw the respective parse tree for it (4 marks)
b) Using the following grammar
1. S ? SS
2. S ? ()
3. S ? (S)
4. S ? []
5. S ? [S]
derive the following sequence ([ [ [ ()() [ ][ ] ] ]([ ]) ]) (6 marks)
3
c) Describe 2 language problems (2 marks)
QUESTION FIVE
a) Give the following grammar
1. S -> E+T
2. E -> T
3. T -> E-T
4. T -> F
5. F -> E*F
6. F -> id
identify and eliminate the left recursion (12 marks)
b) Given the following grammar,
1. E ? T E’
2. E’? + T E’ | e
3. T ? F T’
4. T’? * F T’ | e
5. F ? ( E ) | id
i. Define the FIRST and FOLLOW
ii. Construct the Look-up table
More Question Papers
Exams With Marking Schemes