ExamsSCHOOL OF SCIENCE AND TECHNOLOGY

National Open University Exam Past Question – CIT 445 JANUARY/FEBRUARY 2013 EXAMINATION

NATIONAL OPEN UNIVERSITY OF NIGERIA CIT 445 Principles & Techniques of Compilers

14-16 AHMADU BELLO WAY, VICTORIA ISLAND, LAGOS

SCHOOL OF SCIENCE & TECHNOLOGY

JANUARY/FEBRUARY 2013 EXAMINATION

 

 

Course Code:          CIT 445                                                                       Time:  2½ hrs

 

Course Title: Principles & Techniques of Compilers                        Course Credit Unit: 3

 

Instruction: Answer any five (5) questions. Each question carries 14 marks

 

 

 

1a) Explain what is meant by the term handle?) 2 marks b) Consider the following grammar for list structure:

S → a | ^ | (T)

 

T → T,S | S

 

  1. i) find the rightmost derivations for: ) 7marks

 

(i) (a, (a, a))

 

(ii) (((a, a), ^, (a)), a)

 

  1. ii) Indicate the handle of each right sentential form for the derivations in (a)

above       ) 5 marks

 

 

 

2a) Briefly describe the operation performed by the shift-reduce parser) 6 marks b) Given the context-free grammar G below:

G:       E ® E + E

 

E ® E * E E ® (E)

E ®  id

 

State the steps performed by the shift-reduce parser when analyzing the input string:

id1 + id2 * id3                ) 8 marks

3a) Explain what is meant by the term Viable Prefix?        ) 3 marks

 

  1. b) Given the grammar G with following production rules, S → a | aS | bS, determine whether the string aababbba can be generated by the grammar ) 5marks
  2. c) Enumerate any three of the errors which can be detected during lexical analysis
YOU MAY ALSO LIKE  National Open University Exam Past Question - CHM 305 MAY/JUNE 2012 EXAMINATION

) 6 marks

 

 

4a) Explain what is meant by top-down parsing technique ) 2 marks b) State the difficulties in top-down parsing                      ) 6 marks c) Using examples, state and illustrate how to minimized ) 6 marks

 

 

5) Consider the grammar Ggiven below: G: E ® E + T / T

T ® T * F / F

 

F ® (E) / i

 

  1. a) Find all the first and last terminals in this grammar ) 5 marks
  2. b) Generate the operator precedence passing table for this grammar) 9 marks

 

 

6a) Define the following for any given grammar? ) 5 marks i)  FOLLOW A

  1. ii) FIRST(α)
  2. b) Consider the grammar,

 

G:        E → E + T | T

 

  T → T*F | F  
 

F → (E) | i

 

i)

ii)

 

Find the FOLLOW(A) for all the terminal in G Find the FIRST(α) for any string derivable from G

 

) 4 marks

) 5 marks

 

 

7a) Consider the grammar

 

S → L = R | R L → *R | i

R → L

 

 

  1. a) Compute all the LR(0) items for the above grammar )10 marks b) Construct an NFA whose states are the LR(0) items from (a) )4 marks

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Close