CS652 Home

Added by Terence Parr, last edited by Terence Parr on Apr 23, 2009  (view change)

This is the home page for Computer Science 652, Graduate Programming Languages, at the University of San Francisco. This course is all about implementing programming languages.

Instructor: Terence Parr

Spring 2009: HR530 (lab room) MW 10:30pm - 12:15pm
Last day of class: Wednesday May 13, 2009

Midterm exam: Apr 1, 2009
2nd midterm exam: May 13, 2009 (serves as final)

Materials use ANTLR v3.1.1 or above

No laptops are allowed in my lectures ('cept mine)

Abstract

Because programming languages are at the core of writing software, programmers should have a thorough understanding of how languages are designed, implemented, and manipulated. This course concerns itself specifically with the implementation and translation of computer languages, leaving an in-depth study of language design to another course. Students will learn the formalisms behind computer languages, but the focus will be on developing the ability to build languages and their translators.

This class is only moderately difficult for the most part, though some of the language formalisms take a while to sink in. Well, actually you have one major hurdle to get over and then it's easy--abstraction in the sense of recursion, meta-language, programs that generate other programs (or even themselves), etc... If you get a headache when you try to figure out how the first C compiler could have been written in C, you might invest in a big bottle of aspirin.

Students are required to build projects in Java unless specified otherwise. You should have a good understanding of data structures and algorithms. Prior experience with language implementation is helpful, but not required. You will be expected to write a lot of code this semester--lots of little projects and then a big language implementation project at the end.

Two classes is considered full-time and, hence, you can expect this class to require <= 20 hours/week including class time.

Student Learning Outcomes

At the end of this course, you will

  • be familiar with the evolution of programming languages
  • be able to build NFA, DFA, and related state machines
  • understand the nature and structure of language
  • be able to describe a variety of garbage collection strategies
  • be able to describe how object-oriented languages implement inheritance, polymorphism, encapsulation, and data-hiding
  • be very comfortable with grammars and parsing.
  • know how to implement a simple interpreter
  • be able to translate common language constructs to assembly by hand
  • know how static, just-in-time, and on-the-fly compilers work
  • be able to build symbol tables and intermediate representations
  • be able to build lexers and parsers by hand and via ANTLR
  • be able to build source-to-source translators, config files readers, XML parsers, interpreters, and code generators for language such as PostScript and HTML.

In short, you will be able to discuss intelligently the implementation and translation of programming languages and will have built several small projects that teach the fundamental implementation techniques.

Syllabus

I. Introduction

Homeworks:

Labs:

II. Parsing

  • Basic parsing patterns
  • Advanced parsing patterns
    • Backtracking
    • Memoizing
    • Predicated
  • ANTLR introduction: Chapter 3 from ANTLR reference
  • Ambiguities and Nondeterminisms: Section 11.5 from ANTLR reference
  • Using semantic and syntactic predicates: Chapter 12 from ANTLR reference (required reading: Chapters 13, 14 from ANTLR reference)

Labs:

III. Intermediate forms and semantic analysis

  • Intermediate form trees
    • Resource: Chapter 7 from ANTLR reference
    • Parse trees
    • ASTs: homogeneous, Normalized Heterogeneous AST, Irregular Heterogeneous AST
  • Tree walking patterns
    • Embedded heterogeneous tree walker
    • External visitor
    • Tree grammar
    • Tree pattern matcher
  • Symbol table patterns
    • Monolithic
    • Nested scopes
    • Data aggregates like C structs
    • Class hierarchies
      Resource: Symbol tables
  • Semantic analysis: static type computation and enforcing static type equivalency

Labs:

IV. Interpreters and program execution

Labs:

V. Translators

Labs:

Projects

Parsing Graphviz DOT files the hard way 6% Due Feb 11
Build a lexer and parser by hand that checks DOT files for correct syntactic structure.

AST Construction 10% Due Feb 25
Build an AST for an object-oriented programming language.

Symbol table 15% Due Mar 16
Build a symbol table for an object-oriented programming language.

CANCELED! Byte code assembler and interpreter 10%
Build an assembler and interpreter for a simple stack-based byte code.

Command interpreter 14% Due Apr 10 5pm
Build an interpreter that walks a list of Command objects instead of byte codes to execute programs.

Adding Closures to a Java-like language 10% Due May 8
Source-to-source translator that adds simple closures and map operator to Java.

CANCELED! C subset compiler 10% Due May 13 (last day of class)
Build a compiler for a subset of C with arrays and int types. Generates LLVM intermediate representation, which will compile the IR down to machine code.

There are no late projects and incomplete features do not count.

All projects will be graded and must run under UNIX. Projects will be graded interactively and may require students to meet with the instructor outside class.

SVN repository

All projects must be submitted in SVN. For example, here is how I would create my cs652 directory:

svn mkdir https://www/svn/parrt/cs652 -m 'add dir'

Exams

There will be two written exams. The midterm exam is on ??.

Grading

Your grade will be computed according to the following relationship:

10% Labs
15% Exam 1
15% Exam 2
5% Homework/class participation
55% Projects

I consider an "A" grade to be above and beyond what most students have achieved. A "B" grade is an average grade or what you could call "competence" in a business setting. A "C" grade means that you either did not or could not put forth the effort to achieve competence. An "F" grade implies you did very little work or had great difficulty with the class compared to other students.

Unless you are sick or have a family emergency, I will not change deadlines for projects nor exam times. For example, I will not giveyou a special final exam just because you want to fly home early. Consult the university academic calendar before making travel plans.

Miscellaneous

Attendance is part of your grade. Even if you know this subject well, I will be providing a number of anecdotes from industry and other goodies during my lectures. Anything I say in class is fair game for an exam

Tardiness. All classes begin precisely at 10:30am and will restart after the 10 minute break exactly on time.

Academic honesty. You must abide by the copyright laws of the United States and academic honesty policies of USF. If told you may for a particular project, use any code from the net that you find as long as it does not violate the software's license. You may not borrow code from other current or previous students. All suspicious activity will be investigated and, if warranted, passed to the Dean of Sciences for action.

Mailing list. You must all join:

http://cs.usfca.edu/mailman/listinfo/cs652

I will make lots of announcements on it.

Course text

The Definitive ANTLR Reference. You will definitely need this as a reference for ANTLR.

Resources

How To Read C Declarations

Credits

I'd like to thank Kay Roepke for his help designing this course structure.

Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.