NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
APRIL 2019 EXAMINATION

COURSE CODE: CIT445

COURSE TITLE: Principles and Techniques of Compilers

CREDIT: 3 Units

TIME ALLOWED: 2½ Hours

INSTRUCTION: Answer Question 1 and any other FOUR (4) Questions

1a) Define formal language (3 marks)

  b) State three areas of application of formal languages (3 marks)

3. Define translator, hence, state the advantages of a translator in computing. (4 marks )
4. Enumerate the functions performed by the lexical analyser (4 marks)
5. State four benefits of LR parsing  (6 marks)
6. Define FIRST(α) for any given grammar? (2 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:

id₁ + id₂ * id₃   (6 marks)

3a)  List the common techniques for building tables for an “LR” parser stating the characteristics of each?    ( 6½ marks)

b) Consider the grammar,

     G:   E → E + T | T

T → T*F | F

F → (E) | i

What is the augmented grammar for this grammar. (2 marks)

c) Explain what is meant by the term Viable Prefix?            (3½ marks)

4) Consider the grammar G below:

      G: E ® E + T / T

T ® T * F / F

F ® (E) / i

i) Generate the non-left recursive version of the grammar (5 marks)

ii) Find FOLLOW of all the non-terminal symbols in the non-left recursive version of the grammar  (7 marks)

5a) Given the grammar G with the following production rules, S → a | aS | bS, determine whether the string aababbba can be generated by the grammar(6 marks)

  b) Enumerate any three of the errors which can be detected during lexical analysis (6 marks)

6) Consider the grammar,

G: S → a | aS | bS

1. Find the LR(0) items for this grammar  (9 marks)

 b) Construct an NFA whose states are the LR(0) items from (a) above.      (3 marks)