/compiler-course-unipi

Lab of the course Languages, Compilers and Interpreters (Cod. 653AA) @ UNIPI

Primary LanguageOCaml

Languages, Compilers and Interpreters (Lab) - 3 CFU

Teacher: Letterio Galletta

Contact: name.surname(at)imtlucca.it

Office hours: contact me by e-mail

Page of theory part of the course held by Prof. Roberta Gori: http://pages.di.unipi.it/gori/Linguaggi-Compilatori2020/

Course description

The course will present tools and techniques used in the implementation of programming languages. In particular, the course will guide students in the implementation of a compiler for a small subset of language C, called MicroC, and of an interpreter of a small functional language, called FUN. During the lectures students will work on programming assignments covering different aspects of language implementation. The programming language adopted for the exercises and the project is OCaml. At the end of the course students who completed all the assignments will have developed an simple interpreter and a compiler.

Learning objectives

After completing the course, students will have

  • Known the basics of the functional programming language OCaml;
  • Implemented parsers using state-of-the-art parsers generators;
  • Designed and implemented semantic analyses for a functional and an imperative languages;
  • Used the LLVM toolchain for generating and optimize code;
  • Had some fun along the way! 😄

Program of the course

  • Introduction to functional programming and to OCaml language;
  • Lexing and parsing using ocamllex and menhir;
  • Semantic analysis implementation: type checking, scope management, control-flow analysis;
  • Introduction to LLVM infrastructure and LLVM intermediate language;
  • Code generation.

Lectures

This table specifies the lecture schedule with topics and materials.

See these instructions to set up your programming environment.

Date Topics Slides Examples Assignments
9/25 Intro to OCaml: functions, string
REPL, compilation		 Intro to the lab
OCaml Tutorial
OCaml Tools		 ocaml-basics.ml Exercises 1
10/2 Intro to OCaml: lists, tuples, records,
algebraic data types, pattern matching		 OCaml Tutorial ocaml-basics.ml Exercises 2
10/9 - Intro to OCaml: module, imperative features.
- The interpreter of FUN		 OCaml Tutorial
The interpreter of FUN		 vector.mli
vector.ml
fun.ml		 Exercises 3
10/15 - Discussion on previous programming assignments
- Introduction to lexing with ocamllex		 Lexing with ocamllex - -
10/23 Tutorial on ocamllex Lexing with ocamllex cwd.mll
count.mll
count_fun.mll
stokens.mll
stokens_pos.mll
comments.mll
csv_simple.mll
toy_lang.mll		 Exercises 4
10/30 Tutorial on menhir Syntactic analysis with menhir calc
calc-alias
calc-ast
calc-ast-pos
calc-two
calc-multi
calc-incremental
json		 Exercise 5
11/06 - Parsing with menhir
- Discussion on previous programming assignments
- Presentation of MicroC project		 Syntactic analysis with menhir
Introduction to MicroC		 FUN parser solutions of exercises 4.5 & 5.4
IoT-Lysa parser for an example of parser using FParsec		 MicroC parser
11/13 Type analysis Type analysis FUN type checker
Incremental MinCaml
CADL		 Exercises 6
11/20 Control-flow analysis CFA analysis FUN CFA analysis Exercises 7
11/27 Semantic analysis for MicroC Semantic analysis for MicroC - MicroC analyzer
12/04 Introduction to LLVM LLVM Infrastructure empty-module.ll
add.c
add.ll
main.c
fun-decl.ll
global-local.ll
local-vars.ll
arithmetic.ll
conditional.ll
phi-instruction.ll
call.ll
array-struct.ll
gep.c
gep.ll
deps.ll		 Exercises 8
12/11 LLVM Code generation Generating LLVM IR Code from OCaml array_access.ml
call_ext_fun.ml
empty_module_bitcode.ml
empty_module.ml
fun_abs.ml
fun_abs_phi.ml
fun_body_void.ml
fun_def_void.ml
fun_equals.ml
fun_params.ml
fun_sum.ml
global_variables.ml
local_variables.ml
Simple Compiler for FUN		 MicroC code generator

Final project

The final project of the course consists in implementing a compiler for MicroC. See here for the instructions.

Material

Software

Programming assignments will use the following pieces of sotfware:

  • OCaml - try to install the latest version. All the code shown during the course is tested with the version 4.10.1.
  • Opam - OCaml package manager.
  • Menhir - a LR(1) parser generator for the OCaml programming language.
  • Clang - a compiler for C programs.
  • LLVM - The LLVM compiler infrastructure. All the code shown during the course is tested with the version 10.0.
  • rlwrap - a small utility to improve the editing capability of the OCaml REPL.

Online Resources

Further resources

Here you find a list of further references that complete and deepen the various topics covered during the course. A rich collection of articles related to the course can be found in Prof. Matt Might's blog.