Objectives and outcomes
The aim is to teach students about the techniques of conversion from one programming language to
another, as well as about the principles of compilers, the tools for their creation, and their
implementation. Moreover, students understand compilers which are the main tools in the development
of computer programs. Students can design a compiler.
Lectures
The origins of the higher programming languages and compilers. Compilers classification. Compilers
evaluation. Current challenges in the development of compilers. Compiler infrastructures (GCC, LLVM).
Theory of formal languages (grammar, Chomsky’s hierarchy). Lexical analysis (basic scanning algorithm,
basic dilemmas, regular expressions, non-deterministic and deterministic finite automata, tabular
implementation of finite automata). Semantic analysis (context-free grammars, ambiguity and how to
overcome it, parsing errors and how to approach them, abstract syntax tree, recursive descending
parsing, left recursion and how to overcome it, predictive parsing, LL1 table, ascending parsing).
Semantic analysis (scope, symbol table, type environment, method type, static and dynamic type
control). Code generation (execution organisation, activation record, allocation, alignment, machine
stack, MIPS architecture). Fundamentals of code optimisation (evaluation rules, intermediate code, base
block, flow control graph, local and global optimisation).
Practical classes
Parsing strings in C and Python. Regular languages, practising the writing of regular expressions.
Coding a simple interpreter for C in Python. Lexical analysis and token recognition. Implementation of a
finite automaton for a specific context-independent grammar. Parsing mathematical expressions using
appropriate context-independent grammar. Generating an abstract syntax tree. Implementation of simple
elements of the C language: functions, libraries, declarations, if-structure, while-structure, for-structure.
Implementation of semantic analysis. Introduction to the LLVM environment.