Credits

There will be a practical test in December, as part of the tutorials. Those who fail will have another opportunity in January. Success in the practical test is required for enrolling to the exam.

The exam is oral with a time for written preparation.

Lectures

The dates below are only an approximation; actual timing will differ. The contents of slides may be adjusted just before every lecture.

29.9.2025	Compiler - an introduction	01-comp.pptx
6.10.2025	Lexical analysis	02-la.pptx
13.10.2025	Syntax analysis - an introduction	03-sxa.pptx
20.10.2025	Syntax analysis - top-down parsing	03-sxa.pptx
27.10.2025	Syntax analysis - bottom-up parsing	03-sxa.pptx
3.11.2025	Semantic analysis	05-saatr.pptx
10.11.2025	Intermediate code	04-ic.pptx
24.11.2025	Intermediate code generation	06-genic.pptx
1.12.2025	High-level optimizations	07-opt.pptx
8.12.2025	CPU architectures	08-cpu.pptx
15.12.2025	Code generation	08-cpu.pptx
5.1.2026	Runtime	09-rt.pptx
	Interpreted languages	10-interp.pptx

Playground

In the previous seasons of this course, students were required to implement their own compiler of a subset of the C language. As the playground, you will receive the teachers' implementation of this compiler. The following paragraphs describe the main elements of the implementation.

Syntax of the language

The grammar rules of the subset are in the doc/selected-grammar.md in the skeleton repository. This grammar was created by removing some rules from the C programming language specification (working draft) Annex A.

• The start nonterminal is "translation-unit".
• There can be an arbitrary number of white space characters (CR, LF, SPACE, TAB) between the tokens as well as before the first one and after the last one.
• Comments also count as a white space.
• All identifiers and keywords are case-sensitive.

Lexical analysis

• All objects representing tokens are created using a call to a function like cecko::parser::make_WHILE(...) whose declarations are generated in <build-folder>/fmwk/ckdumper.hpp by the build system for cecko1. All these functions have a parameter location_type l, pass ctx->line() here.
• The list of token names (and additional parameter types) may be found in ckdumper.y (it has to be the same as in caparser.y which is not used when building cecko1)
• Some tokens (like >,<,>,<=,>= or +,-) are grouped together. The object representing the token is shared across each group (it will become the same terminal in the grammar); individual tokens are distinguished using an additional parameter of the object (an enumeration type associated to the group, like cecko::gt_cmpo::LT - see ckgrptokens.hpp).
• Identifiers and literals have an additional parameter of the object - the text or value - pass the value of the correct type here
• String literals shall not contain end-of-line (non-escaped \n). You will need 'start conditions' feature of FLEX to implement escape sequences. The effective value (with quotes removed and escapes replaced) shall be passed to make_STRLIT as std::string (cecko::CIName is just an alias)
• Character literals shall not contain end-of-line (non-escaped \n) and they represent always only one char in Cecko. Remember, characters have type int in C.
• Multiline comments are enclosed in /* and */ (not inside a string or one-line comment). Comments can contain any sequence of any characters. Multi-line comments can be nested - starts (/*) and ends (*/) have to be paired correctly. You will certainly need 'start conditions' to handle this.
• One-line comments start with // (not inside a string or multi-line comment) and end with end of the line. Comments can contain any sequence of any characters except the end-of-line. You will certainly need 'start conditions' to handle this.
• Call ctx->incline() whenever you meet end-of-line - this increments ctx->line(). The first line has number 1 (ctx->line() is already initialized to 1). (You must not use %option yylineno to count lines.)

Parsing

Slides (en):

• The grammar shall not produce any shift/reduce and reduce/reduce conflicts. Warning: bison does not report conflicts to stdout. CMake projects instruct bison to report the conflicts in <build_folder>/stud-sol/caparser.y.output, but you have to examine this file manually.
• The lexical element identifier corresponds to two tokens IDF and TYPEIDF depending on the content of compiler tables. The call if(ctx->is_typedef(yytext)) is used for detecting type identifiers using compiler tables. The identifier FILE is known to the compiler as a type identifier (the implementation does not include preprocessor, therefore, a small part of standard C library is built into the compiler).

Declarations

Slides (en):

Framework doxymentation

Frequently asked questions

• void, _Bool, char, int, TYPEIDF, const
• pointer and function declarators
• variable and function declarations and definitions
• return statement containing an INTLIT
• typedef definitions
• array declarators (with an INTLIT in brackets)
• enum declarations and definitions
• struct declarations and definitions

Expressions

Slides (en):

Framework doxymentation

Frequently asked questions

• Integer, character, and string literals
• Implicit conversions:
• Array to pointer (string literals are of type char[N])
• _Bool/char to int, int to char
• Function calls (including variadic functions like printf)
• Arguments and return values of types char/int/pointer
• int operators:
• Unary +, -
• Binary +, -, *, /, %
• Pointer operators:
• Unary *, &
• Assignment operator (into char/int/pointer L-values)
• Return statement
• sizeof operator
• int ++, --, +=, -=, *=, /=, %= operators
• pointer ++, --, +=, -= operators
• [] operator
• Pointer+int, int+pointer, pointer-int operators
• .,-> operators
• Assignment, function arguments and return values of type struct

Control-flow statements and Boolean expressions

Slides (en):

Framework doxymentation

• Implicit conversions:
• char/int/pointer to _Bool
• _Bool operations:
• Unary !
• Arguments and return values of type _Bool
• Assignment operator into _Bool
• int operators:
• ==,!=,<,>,<=,>=
• if and if-else statements
• while and while-do statements
• for statement
• pointer operators:
• ==,!=,<,>,<=,>=
• pointer-pointer
• &&, || operators with shortcut evaluation

Developing and testing

Read the Using your Cecko repository section before cloning the skeleton. The framework and skeleton files may be updated for various reasons, therefore, you will need a method to merge the updates into your project.

The skeleton framework contains the following folders:

• doc - documentation
• fmwk - framework, do not change the files here
• main - different main function for different homeworks, do not change the files here
• solution - this is your playground, update incrementally files as you need (however don't touch CMakeLists.txt)
• test - test files and expected results

You will need to prepare your building environment as described in Prerequisites.

Refer to Building and running Cecko for instructions on building and running the code.

The solution files

• calexer.lex - Flex source file for the lexical analyzer
• caparser.y - Bison source file for the parser and semantic actions
• casem.hpp - C++ header file
• casem.cpp - C++ source file

Test files

The Cecko source files have the usual suffix .c, the corresponding expected outputs are in the .gold files.

The test files whose names end with "n" contain intentional semantic errors and are expected to fail during compilation.

Prerequisites

Platform

Recodex uses Linux and GCC to compile and run your submissions. It may trigger errors which escaped detection in other compile/run environments. For such cases, it is advantageous to have a GCC-based build environment prepared beforehand.

On the other hand, the Cecko sources are intended to be multi-platform and the skeleton is regularly tested with both GCC and Microsoft Visual C++. Therefore, development using MSVC is possible (and encouraged).

Windows Subsystem for Linux

For developers equipped with Windows 10, Windows Subsystem for Linux (WSL) is recommended as the best approach to multi-platform development. Compiling, running and debugging in the WSL-GCC environment is integrated in Visual Studio 2022 (as well as VS Code) and fully supported by Cecko projects.

Note: If you plan to build LLVM on your own (instead of downloading binaries), make sure that you use WSL 2 and that the working folder is at native Linux filesystem (i.e. not /mnt/...).

Git

Make yourself familiar with the principles of git.

In Linux, you will probably use command-line git which is present in all modern Linux distributions.

In Windows, TortoiseGit is the recommended option.

You may also try using the Git plugins in Visual Studio 2022 or VS Code; however, be aware that some advanced commands may not be available there.

To access gitlab.mff.cuni.cz, you will first need to login (using your SIS credentials) in its web interface and register your SSH keys there (if you have not done so yet).

Build tools

cmake

CMake 3.19 or newer is required. It is packaged in sufficiently new distributions of Linux (including Ubuntu 22.04 in WSL), installed by something like:

sudo apt install cmake

For Windows, cmake (and ninja) is installed with Visual Studio 2022 when C++ CMake tools for Windows is enabled in the Visual Studio Installer. C++ CMake tools for Linux is required when Visual Studio is used to build in WSL or remote Linux.

When using VS Code, cmake (as well as a C++ compiler) must be installed as an external tool.

ninja and zlib

If you use Visual Studio support for Linux, you may need to manually install ninja build system like:

sudo apt install ninja-build

In some Linux distributions, you may encounter linker complaining about -lz. The remedy is installing libz like:

sudo apt install zlib1g-dev

bison and flex

bison 3.4 and flex 2.6.4 or newer are required. They are present in any (sufficiently new) distribution of Linux (including WSL), installed by something like:

sudo apt install bison flex

For Windows, they may be downloaded from lexxmark/winflexbison. Unpack the .zip to a suitable location and add the folder to the Path variable using the Edit the system environment variables control panel dialog. This package contains win_bison.exe and win_flex.exe - these names are recognized by cmake.

If you are unable to install bison/flex into system folders or if cmake does not find (the correct version of) bison or flex, you may specify it explicitly when invoking cmake:

cmake -DBISON_ROOT=<bison_install_folder> -DFLEX_ROOT=<flex_install_folder> ...

Note that the bison executable must be located in <bison_install_folder>/bin etc.

Within Visual Studio, you may specify the BISON_ROOT and FLEX_ROOT in the CMake Settings.

Note: You may also use the winflexbison3 package from Chocolatey.

Note: You cannot use WSL installations of bison/flex for MSVC builds (and vice versa) because cmake would not invoke them properly. Therefore you will probably end with two bison/flex installations if you do both MSVC and GCC builds, similarly to having two installations of cmake in this case.

Installation using WinGet

WinGet is a package manager available by default in Windows 11. However, the WinGet package WinFlexBison.win_flex_bison is broken and can only be installed using this method:

• Open a command prompt or PowerShell as administrator and run the command: winget settings --enable LocalManifestFiles
• Download the three manifest files from the WinGet Community Repository entry for WinFlexBison.win_flex_bison
• Append the line ArchiveBinariesDependOnPath: true to the downloaded WinFlexBison.win_flex_bison.installer.yaml file
• Open a (non-elevated) command prompt and execute the command: winget install --manifest the-folder-containing-the-three-manifest-files
• Open a new command prompt and verify the installation by running win_bison --version

C++20 compiler

MSVC 19.36 (part of Visual Studio 2022 v17.6) and gcc 11.4.0 are verified to be sufficient for the compilation of Cecko.

LLVM

Cecko uses the intermediate code (IR) and JIT x86 code generator (MCJIT) from the LLVM framework. The required version is LLVM 15 or newer; the tests in Recodex run with LLVM 19.1.0.

Although the LLVM team recommends building LLVM from sources, it may be well beyond the capability and patience of most Cecko developers. Therefore, downloading a binary version is recommended.

Note: Cecko requires only headers and static libraries; however, all binary distributions of LLVM include also many executables and dynamic libraries. Some downloads/packages include only the executables which is insufficient for Cecko. This also applies to some downloads at LLVM Pre-Built Binaries

Linux (including Ubuntu 22.04 in WSL) - using system-wide installation

The simplest way to install the required LLVM modules is from a Linux distribution channel, like:

sudo apt install llvm-19

cmake will automatically find LLVM if installed in this way.

Note: Although these libraries are compatible with Debug mode, they do not contain full debug info, for example, stepping into LLVM procedures during debugging of Cecko may be impossible.

Linux - installing and using private LLVM copy

Pre-built LLVM 19.1.0 binaries for Cecko are available here:

• llvm-19.1.0-install-x86_64-gcc-14.2.0-release.tgz (391 MB).

Note: These are the same binaries as used in Recodex, compiled with g++ 14.2.0

When building Cecko with a private LLVM installation, cmake must be instructed to find LLVM by setting the LLVM_DIR cmake variable to the value <llvm-install-folder>/lib/cmake/llvm as follows:

cmake -DLLVM_DIR=<llvm-install-folder>/lib/cmake/llvm <...other-arguments...>

Windows binaries

Beware: The Windows versions of Pre-Built Binaries published by LLVM (as of October 2023) are not complete enough for Cecko.

Beware: vcpkg can now install LLVM; however, the installation is implemented by building from sources and may take several hours.

Pre-built LLVM binaries for Cecko are available here:

Visual Studio CMake Configuration		CMAKE_BUILD_TYPE	Download
x64-Debug	x64-Release
(default)	(incompatible)	Debug	llvm-17.0.1-install-x86_64-msvc-19.36-debug.zip (1.2 GB)
(incompatible)	(default)	RelWithDebugInfo	llvm-17.0.1-install-x86_64-msvc-19.36-relwithdebinfo.zip (651 MB)
(incompatible)	(works)	Release	llvm-17.0.1-install-x86_64-msvc-19.36-release.zip (332 MB)

Note: The above binaries are compatible with Visual Studio 2022 v17.2.0 (May 2022) or newer.

When building Cecko, cmake must be instructed to find LLVM by setting the LLVM_DIR cmake variable to the value <llvm-install-folder>/lib/cmake/llvm.

In Visual Studio 2022, the LLVM_DIR variable is set in the CMake variables and cache section of the CMake Settings (CMakeSettings.json); you may run Generate Cache to pre-create this variable before setting it to the correct value.

In VS Code, the LLVM_DIR variable is located in the cmake.configureSettings entry of .vscode/settings.json.

When cmake is invoked from command-line, it may look like:

cmake -GNinja -DLLVM_DIR=<llvm-install-folder>/lib/cmake/llvm <...other-arguments...>	

Note: Make sure you use ninja (-GNinja) as the cmake Generator. Modern versions of cmake for Windows generate Visual Studio projects by default and some commands described in this guide do not work correctly in this mode. If cmake is invoked by Visual Studio, Ninja is enforced by default.

Note: If you compile with Microsoft Visual C++ from command-line, make sure that the x64 version of cl is visible when cmake is invoked (e.g. by starting from the "x64 Native Tools Command Prompt for VS 2022"). The cecko system is incompatible with 32-bit x86 mode which could be the default elsewhere.

Building LLVM (advanced)

If you decide to ignore binary distributions and build LLVM on your own (beware, it may require several hours of downloading and building), the simplest approach is cloning llvm-project into a <llvm-project-folder>:

git clone https://github.com/llvm/llvm-project.git <llvm-project-folder>	

If you want to have exactly the same version as in recodex, checkout the tag llvmorg-17.0.1.

To build and install, create a <llvm-build-folder> and a <llvm-install-folder>, then configure, build and install using:

cd <llvm-build-folder>
cmake -GNinja -DLLVM_PARALLEL_COMPILE_JOBS=8 -DLLVM_PARALLEL_LINK_JOBS=1 \
  -DLLVM_TARGETS_TO_BUILD=X86 -DCMAKE_BUILD_TYPE=Debug \
  -DCMAKE_INSTALL_PREFIX=<llvm-install-folder> \
  <llvm-project-folder>/llvm
cmake --build .
cmake --install .

When building Cecko with the home-built LLVM, define the LLVM_DIR variable as <llvm-install-folder>/lib/cmake/llvm.

See also Building LLVM with CMake.

The Cecko repository

To be defined.

Building and running Cecko

Building

Command-line

Create a <build-folder>, by convention as <cecko-folder>/build. Then configure using these commands:

cd <build-folder>
cmake -DCMAKE_BUILD_TYPE=Debug -DLLVM_DIR=<llvm-install-folder>/lib/cmake/llvm <cecko-folder>

The -DLLVM_DIR option is usually not required if LLVM was installed as a system package.

Building is then done by invoking cmake --build . or make in <build-folder>.

The resulting executables are located in <build-folder>/stud-main and invoked like:

cd <build-folder>
<build-folder>/stud-main/cecko1 <cecko-folder>/test/test1.c

Visual Studio 2022

Open the <cecko-folder> with Visual Studio.

When opened for the first time, use PROJECT/CMake Settings to adjust the cmake configuration, the LLVM_DIR variable in particular (see Prerequisites). The default x64-Debug configuration is created automatically; to use WSL, add the WSL-GCC-Debug configuration, adjust it if necessary and switch to it.

See also the related Visual Studio Documentation.

Visual Studio Code

In Windows, install the Visual C++ compiler first. Then start an x64 Developer Command Prompt (which defines the environment where the compiler is visible), then run code from the command prompt. Then follow the documentation for the CMake Tools extension.

Running

Command-line

The resulting executables are located in <build-folder>/stud-main and invoked like:

cd <build-folder>
<build-folder>/stud-main/cecko1 <cecko-folder>/test/test1.c

Visual Studio 2022

Open DEBUG -> Debug and Launch Settings for … (launch.vs.json) and add the following settings into the x64 configuration(s) in use:

"currentDir": ".",
"args": [ "test\\test1.c" ]

For WSL configuration(s), use:

"cwd": ".",
"args": [ "test/test1.c" ]

For remote Linux configuration(s), adjust remoteCMakeListsRoot in CMakeSettings.json so that it does not use the $HOME variable, then use:

"cwd": "${cmake.remoteCMakeListsRoot}",
"args": [ "test/test1.c" ]

Note that WSL and remote Linux use the same debug config ("type": "cppgdb"); therefore, there is probably no setting that works simultaneously in both cases.

See also the related Visual Studio Documentation.

Visual Studio Code

T.B.D.

Links

We have gathered several links to materials that are closely related to the subject. If you detect broken links or you wish to share a good link with your fellow students, please contact the teachers.

A free online textbook by Douglas Thain

Douglas Thain: Introduction to Compilers and Language Design, 2nd edition, 2020, ISBN 979-8-655-18026-0

• www3.nd.edu/~dthain/compilerbook

The Dragon Book

Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compilers: Principles, Techniques, and Tools (2nd Edition), Addison Wesley, 2006, ISBN 978-0321486813

• Dragon Book supplement page
• Dragon Book on Amazon

Manuals for the tools

• Flex manual ( manually generated for the latest version )
• Bison manual ( manually generated for the latest version )

Recordings of lectures

• Old recordings of lectures (2020, only Czech, use anything@cuni.cz to sign in)