CS652 Home

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, @the_antlr_guy

Spring 2011: 2:15pm - 3:20pm MWF in COWELL 312
Last day of class: Wednesday May 11, 2011

Midterm exam: March 11, 2011
2nd midterm exam: Wednesday May 11, 2011

Materials for this class assume ANTLR v3.3 and StringTemplate 3.2.1 or above

Textbook is Language ImplementationPatterns (LIP):

You'll also find The Definitive ANTLR Reference (TDAR) useful.

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 can be challenging conceptually. 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, algorithms, and recursion. Prior experience with language implementation is helpful, but not required. You will be expected to write a lot of code this semester, culminating in a complete programming language implementation.

Two graduate classes is considered full-time at USF and, hence, you can expect this class to require about 20 hours/week of class time and homework/development time. You should start early on every project. Note that there is no such thing as a late project. Late projects get a 0 grade as I will be handing out the solutions the day projects are due.

Course goal

By the end of this course, you will have implemented a complete programming language. The lecture flow will lead you through all of the formalisms and techniques you'll need and we'll closely follow the chapter sequence in the textbook for the first part of the semester. For the Spring 2011 semester, we're going to build a bytecode compiler and interpreter for SmallTalk. The main tasks are:

parser and AST constructor
bytecode generator
bytecode interpreter
SmallTalk primitives and runtime support

After the first stage, you will all start from my solution for the subsequent stages. This will show you what a proper implementation looks like and prevents a single bad stage from killing your chances of success on the remaining stages.

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 build symbol tables and intermediate representations
be able to build lexers and parsers by hand and via ANTLR
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 build source to source translators
be able to build a programming language to bytecode compiler
be able to implement a bytecode interpreter

In short, you will be able to intelligently discuss the implementation and translation of programming languages and will have built a nontrivial programming language.

Syllabus

Introduction

The evolution of programming languages
The difference between compilers and interpreters
Chapter 2: The nature of computer languages (TDAR)
Chapter 1: Language applications cracked open (LIP)

Language recognition

Grammars, languages, derivations, parsing
regular vs context-free languages
DFA/NFA, lookahead for predictive parsers
Basic parsing patterns
- Resources: LL Parsing and recursive descent design pattern, 11.1-11.4 from ANTLR reference
- Grammar to Recursive-Descent Parser Mapping
- Recursive-descent Lexer
- Canonical LL(1) Recursive-Descent Parser
- LL(k) Recursive-Descent Parser
Advanced parsing patterns
- Backtracking (grammar, parse tree)
- 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)
gUnit - Grammar Unit Testing

Labs:

Meet my little friends, ANTLR and StringTemplate

Internal representations

Building Intermediate Form Trees
Walking and Rewriting Trees

Symbol tables

Tracking and Identifying Program Symbols
Managing Symbol Tables for Data Aggregates

Semantic analysis

Enforcing Static Typing Rules

Translation and generation

Translating Computer Languages; syntax directed, rule-based, model driven
Generating DSLs with Templates

Interpreters

Building High-Level Interpreters
Building Bytecode Interpreters; stack, register
PostScript case study
Memory allocation and garbage collection
Implementing Polymorphism

SmallTalk

H3. Misc

Language features

Homeworks

Lexer for XML 2% Due Jan 31, 2011
Build a lexer for XML that separates tags from text.

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

Calculator using ANTLR 3% Due Feb 14

Build ASTs 3% Due Feb 21

Symbol table for statically-typed language 5% Due Feb 28

PostScript interpreter 3% Due Mar 7

Projects

SmallTalk grammar and AST construction 10% Due March 30

SmallTalk bytecode compiler 15% Due April 20

SmallTalk interpreter 20% Due May 11

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'

You might find these svn notes useful. Projects will be placed in subdirectories of cs652 wherever you place it on your disk. E.g., you need to create the following directories:

cs652/xml
cs652/dot
...

See the individual project descriptions for more information about what files must be present to submit a project.

Exams

There will be two written exams. The midterm exam is on March 11, 2011.

Grading

Your grade will be computed according to the following relationship:

15% Exam 1
15% Exam 2
5% Class participation
20% Weekly projects
45% Smalltalk 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 achieve competence. An "F" grade implies you did very little work or had great difficulty with the class compared to other students.

Warning: you lose 10% of your grade if you do not provide a jar file that I can run exactly as I specified in various projects. common mistakes are: jar has wrong name, upper or lowercase difference, missing class files, improperly named Java classes. To communicate effectively, programmers must be incredibly precise. in order to work with other programmers, you must be able to spell, provide the right jar files, and know the difference between upper and lower case. shockingly, lots of students get this wrong.

Unless you are sick or have a family emergency, I will not change deadlines for projects nor exam times. For example, I will not give you 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. Please be on time. It's very disruptive for you to come in late and you could miss vital information.

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.

Twitter. You must all follow @cs652 for news, hints, etc...