SECTION A – COMPULSORY QUESTION - hussein suleman



University of Cape Town

Department of Computer Science

CSC3003S Final Examination

2008

|Marks : 100 Time : 3 hours |

|Instructions: |

|Answer every section, i.e. sections A, B, C and D. |

|All questions in sections A and C are compulsory. Sections B and F offer some choice. |

|Show all calculations where applicable. |

Section A : COMPILERS [Answer questions 1 and 2 – both compulsory]

Question 1 : You must answer this question.

Consider the following grammar:

S → Session $

Session → Facts Question

Session → ( Session ) Session

Facts → Fact Facts

Facts →

Fact → ! string

Question → ? string

a) Calculate nullable, FIRST and FOLLOW sets for this grammar. [5]

b) Construct the LL(1) parsetable. [4]

c) Why is this grammar a LL(1) grammar? Give reasons for your answer by referring to your LL(1) parsetable. [1]

4 Question 2 : You must answer this question.

Multi-core CPUs can influence the design of modern optimising compilers. Firstly, the compiler could automatically convert traditional serial code into a parallel form, where 2 or more pieces of code run at the same time on different CPUs/cores. Secondly, the compiler itself could perform its processing in parallel. Answer the following questions with this in mind.

a) Describe one advantage and one disadvantage of separating the compiler front-end from the compiler back-end. [2]

b) Describe one advantage in having multiple distinct layers (frame generation, code generation, instruction selection, liveness analysis, etc.) within the compiler back-end. [1]

c) Static semantics should be checked before any code is generated. Discuss 2 examples of errors that can be checked for. [2]

d) Describe 3 typical optimisations that a compiler can perform on generated IR code, assuming the code being optimised runs on a single CPU/core. [3]

e) At which point/layer in the compilation process could the code being compiled be converted into segments that may run in parallel (assuming this is done independently of source language)? [1]

f) Briefly describe one technique to exploit multiple cores in the compilation process itself. [1]

Section B COMPILERS [ Answer any 3 questions ONLY ]

Question 3

a) What is the difference between a Concrete Parse Tree and an Abstract Parse Tree? [2]

b) Consider the grammar below describing the abstract syntax of expressions:

[pic]

Describe the Visitor Pattern. Supply the java code for the grammar above to illustrate this design pattern. [8]

Question 4

a) Construct the LR(0) and SLR parse tables for the following grammar and its given LR(0)-DFA: [10]

[pic]

[pic]

9 Question 5 [ Subprogram Analysis ]

a) Write the skeleton of a C-like program (with nested subprograms) that can result in the following activation record stack. All information that can be determined from the activation record stack must be indicated in the program. [5]

three: --------------------------+

| parm x=2 |

| parm y=2 |

| local w |

| local z |

| static_link -------------------+

| dynamic_link --------------+ |

| return address (two) | | |

two : ---------------------------+ ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download