Compiler Construction
- Slides
- Our SLANG Compiler
- OCaml source code can be found at GitHub: https://github.com/Timothy-G-Griffin/cc_cl_cam_ac_uk.
- I hope some students will attempt to implement some of these extensions/modifications to the compiler : practical.txt.
- J.W's proposed x86 fix to my READ command. Or should we change the definition of read in c_runtime.c to return an int, rather than an int64? Reminder : details of x86 are not examinable.
- Supervision Suggestions. Supervisors are strongly encouraged to
assign some practical work.
- (1) Lexing and parsing.
- My problem sheet : exercises.pdf NOTE: this exercise sheet contains NEW REVISION material, so please alert me to typos and mistakes.
- From Introduction to compiler design: Read Chapters 2 and 3 and do as many of the associated exercises as possible. Yes, solutions are available online, but don't peek before attempting on your own.
- Some past tripos questions on similar topics:
- (2) Program transformations.
- (3) A few past tripos questions:
- (1) Lexing and parsing.
- Recommended online book :
Mogensen, T. (2011). Introduction to compiler design. http://www.diku.dk/~torbenm/Basics.
Additional Resources
Here are some optional materials that you may want to explore.
- Fun links from Matthew
- A website that allows you to enter code in many languages and see compiler output from many compilers. https://godbolt.org.
- A site for kernel development with a lot of info about compilers. https://wiki.osdev.org.
- Parsing
- Parsing Expression Grammars (PEG)
- Python syntax (using a custom PEG)
- ANTLR
- Yacc is Dead
- Long Live Yacc
- Rust Language parsing/syntax debate (Thanks to Shaun Steenkamp)
- Ocaml Resources
- The offcial site : https://ocaml.org
- Try OCaml! : http://try.ocamlpro.com
- Side-by-side comparison of SML and OCaml syntax : http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html
- ocamlbuild is very useful for small projects like our interpreters and compilers. No Makefile required! http://caml.inria.fr/pub/docs/manual-ocaml-4.00/manual032.html
- OCaml Labs : http://www.cl.cam.ac.uk/projects/ocamllabs
- New Book: https://realworldocaml.org/v1/en/html/index.html
- OCaml virtual machine.
- Introduction to X86-64 Assembly for Compiler Writers
- General Concepts
- Compiler : http://en.wikipedia.org/wiki/Compiler
- Interpreter : http://en.wikipedia.org/wiki/Interpreter_(computing)
- Virtual Machine: http://en.wikipedia.org/wiki/Virtual_machine
- Just In Time (JIT) compilation : http://en.wikipedia.org/wiki/Just-in-time_compilation
- Continuation Passing Style :
- Euan's proof of correctness for CPS of gcd using the LEAN theorem prover can be found here.
- http://en.wikipedia.org/wiki/Continuation-passing_style
- CPS and JavaScript
- Continuation-Passing Style: and why JavaScript developers might be interested in it: http://marijnhaverbeke.nl/cps>/li>
- CPS and tail-call emimination in JavaScript : http://www.eriwen.com/javascript/cps-tail-call-elimination
- CPS by example: http://matt.might.net/articles/by-example-continuation-passing-style
- Asynchronous Programming and Continuation-passing Style in JavaScript : http://css.dzone.com/articles/asynchronous-programming-and
- Abstract Machines. My derivations of stack machines using CPS and defunctionalisation are very much inspired by the following papers.
- Mitchell Wand. Deriving Target Code as a Representation of Continuation Semantics. ACM Transactions on Programming Languages and Systems, 4(3):496-517, July 1982.
- Definitional interpreters for higher-order programming languages (1972). John C. Reynolds
- Olivier Danvy and Lasse R. Nielsen. Defunctionalization at Work. June 2001.
- : Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard. From Interpreter to Compiler and Virtual Machine: A Functional Derivation.March 2003.
- : Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard.A Functional Correspondence between Evaluators and Abstract Machines.March 2003.
- Virtual Machines
- JVM
- http://jasmin.sourceforge.net/ : Jasmin is a JVM bytecode assembler, taking an ASCII foo.j file to a binary foo.class file.
- http://www.angelfire.com/tx4/cus/jasper/ : Jasper is a JVM bytecode disassembler, taking a binary foo.class file to an ASCII foo.j file in the Jasmin syntax. Note that the javap dissassembler also prodoces ASCII. However, there does not seem to be an associated assembler (please correct me if I'm wrong).
- https://github.com/Storyyeller/Krakatau : Krakatau. A JVM bytecode assembler/dissassembler.
- http://commons.apache.org/proper/commons-bcel : BCEL. The Byte Code Engineering Library provides ways to analyze, create, and manipulate (binary) Java class files (those ending with .class).
- Compiling other languages to the JVM
- http://www.dcs.ed.ac.uk/home/mlj : MLj compiles SML to JVM bytecode.
- Ocaml VM
- http://ocsigen.org/js_of_ocaml : js_of_ocaml. A OCaml bytecode to javascript converter. See this paper for a detailed description.
- https://github.com/nojb/ocaml-c0 : A C0 to Ocaml bytecode compiler, witten in Ocaml.
- HLVM : http://www.ffconsultancy.com/ocaml/hlvm
- Memory Management (AKA Garbage Collection)
- Selected Open-Source Compilers
- LLVM toolkit http://llvm.org/
- JAVA
- http://openjdk.java.net : OpenJDK.
- http://jikes.sourceforge.net : Jikes. IBM
- SML
- http://mosml.org : Moscow ML.
- http://www.polyml.org/ : Poly ML.
- http://www.smlnj.org/ : Standard ML of NJ.
- http://www.mlton.org/ : MLton.
- https://github.com/melsman/mlkit : MLKit
- OCaml
- Idris http://www.idris-lang.org : Idris is a new experimental language with a dependent type system.
- whitespace! http://compsoc.dur.ac.uk/whitespace
- Verified Compilers. An interesting area of much recent work.
See motivation herehttp://gallium.inria.fr/~xleroy/courses/VTSA-2013/.
- CompCert : http://compcert.inria.fr CakeML : https://cakeml.org/