Lecturer: Robin Cockett

Notes 2010

COURSE OUTLINE:

• Overview of the tasks of a compiler: lexical analysis, parsing, semantic analysis, code generation.
• Lexical analysis: regular languages and automata
• Context free grammars: LL(n), LR(n),  LALR(1).
• Attribute grammars: inherited and synthesized attributes, circularity.
• Compiling to a stack machine.

This course is a prerequisite for the main compiler course: CPSC610: Compiler Code Generation and Optimization.  This course is centered round the optimizations which are performed in the "back-end" of a compiler and a project in which one builds a significant component of a compiler/system.  

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.        LR(1) grammars
10.         LALR(1) grammars (LALR(1) follow sets)
11.           Runtime organization and AM
12.            Symbol table
    
13.             Plumbing diagrams

ASSIGNMENTS:

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

• on correctness and completeness of your code;
• clear succinct documentation;
• your coding techniques;
  
• your performance on test examples and the test examples you provide.

1. Due January 27: Using lex  here (3%)
   
2. Due Febuary 24: Recursive descent parsing and generating basic stack code here (10%)
3. Due March 17: Using Lex and Yacc  (description of project here with the extended version here: tests here) (7%)
   
4. Due April 7: Symbol table and semantic analysis (the description of the intermediate representation is here: tests here) (10%).
5. Due April 14: Stack based code generation (the description of the AM machine is here) (10%).

Past assignments  here.

EXAMS:

1. March: 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:

• Cheng Xu, Thomas Burt notes for 2010 here.
  
• Andrew Kuiper's notes for 2009 here.
  
• David Aikema's notes for 2008 here.
• Ning Tangs notes for 2007 here.
  
• Karel Bermannn's notes for 2008 here.
• Brett Giles's notes for 2003 here - mostly Python.

 
POLICIES:

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

Cheating: Any cases will automatically receive the following treatment :

• [First offense:] You will receive a letter notifying you that you were involved in such behavior.   This letter will be kept in your file for the remainder of your stay at the university.
• [Second offense:] You will be subject to disciplinary action: usually removal from your program.

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.
 

TEXT

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.

PARSING LINKS:

• A web based tool for investigating context free grammars (developed by Mike Burrell a former CPSC411 student!).   It allows you to: transform grammars into LL(1) (when possible) to look at LL(1),  LR(0), SLR(1), LALR(1), and LR(1) parsing tables and automata.  It also has examples of context free grammars belonging to most of the different classes considered in the course.
• A downloadable tool for (Early) parsing called Kakuy  (it is free and for windows platforms).
• Practical guide to parsing by Dick Grune and Ceriel Jacobs.
• Essays by F.D. Lewis on Recursive descent , top-down parsing, and building a top down parser. and bottom up parsers.  These are simple overviews of these parsing ideas.
• Java versions of Lex and Yacc the Java CUP systems.
• A catalog of lexer and parser generators.
• The ANTLR system: ANother Tool for Language Recognition which has become very popular recently: it uses LL(k) grammars.
• Yapps is a python based parser generator.
• Dr. Seuss on Parser Monads: well some good fun for those who are interested in functional languages.
• Happy a parser generator for Haskell.

• The Haskell webpage.
• Yet another nice tutorial on Haskell by Hal Daume (recommended by Karel).