Course pages 2019–20

Compiler Construction

Last changes: Last changes: Wed Feb 26 16:10:40 GMT 2020 (fixed some questions in exercises.pdf).

Fri Feb 21 11:35:25 GMT 2020 (added fixes to lecture 16 slides and one more tweak to lecture 15 slides).

Fri Feb 21 09:55:57 GMT 2020 (added exercises for lexing and parsing).

Thu Feb 20 13:31:24 GMT 2020 (added lecture 16 slides).

Wed Feb 19 11:16:21 GMT 2020 (added lecture 15 corrections).

Tue Feb 18 17:21:36 GMT 2020 (added Lecture 15 slides, lecture 14 corrections).

Fri Feb 14 14:45:15 GMT 2020 (added Lecture 14 slides).

Fri Feb 14 11:24:07 GMT 2020 (added Lecture 13 slides with corrections).

• Slides
• Lectures 1 -- 12.
• Compiler_Construction_1_12_2020_2up.pdf (two slides per page)
• Compiler_Construction_1_12_2019.pdf (one slide per page)
• Lectures 13 -- 16 (Lexing, Parsing). Thanks to all for helping me debug these new slides!
• CC_2020_Lexing.pdf with these corrections:
• Slide 2: added Sigma base case!
• Slide 6: fixed definition of nondeterministic transition starting with an epsilon move.
• Slide 19: Condition (2) corrected.
• Slide 23: Cleaned up explanation.
• Lecture 14: CC_2020_ParsingI.pdf with these corrections:
• Slide 16: eliminate bogus first step of the computation
• Lecture 15: CC_2020_ParsingII.pdf with these corrections:
• Add slide numbers where missing
• Slide 8 : clarify definition of FIRST (AGAIN on 21 Feb!)
• Slide 10: The two instances of "FIRST(A)" should be "FIRST(alpha)"
• Slide 18: On line 5 the {a} should be {epsilon}. Also, in first line of while loop, subtract {epsilon} from FIRST(X_j).
• Slide 20: Fix grammar definition.
• Slide 22: New slide to give definition of "FIRST(alpha)".
• Lecture 16: CC_2020_ParsingIII.pdf with these corrections:
• Slide 13: On last line change NFA to DFA.
• Recommended online book :
  Mogensen, T. (2011). Introduction to compiler design. http://www.diku.dk/~torbenm/Basics.
• Our Slang Compiler
• OCaml source code can be found at GitHub: https://github.com/Timothy-G-Griffin/cc_cl_cam_ac_uk.
• On 24/01/20 I updated this file expr_machine.ml.
• I hope some students will attempt to implement some of these extensions/modifications to the compiler : practical.txt.
• 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.
• Supervision Suggestions. Supervisors are strongly encouraged to assign some practical work.
  • (1) Lexing and parsing.
    • My problem sheet : exercises.pdf (added 21 Feb, fixed on 26 Feb)
    • 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:
      • y2015p3q3
      • y2012p3q4, (a), (b)
  • (2) Program transformations.
    • Review basic transformations.
    • exercieses_cps.ml
    • y2017p23q4
  • (3) A few past tripos questions:
    • y2018p4q3
    • y2018p4q4
    • y2017p23q3

Additional Resources

Here are some optional materials that you may want to explore.

• 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 :
  • 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
• 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
• https://ocaml.org
• 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/