Introduction to Compilers

ECEN 4553 & 5013
CSCI 4555 & 5525
Fall 2008

Course Information

High-level programming languages like Python make programming a breeze, but how do they work? There's a big gap between Python and machine instructions for modern computers. Learn how to translate Python programs all the way to Intel x86 assembly language with a pit stop at C along the way.

Most compiler courses teach one phase of the compiler at a time, such as parsing, semantic analysis, and register allocation. The problem with that approach is it is difficult to understand how the whole compiler fits together and why each phase is designed the way it is. Instead, each week we implement a successively larger subset of the Python language. The very first subset is a tiny language of arithmetic expressions, and by the time we are done the language includes objects, inheritance, and first-class functions.

Prerequisites: Fluency in at least one programming language (Java, C, C++, Python, etc.). Students will do a lot of programming in Python, but prior knowledge of Python is not required. The course will start with a crash course on Python and Python is one of the easiest languages to learn. A familiarity with the C programming language is needed or a willingness to learn it quickly on your own. Prior knowledge of an assembly language helps, but is not required.

Distance Learning: This course is also offered through the CAETE program.

Time: MWF 11:00am-11:50am

Location: ECCS 1B28 (was ECCS 1B14)

Office hours: Thursday 1:00pm-2:00pm

Textbook: None.

Recommended books:


Grading: homework 10%, weekly quizzes 40%, midterm exam 20%, final exam 30%.

Workload: up to 9 hours of out-of-class work per week.

Policies regarding honor code, religious observances, disabilities, and classroom behavior can be found here.

Homework and quizzes for distance students (CAETE): Because there is a short delay in when you can watch the videos of the class, homeworks are due two days after the posted date. The questions for quiz will be emailed to you on the morning of the posted date of the quiz and you will email the answers back to Jeremy by midnight of the same day. The quizzes are closed book and should be completed alone, just use your brain and only use the computer to type in your answers. For example, do not use the Python interpreter on your computer to help you answer the quiz.

Assignments:

  1. Integer expressions and ASTs [pdf], due 9/5. Solution: hw1.py. Tests for P0: test_p0.tar
  2. Parsing with PLY (Python Lex-Yacc) [pdf], due 9/12. Solution: hw2.py.
  3. Floats, bools, and polymorphism [pdf], due 9/19. Solution: hw3.py. Tests for P1: test_p1.tar
  4. Type analysis and specialization [pdf], due 9/26. Solution: hw4.py.
  5. (a) Variables, control flow, and iterative type analysis [pdf], due 10/3. Solution: hw5.py. Tests: teste_p2.tar.
    (b) Static single-assignment (SSA) form [pdf], due 10/10.
    Part (b) is required for graduate students and extra credit for undergraduates. For the solution to (b), see the solution to hw 6.
  6. Lists, dictionaries, and heap allocation [pdf], due 10/10. Solution: hw6.py. Tests: test_p3.tar.
  7. Functions and closure conversion (part 1) [pdf], due 10/17. Tests: test_p4.tar.
    Functions and closure conversion (part 2) [pdf], due 10/24. Jay's solution, Dan's solution, Jeremy's solution (submit as assignment 8)
  8. Objects and classes [pdf], due 11/10. Tests: test_p5.tar. Moss's solution, Jay's solution, Jeremy's solution (submit as assignment 9)
  9. First steps toward x86 [pdf], due 11/17. Reading assignment: Intro to the x86 machine. Jeremy's solution (submit as assignment 10)
  10. Removing structured control flow and 3-operand statements [pdf], due 12/1 (submit as assignment 11)
  11. Function calling conventions and the stack [pdf], due 12/8. (submit as assignment 12)
  12. Register allocation [pdf], due 12/15. (submit as assignment 13)

Instructions for turning in assignments: Assignments are due by 6am of the due date. Upload your compiler using the web-form at the URL given in the email to the google group. The compiler must be a stand-alone python script that reads in the input python program specified as argv[1]. Your compiler should print the C program text to standard output.



Quizzes (given in class):

  1. 9/8: on material from assignment 1 (Integer expressions and ASTs). solution.
  2. 9/15: on material from assignment 2 (Parsing). solution.
  3. 9/22: on material from assignment 3 (Floats, bools, and polymorphism). solution.
  4. 9/29: on material from assignment 4 (Type analysis). solution.
  5. 10/6: on material from assignment 5 (Variables, statements, and iterative type analysis). solution.
  6. 10/15: on material from assignment 6 (Lists, dictionaries, and heap allocation) ugrad solution, grad solution.
  7. Practice quiz for assignment 7 with solution pdf. (Midterm will include material up through assignment 7)
  8. 11/12: on material from assignment 8. solution.
  9. 11/19: on material from assignment 9. solution.
  10. 12/3: on material from assignment 10. solution.
  11. 12/10: on material from assignment 11 (cancelled, material will be tested in the final exam) practice quiz.
  12. Practice quiz for register allocation.


Exams:

  1. Midterm: in class on Oct. 31
    ugrad solution, grad solution, CAETE solution,
  2. Final: in 1B14 on Tuesday, Dec. 16, 10:30am to 1:00pm. solution,


Grades are posted here.

If you can't solve a problem, then there's an easier problem you can solve: find it. - George Polya