University Of Pretoria SA Coronavirus Website Computer Science Department

COS341 - Compiler Construction


Module Content

Background Reading - Background Reading
Paper by Chen and Erwig: "When type inference fails, it is often difficult to pinpoint the cause of the type error among many potential candidates. Generating informative messages to remove the type error is another difficult task due to the limited availability of type information. Over the last three decades many approaches have been developed to help debug type errors..."
This paper explains the Generalised LR parsing technique (GLR) which can cope even with ambiguous context-free grammars.
This paper discusses the computational runtime costs of Generalised LR parsing (GLR)
In this paper, professor Peter Pepper from the Technical University of Berlin (Germany) explains how you can safely transform a given grammar to make it better suitable for parsing.
Though the detection of ambiguities in context-free grammars is generally UNdecidable, the situation is not entirely hopeless: In this BSc-Dissertation, a young BSc-Student from Germany is giving you a lot of help which you can apply when you need to search your ambiguities in your Practical Project grammar. If a young BSc-student from Germany can do it, then you can do it, too :)
The LR(k) grammars/languages are the genuine sub-class of all those context-free grammars/languages that can be handled by a DETERMINISTIC Push-Down Automaton (PDA) with 1 stack. (Remember that deterministic PDA are "weaker" than non-deterministic PDA, whereas NFA and DFA, without any stack, are equally strong). In this classical paper, "grandmaster" Donald Knuth explains the parsing of LR(k).
LR(1) grammars/languages ---NOT to be confused with LL(1)--- are the sub-class of all those LR(k) grammars/languages for which k=1. In this paper, which is based on Knuth's work, Korenjak explains that LR(1) parsing is much simpler than LR(k) parsing but still "good enough" for many practical application cases. What Korenjak is calling a 'processor' in this paper is actually a parser; thus please do not get confused about the terminology.
This paper by Dahlhaus and Warmuth explains nicely why Context-SENSITIVE Grammars are NOT used for compiler construction! Even in those cases, in which the word-membership problem is (still) decidable, the decision procedure would be far too 'expensive' in run-time: the compiler would be too slow and thus no longer user-friendly.
Some more background theory for you on the topic: "Undecidable Problems for Context-free Grammars".
Slide show from another university: Theory of Formal Languages. Use this as a "reminder" of what you had seen in COS210 last year.
"Refresher" slide-show on some topics Theory of Computation, compiled by Jeanne Ferrante. It is presumed that students of COS341 are reasonably familiar with these topics from earlier courses.
Practical Project - Practical Project: Task Specifications
Test Cases
Part 00 Test Cases
Test cases used to mark part 00
Part 01 Test Cases
test case files for part 01
Part 02 Test Cases
test case files for part 02
Part 03 Test Cases
test case for part 03
Part 04 Test Cases
test cases for part 04
Task 05 Test Cases
test cases for part 05
Task Booklet for: Code Generation.
Sepcification for task 04
Practical Task Booklet for: Type Checking.
Practical Task booklet for: Static Semantic Analysis / Scope Analysis / Symbol Table.
This project file contains the 'SPL' grammar, for which a parser must be written, together with some further instructions and advice.
The project has started! In this task booklet you can find your first instructions. More will follow later. I wish you happy working :)
Overview: Semester Project
This slide show gives you a 'top-level' overview of what you will have to do in your semester project. Further task details will be provided as the semester continues.
BASIC Interpreter
Interpreter to be used for task 05.
Documentation Requirements
Details about expected information for practical documentation.
Scope Design
Design decision for the scope checker.
Marks - Mark Sheets (anonymised)
The points are "out of 5".
marks for part 01
part 02 marks
part 03 marks
mark sheet for part 03
part 04 marks
part 04 marks
part 05 marks
marks for part 05
Description: Accumulated Semester Marks, out of 60, BEFORE EO2. Students who have 20/60 need a Distinction in EO2 to pass the course. For students with a mark SMALLER than 20/60, participation in EO2 is NOT recommended: Rather focus your study-efforts onto other courses in which you still have a better chance! Students who are already at 50/60 (or higher) are still obliged to participate in EO2!
EO1 Semester Test - The Task Sheet will appear here on the 1st of June at 17h30!
PDF version of the EO1 semester test specification.
PowerPoint version of EO1 semester test specification.
Help slides to Chapter 6: Part A.
Help slides to Chapter 6: Part B.
Help slides to Chapter 6: Part C.
Help slides to Chapter 6: Part D.
Help slides to Chapter 6: Part E.
Related to Chapter #6. The slide-show explains how Target Code is generated recursively from the Abstract Syntax Tree and the Symbol Table.
This slide show (13 slides) provides some additional remarks and comments to chapter #7 of our book. Read the slide show first, then chapter #7, and thereafter the slide show once again.
Help slides to Chapter 8: including the recursive set development to the fix-point.
Help slides to Chapter 8: yet another graph colouring example.
Help-slides to Chapter 9.

Module forums

The new CS forums are available here.

Module Links

"In formal language theory, a context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language..."
"In computer science, an LL parser (Left-to-right, Leftmost derivation) is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Leftmost derivation of the sentence..."
"In computer science, LR parsers are a type of bottom-up parser that analyses deterministic context-free languages in linear time..."
"In the formal languages of computer science and linguistics, the Chomsky hierarchy (occasionally referred to as the Chomsky-Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars..."
"In formal language theory, a context-free grammar G is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form: ..."
"In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables..."
"A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars..."
"In automata theory, the class of unrestricted grammars... is the most general class of grammars in the Chomsky hierarchy... for every unrestricted grammar G there exists some Turing machine capable of recognizing L(G) and vice versa..."


Remember Me

Module Description

THIS WEB PAGE IS THE STUDY GUIDE for COS341: COMPILER CONSTRUCTION. Please carefully take note of all further announcements which will appear on this web page! In COS341 we follow ...

Show Long Description

Lecturer Information

Course Coordinator

Prof Stefan Gruner


Assistant Lecturers


Mr Letanyan Arumugam

Teaching Assistants

There are no teaching assistants assigned.

Class Representatives

Active Assignments

No currently active Assignments.
Check the assignment portal:

Active Fitch Fork Assignments

No currently active Fitch Fork Assignments
Check the assignment portal:

Active Bookings

    No bookings available

Lab Bookings

    No lab bookings available

Active Team Allocations

    No team allocations available

Active Bids

Individual Bids

    No individual bids

Team Bids

    No team bids

Team Pages

Team Pages

    No Team Pages

Team Pages Open to Module Members

    No Public Team Pages

Team Pages Open to Everyone

    No Public Team Pages

Active Polls

How is it going with home-studying during COVID19?

I am coping: Still in good spirit
I am struggling: The situation is very difficult
Cannot cope any more: Feeling overwhelmed

All content copyright © Department of Computer Science, School of IT, University of Pretoria, South Africa