Course Description

Course Number / CSCI 4555
Course Title / Introduction to Compiler Construction
Semester Hours / 3
Course Coordinator / Jeremy Siek
Course URL /

Current Catalog Description

Introduces the basic techniques used in translating programming languages: scanning, parsing, definition table management, operator identification and coercion, code selection and register allocation, error recovery. Students build a complete compiler for a simple language. Prereqs: CSCI 2824 and CSCI 2400. Same as ECEN 4553.

Textbook

None

References

None

Instructors (for the last 3 years: Fall 2006 — Spring 2009)

Jeremy Siek (Fall 2007, Fall 2008)

The course was not offered in 2006.

Meeting Times (Number and Duration of Sessions per Week)

3 sessions per week, 50 minutes per session.

Course Outcomes

Upon completion of this class, students posses:

  • an understanding of how high-level languages features, such as objects and first-class functions, are translated to machine-level operations,
  • the ability to create a parser using lex/yacc,
  • an understanding of program-as-data. Able to write functions that inspect and transform abstract syntax trees,
  • an understanding of static analyses and the ability to implement them, in particular:

otype checking and type inference.

oThe difference between dynamic and static type checking.

oUnderstand polymorphism and its impact on the run-time representations of values.

  • an understanding of memory management techniques, especially garbage collection.
  • an understanding of how to map language features to machine-level features. In particular:

ohow to implement function calls in assembly. Understand calling conventions and able to write assembly code that performs function calls.

oHow to allocate variables to registers. Able to implement a register allocator and able to perform register allocation by hand.

Relationship between Course Outcomes and Program Outcomes

Outcomes / A.
Apply Knowledge / B.
Computing Requirements / C.
Design System / D.
Team Work / E.
Professional Issues / F.
Communicate Effectively
Translation / ✓ / ✓
Parsing / ✓ / ✓ / ✓
Programs-as-Data / ✓ / ✓ / ✓
Types / ✓ / ✓ / ✓
Memory / ✓ / ✓ / ✓
Machine-level / ✓ / ✓ / ✓ / ✓
Outcomes / G.
Analyze Impacts / H.
Professional Development / I.
Current Techniques / J.
Design Tradeoffs / K.
Design & Development
Translation / ✓ / ✓ / ✓ / ✓
Parsing / ✓ / ✓ / ✓ / ✓
Programs-as-Data / ✓ / ✓ / ✓
Types / ✓ / ✓ / ✓ / ✓
Memory / ✓ / ✓ / ✓ / ✓
Machine-level / ✓ / ✓ / ✓

Prerequisites by Topic

  • Formal languages (regular expressions, context-free grammars) from CSCI 2824
  • Trees and Graphs from CSCI 2824
  • Programming in C from CSCI 2400
  • Assembly-code programming from CSCI 2400

Major Topics Covered in the Course

  1. Integer expressions and ASTs
  2. Parsing with PLY (Python Lex-Yacc)
  3. Floats, bools, and polymorphism
  4. Type analysis and specialization
  5. Variables, control flow, SSA, and iterative analysis
  6. Lists and heap allocation
  7. Functions and closure conversion
  8. Objects and Inheritance
  9. Overview of x86 assembly, removing complex opera*
  10. Removing structured control flow and 3-operand statements
  11. Calling conventions, the stack, and translation to x86
  12. Register allocation

Assessment Plan for the Course

There are weekly assignments in which the students incrementally develop a compiler throughout the semester. The assignments are performed in groups of 2-4 students and accounts for 10% of the students grade. There are weekly quizzes to test the students’ individual knowledge and skills. The quizzes are 40% of the grade. There is also a midterm exam (20%) and a comprehensive final exam (30%).

How is Data from this Course used to Assess Program Outcomes?

The instructor retains copies of student homework assignments, midterms, and semester projects. These materials are then evaluated by the department’s external advisory board for examples that demonstrate fulfillment of the program outcomes.

Curriculum Category Content (Semester Hours)

Area / Core / Advanced
Algorithms / 0.5
Data Structures / 0.5
Computer Organization and Architecture / 0.5
Software Design / 0.5
Concepts of Programming Languages / 1.0