COMP 520 - Compilers http://www.cs.unc.edu/~prins/Classes/520/ Spring 2013 (Tue Jan 10 - Thu Apr 25) TTh 12:30 - 1:45 PM, SN 014 Instructor: Jan Prins FB 334, Tel: 962-1913, prins@cs.unc.edu Office hours: Wed 3-4PM (and by appointment) TA: Shrey Banga SN 373, Tel: 919-448-8780, banga@cs.unc.edu Office hours: Tue 3:00 - 4:30 PM

Overview

• Understand the theory and practice of compilers, interpreters, assemblers, linkers, and loaders, and be able to work effectively with such programs.
• Be able to design and implement parsers and language translators for simple languages.
• Appreciate the effects of decisions in programming language and computer architecture design on the translation process and run-time systems.
• Have experience with the design and implementation of large and complex programs using Java.
• Retain knowledge of compilation and interpretation techniques in preparation for advanced courses in compilers and/or comprehensive computer science studies.

Prerequisites

Text

Course overview

• Midterm exam will be given in-class Tue Mar 5. Open book/notes. No computers.
• This course will use Piazza to manage class questions and discussions online.
  • Please join our discussion group using this link: https://piazza.com/unc/spring2013/comp520
  • Please access the discussion group using this link: https://piazza.com/unc/spring2013/comp520/home

Reading Assignments

• (for Thu Feb 28) PLPJ Read Chapter 5 - Triangle Contextual Analysis case study - section 5.4 (pp 163 - 169)
• (for Tue Feb 26) PLPJ Read Chapter 5 - Implementation of contextual analysis - section 5.3 (pp 153 - 163)
• (for Thu Feb 21) PLPJ Read Chapter 5 - Type checking - section 5.2 (pp 150 - 153)
• (for Thu Feb 14) Chapter 5 - Contextual analysis - section 5.1 (pp 136 - 150)
• (for Tue Feb 5) PLPJ Chapter 4 - Abstract Syntax Trees, Secn 4.4 (pp 109 - 118).
• (for Thu Jan 31) No new reading assignment.
• (for Tue Jan 29) PLPJ Chapter 4 - Scanning, Secn 4.5 (pp 118 - 124) (we will return to Secn 4.4 AST)
• (for Thu Jan 24) PLPJ Chapter 4 - Systematic Development of RD Parsers (4.3.4) (pp 93 - 109)
• (for Tue Jan 22) PLPJ Chapter 4 - Parsing (4.3) [pp 83 - 84]
  Top-Down Parsing (4.3.2), Recursive Descent Parsing (4.3.3) [pp 87 - 93]
• (for Thu Jan 17) PLPJ Skim Chapter 3 - Organization of Compilers and Compilation (pp 55 - 70).
  We will come back to Chapter 2 later.
  Start reading Chapter 4 - Grammars, Secns 4.1 - 4.2 (pp 73 - 83)
• (for Tue Jan 15) PLPJ Read Chapter 1 - Introduction (pp 1 - 25).

Lecture Notes

• Index of Lecture Slides.

• Short written assignment WA1 assigned Thu Jan 10, due Tue Jan 15.
• Short written assignment WA2 assigned Jan 22, due Jan 29 (extended to Jan 31)
  WA2 sample solutions. Additional detail on computing Nullable, First, and Follow sets (for a different problem) can be found in this grammar analysis example.
• Short written assignment WA3 assigned Feb 21, due Feb 28.
  WA3 sample solutions.

Programming Assignments

• Compiler project assignment PA1 assigned Tue Jan 1, due Thu Jan 31.
  • Submission instructions
  • Simple PA1 test program
  • PA1 tests (zipped)
  • Checkpoint 1 regression tester. For instructions, see the reference section below.

• Compiler project assignment PA2 (complete) assigned Thu Jan 31, due Tue Feb 19.
  • Submission instructions.
  • miniJava AST classes in zip file
  • Simple PA2 test program
  • PA2 tests (zipped)
  • Checkpoint 2 regression tester. For instructions to run the tester, see the reference section below.

• Compiler project assignment PA3 (complete) assigned Tue Feb 19, due Mar 21.
  • Simple PA3 test program

Examples

• A very simple expression parser with single character terminals, parsing expressions over +, * and integer literals 0-9.
• An improved expression parser with scanner that illustrates the Parser, Scanner, and Token classes. By including a scanner, we can now parse expressions with multidigit numbers and white space e.g. "12 * 7 - 83".
• A grammar analysis example.
• An simple example of the SimpleScannerParser adapted to have the package structure required for your compiler
• Arithmetic expression evaluator implementing a scanner, operator precedence parser, AST construction, display, and evaluation.
• Arithmetic expression evaluator using visitor pattern with same capability as previous example, but using visitor classes for AST traversal and organized into nested packages

Reference Section

Textbook

• Text Errata and access to the Triangle compiler sources

Java Reference

• Java Language Specification, 3rd edn. also available in PDF.
• Java Platform Standard Edition Release 6 documentation

Additional references

• The MIPS instruction set is summarized in section A.10 from Appendix A of Hennessy and Patterson, Computer Organization and Design: The Hardware/Software Interface.
• The Java Virtual Machine (JVM)

MiniJava Project tester

• Each checkpoint in the compiler project will be evaluated by a series of tests.
• You can run the tests from past checkpoints in Eclipse to check that you have fixed errors. Note that earlier tests may not be valid later in the project.
• Instructions to install the tester
  1. Create a new package called tester within your miniJava project. So the tester package sits next to your miniJava package, and not in your miniJava package.
  2. Create a new project (so not a Java project) called tests in your Eclipse workspace (so tests and your miniJava project are completely separate projects).
• Instructions to use the tester
  1. Import or copy a checkpoint tester, e.g. Checkpoint1.java, into the tester package.
  2. Import the matching folder of tests, e.g. pa1_tests, into the the tests project.
  3. Run the tests, e.g. run Checkpoint1. It will apply all tests and show you a report of their outcome.

Triangle compiler

• Instructions for installing and running the Triangle compiler tools in Linux.
  1. Make sure you have a working java runtime and compiler with the following commands:
     which java -- this should be /usr/bin/java
     java -version -- this should be 1.7 currently
     javac -version -- this should be 1.7 currently
     If you encounter problems check that /usr/bin is on your PATH.
  2. Install the TriangleTools directory:
     curl "http://www.cs.unc.edu/~prins/Classes/520/Examples/TriangleTools.tgz" | tar -xz
  3. Change into the TriangleTools directory and compile the Triangle language tools:
     cd TriangleTools
     javac Triangle/Compiler.java
     javac TAM/Interpreter.java
     javac TAM/Disassember.java
  4. Run the Triangle compiler on a sample input program p1.tri:
     java Triangle/Compiler p1.tri
  5. Run the interpreter on the object code generated in file obj.tam:
     java TAM/Interpreter obj.tam
  6. Run the disassembler on the object code generated in file obj.tam:
     java TAM/Disassembler obj.tam

• Instructions for installing and running the Triangle compiler using Eclipse
  1. In Eclipse, select the Java perspective and create a new Java project TriangleTools (File/New/Java Project, enter "TriangleTools" in the Project Name, important: choose "Use project folder as root for sources and class files" and select "Finish").
  2. Import the jar file TriangleTools.jar into the project (File/Import/General/Archive, browse to the jar file, verify the project it will be imported into is "TriangleTools", and select "Finish").
  3. Create run configurations in the project for the three Java Applications: Triangle.Compiler, TAM.Interpreter, and TAM.Disassembler (Run/Run Configurations ... then create three new instances of a run configuration for a Java Application, each with the appropriate main. Edit the run configuration for the Triangle compiler to include argument "p1.tri").
  4. Run the configurations in order: compiler, interpreter, and disassembler.