Lecturer: Robin Cockett (ICT 652)

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 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:

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

• 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 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%).

EXAMS:

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 ....

 
POLICIES:

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 :

• [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).
• "A Practical Guide to Parsing" by Dick Grune and Ceriel Jacobs (search on web!).
• 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.
• 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.
• Alex and Happy  parser generator, Parsec, BNFC and BNFC-meta (for Haskell).
  

• The Haskell webpage.
• Beginners' guide to Haskell: "Learn you a Haskell for Great Good".
  
• On the future of programming here.