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-Compilatori2022/

Course description

The course will present tools and techniques used in the implementation of programming languages. 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 and the project 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
10/03	Intro to OCaml	Intro to the lab OCaml Tutorial OCaml Tools	ocaml-basics.ml OCaml Programming Problems	Exercises 1
10/10	- Intro to OCaml: records, algebraic data types module, imperative features - The interpreter of FUN	OCaml Tutorial The interpreter of FUN	ocaml-basics.ml vector.mli vector.ml fun.ml	Exercises 2 Exercises 3
10/17	Introduction to lexing with 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/24	- Parsing with menhir - Presentation of MicroC project	Syntactic analysis with menhir Introduction to MicrocC	calc calc-alias calc-ast calc-ast-pos calc-two calc-multi calc-incremental json FUN parser solutions of exercises 4.5 & 5.4 IoT-Lysa parser as an example of parser using FParsec MinCaml parser as an example of parser using ocamlyacc FrontC as an example of a menhir parser for a real language Solidity-parser for an example of a menhir parser for a real language	Exercise 5 MicroC parser
10/31	No Lecture	-	-	-
11/07	- Type analysis	Type analysis	FUN type checker MinCaml Incremental MinCaml CADL Grow Your Own Type System The PL Zoo	Exercises 6
11/14	-Discussion on previous assignments - Control-flow analysis	CFA analysis	FUN CFA analysis A toy static analysis tool based on the monotone dataflow analysis framework VSA a framework for Value-Set Analysis EthCA Ethereum Concurrency Analyzer	Exercises 7
11/21	- Control-flow analysis - MicroC Semantic analysis	CFA analysis MicroC Semantic analysis	-	MicroC semantic analysis
12/02	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/05	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 software:

• OCaml - try to install the latest version. All the code shown during the course is tested with the version 4.14.0.
• 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 14.0.
• rlwrap - a small utility to improve the editing capability of the OCaml REPL.
• utop - an improved toplevel (i.e., Read-Eval-Print Loop) for OCaml.

Online Resources

• OCaml API
• OCaml user manual
• OCaml Discourse the community forum
• OCamlverse an attempt to documenting everything about OCaml
• The book OCaml Programming: Correct + Efficient + Beautiful
• The book Real World OCaml
• The book OCaml Scientific Computing
• OCaml MOOC
• The videos of the book OCaml Programming: Correct + Efficient + Beautiful
• An interactive tutorial on using git
• LLVM Language Reference Manual
• LLVM OCaml Binding Documentation
• Kaleidoscope: Implementing a Language with LLVM in Objective Caml
• Mapping High Level Constructs to LLVM IR
• The Programming Languages Zoo - A potpourri of programming languages
• Compiler Explorer
• Resources for Amateur Compiler Writers
• CompilerJobs a list of compiler, language and runtime teams for people looking for jobs in this area.

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.