(Winter  2018, 9:30-10:45am,  MS 217)

Lecturer: Robin Cockett (ICT 652)


Who should take this course? 

Have you ever wondered how a compiler works?  This course is an introduction to compiler construction which concentrates on the front-end issues: parsing, generating the appropriate internal data structures (abstract syntax tree), and basic "ad hoc" code generation.   The problem of parsing input led to some of the earliest theoretical developments in computer science: the theory of regular and context free languages.  The parsing algorithms which resulted for context  free languages are useful far beyond the specific task of generating a compiler.  These techniques provide the basis for the front-end of almost all major systems.  Modern compilers and other systems use software tools for facilitating the construction of these front-ends.  The course will introduce the basic tools of Lex and Yacc and end by building a compiler (to stack machine code or -- possibly -- an ARM emulator) for a  simple language.

This course is centered round the organization of the "front-end" of a compiler.   The "back-end" issues (code optimization, dataflow analysis, instruction selection, register allocation etc.) will only be briefly discussed in this course -- they are the main subject of the follow on course  510/611.  

LECTURE NOTES (as they become available):

  1. Introduction to compilers
  2.  Grammars and parse trees
  3.   Recursive descent parsing  .... here is a simple expression parser as a Haskell program.
  4.    Recursive descent grammars
  5.    Introduction to LL(1) parsing
  6.     LL(1) grammars
  7.      Grammar transformation
  8.       Regular languages
  9.       (Guest lecture by John Aycock) LR(0) grammars
  10.        LR(1) grammars
  11.         LALR(1) grammars (LALR(1) follow sets)
  12.           Runtime organization and AM
  13.            Symbol table
  14.              Plumbing diagrams  (Haskell examples for typing pure expressions here, for let-expressions here)


Assignments may be written in a language of your choice.  The choice must be discussed and agreed upon with your TA.  The language you  choose must support LEX and YACC (an LALR(1) parser generator tool).  Your assignment marks will depend on

The main language of instruction will be the functional programming language Haskell.  Discussion of comparison between implementation techniques in different paradigms will take place in the labs and students are encouraged to share their observations.  Here are some possible languages and the available tools:


Assignments for 2017:
  1. Due January 26: Using lex here (3%)
  2. Due February 16: Recursive descent parsing and generating basic stack code here (10%)
  3. Due March 20: Using Lex and Yacc here (7%)
  4. Due April 4: Symbol table and semantic analysis here (10%).
  5. Due April (end of classes): Stack based code generation here (10%).


  1. March 8: Midterm  (25%) past exams are here:  this is mostly on context free languages (if you have not done so already check out the Context Free Grammar Checker).
  2. April: Final  (35%) past exams are here.

Please find the tutorial notes here ....


Late policy: for each 24 hours late the maximum mark you can obtain will be reduced by 20%.   After two working days we will not accept a late submissions.

Cheating: Any cases will automatically receive the following treatment :

My main concern is that you should be learning in this class: if you are cheating you are not learning!  Furthermore, you may be setting an unfortunate trend for your future work habits. I regard it as an integral part of my job, as a teacher, to ensure that you approach your work with the right attitude and will muster all the resources at my disposal to achieve this.

When you hand in work to be graded you are saying that it is your work. For programs this means that you typed in the program, developed it, and debugged it yourself.   If you use routines from a book or another source you must clearly document your source.  Furthermore, before handing in some code, you should spend a moment to consider how you had arrived at that code.  If you realize that some of the code which should have been yours is not then this is the time to come and talk to me or the TA before you get into trouble.   This allows us to apportion credit appropriately.

Discuss the course material!  I strongly encourage you to discuss all aspect of the course material!  Form study groups for the exams.   Your peers are probably your best learning resource.  When you discuss programming projects do so "off line" and away from the terminals: a good idea is to do so on a blackboard which you clean carefully after the discussion.   The golden rule is: after you have finished such a discussion you must walk away only with what is in your head!

See the honest in academics website here.

Enjoy the course.


  1. (Required) Compiler construction: principles and practice.  K.C. Louden.
  2. (Recommended - and a useful book) Lex & Yacc. J.R. Levine, T. Mason, D. Brown.
  3. (Recommended) Compilers: principles techniques, and tools.  Aho, Sethi, Ullman.