Admission requirements
This is a practical-intensive course, which involves lots of low-level systems programming. Mastering all this is highly rewarding. Students are assumed to have taken courses in (object-oriented) programming, and computer architecture at a BSc level. Prior knowledge of Java is not required and can be learned during this course.
Description
Computer programs in a higher programming language cannot be executed by a computer until they have been translated into lower-level executable code. In many cases this is done by a compiler.
In this course we learn how compilers convert source code into assembly code in several steps. We study the theory behind compilers with a keen eye on the practical aspects of building a compiler, and apply this in a series of assignments. We construct a compiler for the ChocoPy language, which is a subset of Python. The compiler itself is written in Java and outputs RISC-V assembly code.
Through compiler construction, we lear how programming languages work and how they are implemented. We get insight into the reasons why programming languages are designed the way they are, and what their tradeoffs and limitations are. Because of this, and because a lot of programming has to be done in the practical, you will become a better programmer with a much more in-depth understanding of languages and tools.
Topics covered during the lectures relate to the process of constructing a compiler, e.g., parsing, semantic analysis, code generation, and code optimization.
Course Objectives
After this course, students are expected to be able to:
Reproduce concepts used in compilers, such as the stages of compilation, syntax-directed translation, type conversions, basic blocks, stack frames, etc.
Explain how programming languages work and how they are implemented, including design considerations and limitations.
Understand how grammars and intermediate representations are used to implement the syntax and semantics of programming languages.
- How a grammar can be made unambiguous.
- How grammars can be used to implement syntax-driven analysis.
- How to construct and use abstract syntax trees and three-address code.
- How symbol tables and scoping work.
- Explain how a type system helps with preventing programming errors and generating more efficient code.
Discuss how to generate code, how procedure calls are implemented, how to manage the stack and memory, explain the interplay between generated code and a runtime system.
Implement lexical analysis and parsing.
Implement semantic analysis and type checking.
Implement code generation and optimization.
Analyse the quality of the generated code and its performance.
Timetable
In MyTimetable, you can find all course and programme schedules, allowing you to create your personal timetable. Activities for which you have enrolled via MyStudyMap will automatically appear in your timetable.
Additionally, you can easily link MyTimetable to a calendar app on your phone, and schedule changes will be automatically updated in your calendar. You can also choose to receive email notifications about schedule changes. You can enable notifications in Settings after logging in.
Questions? Watch the video, read the instructions, or contact the ISSC helpdesk.
Note: Joint Degree students from Leiden/Delft need to combine information from both the Leiden and Delft MyTimetables to see a complete schedule. This video explains how to do it.
Mode of Instruction
The course is composed of two components:
1. Lectures given by the instructor, to setup course format, assignments, and to teach key topics in compiler construction.
- Self-study Lab Assignments. Students are expected to work on the lab assignments autonomously, outside of the lectures. We also have a Lab Class every week. In these labs, students can ask questions and get practical help from teaching assistants. Please note that this is a hands-on course, where the lab constitutes a large part of the final grade.
For the lab of this course, we implement a ChocoPy compiler. ChocoPy is a subset of Python (all ChocoPy programs are valid Python programs). The compiler will be written in Java. The output of the compiler is RISC-V assembly instructions, which can be emulated on any machine. Thanks to the use of Java, the compiler and generated code can run on any platform, so you can do the whole assignment on your own PC or laptop.
A regular compiler has 4 main stages to go from code to machine-understandable instructions: 1. Lexical Analysis and parsing 2. Semantic analysis and type checking 3. machine-code emitting and 4. optimization. There are 4 practical assignments, each one implementing one of the aforementioned stages, designing compiler functionality to treat various language features and compiler components and optimizations. Students can build each next stage on top of their previous stage implementations. However, reference implementations are also provided after each assignment, to make sure you do not get stuck if an earlier assignment goes less well than anticipated.
A base framework will be published to write your implementation in. We also provide tests to verify implementation correctness. The assignments will be implemented in Java.
Assessment method
The final grade of this course is composed of:
**- a large practical assignment (75%) **- an exam (25%)
The lab grade is the weighted average over the lab assignments, weights to be announced at the start of the course. In addtion, there are various optional bonuses which add on top of the regular activities. The bonuses are programming assignments, expanding the compiler designed in the main practical assignment (up to 1p extra). We also organize a competition, where the compiler that generates the fastest code on our benchmarks receives one bonus point. The assignments can be done in pairs.
In this course, the use of generative AI (e.g., ChatGPT, copilot, etc.) is not allowed. We perform a short individual oral examination where you have to explain your solutions and code. Failure to explain your own code leads to disqualification.
To pass the course, students have score a grade higher than or equal to 5.5 for each of the assignments. All assignments have to be submitted to get a grade for this course. Each assignment can be submitted twice: once to get feedback, and one final submission for the grade. Deadlines for the assignments are hard deadlines; For late submissions, 1 point is deducted, and a submission cannot be more than 1 week overdue. You can resit at most one of the lab assignments, but the grade for that assignment will be capped to a 5.5. The grade for the exam also must be 5.5 or higher. Partial scores will not be kept between academic years.
Course load
Total hours of study: 168 hrs.
Practical work: 100 hrs
Lectures & Tutoring: 20 hrs
Self-tuition: 48 hrs
Reading list
Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, second edition, Pearson New International Edition, 2013, ISBN 9781292024349.
Registration
As a student, you are responsible for enrolling on time through MyStudyMap.
In this short video, you can see step-by-step how to enrol for courses in MyStudyMap.
Extensive information about the operation of MyStudyMap can be found here.
There are two enrolment periods per year:
Enrolment for the fall opens in July
Enrolment for the spring opens in December
See this page for more information about deadlines and enrolling for courses and exams.
Note:
It is mandatory to enrol for all activities of a course that you are going to follow.
Your enrolment is only complete when you submit your course planning in the ‘Ready for enrolment’ tab by clicking ‘Send’.
Not being enrolled for an exam/resit means that you are not allowed to participate in the exam/resit.
Contact
Teacher of the course: Rob van Nieuwpoort.
Onderwijscoördinator Informatica bachelor: Education coordinator LIACS bachelors.
Remarks
Voor meer informatie over Brightspace kun je op deze link klikken om de handleidingen van de universiteit te bekijken. Bij overige vragen of problemen kan contact opgenomen worden met de helpdesk van de universiteit Leiden.
Software
Starting from the 2024/2025 academic year, the Faculty of Science will use the software distribution platform Academic Software. Through this platform, you can access the software needed for specific courses in your studies. For some software, your laptop must meet certain system requirements, which will be specified with the software. It is important to install the software before the start of the course. More information about the laptop requirements can be found on the student website.