Examiners: Time: 4 hours Prof P.D. Terry Marks: 180 Prof M. Kuttell Venue: Hamilton Laboratory
You will receive material relating to Section B at 08h00 on Friday 17 November, the day before the examination. No details will be given until then, but it is safe to assume that Section B will comprise a task or set of tasks that you could answer in a laboratory situation, similar in complexity to exercises you have done this year.
This year you will receive a challenging problem at 08h00 and be encouraged to develop a solution. Later in the day you will receive further hints as to how the problem(s) should be solved (by then you might have worked this out for yourselves, of course). You will be encouraged to study the problem(s) and the hints in detail, because during the examination on Saturday you will be set further questions relating to the system - for example, asked to extend a system in certain ways. It is my hope that if you have really understood the material on Friday, these questions will have solutions that come readily to mind, but you will have to answer these on your own!
You might like to have a look at some old examinations on the Web Pages to see the sort of standard expected - but remember that old exam papers are "context sensitive", as they apply to a particular course at a particular time that may have covered material in slightly different ways to the course done this year.
The "24 hour" problems have all been designed so that everyone should have been able to produce at least the basic solution, with scope given for top students to demonstrate their understanding of the subtler points of parsing, scanning and compiling. Each year I have been astounded at the quality of some of the solutions received, and I trust that this year will be no exception.
Please note that there will be no obligation to produce machine-readable solutions in the examination (in fact doing so is quite a risky thing, if things go wrong for you, or if you cannot type quickly). The tools will be provided before the examination so that you can experiment in detail. If you feel confident, then you are free to produce complete working solutions to all of Section B during the examination. If you feel more confident writing out neat detailed solutions or extensive summaries of the important parts of the solutions, then that is quite acceptable. Many of the best solutions over the last few years have taken that form.
Please take note of the following summary of those sections of the textbook that are examinable. The complete (published) book has some sections that are not examinable.
Chapter 1 - All
Chapter 2 - 2.1 ... 2.6
Chapter 3 - To the extent that you should be able to draw T-diagrams confidentally
Chapter 4 - 4.1 ... 4.10
Chapter 5 - 5.1 ... 5.9 5.10 appears in the contents, but was deleted (typo!)
Chapter 6 - 6.1 ... 6.4 You covered the Chomsky hierarchy in CSC 202
Chapter 7 - All
Chapter 8 - 8.1 ... 8.7 You will not be required to explain or develop an "FSA" scanner
Chapter 9 - All
Chapter 10 - All, but only in the sense that there might be "practical" type questions that would require you
to develop or annotate a Cocol grammar, which by now you should be able to do, I hope.
Chapter 11 - 11.1 describes the implementation of the Label class used in chapters 13 and 14.
Chapter 12 - All
Chapter 13 - All
Chapter 14 - 14.1 ... 14.6. We did not cover 14.7
Chapter 15, 16 None
You will need to be completely familiar with the Parva compiler as developed in the last weeks of the course and extended in the last practical of the course.
It has become a long-standing tradition (now going back far longer than most of you have been alive) for the Terrys to host a party for those who manage to survive Professor Pat's Perilous Parva Programming Problems. For family reasons, we are NOT able to host such a party this year, for which we apologise profusely.
There are many terms that you should make sure you understand and can define succinctly and accurately.
To help you search for terms you don't know, I remind you of the PDF file of "the Book" at
http://www.cs.ru.ac.za/courses/CSc301/Translators/cs3notes.pdf
Abstract syntax tree (AST) Object language Alphabet Optimizing compilers Ambiguity Orthogonality Analytic phase Overflow Attribute Parameter passing - value, ref and out Back end Phrase structure Backpatching Portability Backtracking Postfix notation BNF Pragma Character handler Precedence Closure Produces directly Cocol Productions Code generation Program counter Compile-time Pseudo-code Constraint analysis Range checks Context condition Regular expression Cycle-free grammar Regular grammar Dangling else Reverse Polish Notation Decompiler Run-time Decorated tree Scanner Defining occurrence Scope Dereferencing Self-embedding Dynamic semantics Semantic action EBNF Semantic attributes Emulator Semantically driven parser Environment Semantic error detection Fetch-execute cycle Semantic overtones FIRST function and sets Semantics FOLLOW function and sets Sentence Frame file Sentinel node Frame pointer Sentential form Front end Short circuit evaluation Goal symbol Source handling Global scope Source language Global stack frame Stack frame Glogan stack pointer Stack pointer Grammar Start symbol High-level translator State diagram Host language State variable Instruction set Static semantics Intermediate code Symbol Interpreter Symbol table JIT compilation Syntactic class Keywords Syntax Kleene closure Syntax directed translation Language Systems program Lexeme T-diagram Lexical analyser Table-driven algorithm Lexicon Target language LL(1) conflict resolution Terminal start sets LL(1) restrictions Terminal successors LL(k) parsing Token Local scope Top-down parsing Macro assembler Type checking Native code Vocabulary Non-terminal Weak separator Null production Weak terminal Nullable Zero address instruction