CS 321, 322 Languages and Compiler Design

Credit Hours: 4, 4
Course Coordinator: Andrew Tolmach
Course Description: Principles of programming languages and language implementation by compilation. Techniques of language definition. Run-time behavior of progrmas. Compilation by recursive descent. Use of LR compiler-generation tools. Design and implementation of a compiler for a small language. Prerequisites: CS 202, 300, 311.
Prerequisites: Substantial experience with C, C++, or Java programming.
Basic knowledge of computer organization and machine language.
Elementary automata theory is useful.
Experience with the Unix operating system and with a block-structured language such as Pascal are useful.
Goals: To give an in-depth understanding of the design and implementation of programming languages and of their compilers. The CS 321/322 sequence is centered around a substantial programming project: implementing a complete compiler for a realistic language.

CS 321 describes formal methods for specifying the syntax and semantics of languages, and uses these methods to help build the compiler's front end. Programming language structure and capabilities are examined with an emphasis on understanding the demands of efficient implementation.

Upon the successful completion of this course students will be able to:

  1. Explain the phase structure of a typical compiler and the role of each phase.
  2. Describe and apply mechanisms for defining the lexical structure of a programming language.
  3. Use context-free grammars to define syntax of a programming  language.
  4. Describe and apply mechanisms for transforming grammars to make them suitable for predictive parsing, and for building LL(1) parsing tables.    
  5. Explain the operation of a shift-reduce bottom-up parser.
  6. Construct abstract syntax trees for programs in a simple language.
  7. Distinguish between inherited attributes and synthesized attributes,  and use them to define simple syntax-directed actions.
  8. Describe and apply the basic concepts of data abstraction, incapsulation,  object-oriented classes, and modules.
  9. Describe and apply the basic concepts of type systems, including primitive types, aggregate and recursive types, abstract data types, and type equivalence models.
  10. Contrast the main features of different programming paradigms,  including procedural, object -oriented, and functional.
  11. Implement a lexical analyzer, parser, and type-checker for a simple but realistic language.    
CS 322 concentrates on the compiler's backend, including code generation and runtime organization. Completed compiler projects will produce machine code that can be run directly on the target hardware.

Upon the successful completion of this course students will be able to:

  1. Explain basic approaches to formal specification of languages.  
  2. Explain the differences between interpreters and compilers.
  3. Describe and apply the basic concepts of sequential control abstraction, including structured control constructs and subroutines.       
  4. Explain runtime organization of program execution, including activation records, static and dynamic access links, and frame and stack pointers.
  5. Describe standard runtime representations for arrays, records, objects, and first-class functions.    
  6. Explain different parameter-passing modes and their implementation  implications.   
  7. Give examples of peephole and global optimizations, and explain the general techniques involved in each of them.   
  8. Explain the concept of garbage collection and the typical algorithms.    
  9. Implement an interpreter for a simple but realistic language.
  10. Implement a code generator for a simple but realistic language,producing native code for a real machine.
Textbooks: Compilers: Principles, Techniques, and Tools, Aho, Sethi, and Ullman, Addison-Wesley, 1986.
References: Reference manuals for software tools; hardware architecture manuals.
Major Topics: CS 321:
Language Design Issues
Compiler Structure, symbol tables
Lexical analysis theory and tools
Syntax Analysis
Data types
Syntax-directed Translation
Type checking
Formal Semantics

CS 322:
Runtime Organization
Target Machine Architecture
Intermediate Language generation
Machine code generation
Optimization
Non-standard programming models

Laboratory Exercises: CS 321: A complete frontend for a small but realistic language.
Project #1: Symbol tables (2 weeks)
Project #2: Lexical analysis (2 weeks)
Project #3: Parsing (3 weeks)
Project #4: Type checking (3 weeks)

CS 322: A complete backend for the language of CS 301
Project #1: Target machine architecture (2 weeks)
Project #2: Translation of control structures (2.5 weeks)
Project #3: Intermediate Code Generation (2.5 weeks)
Project #4: Machine Code Generation (3 weeks)


CAC Category Credits Core Advanced
Data Structures
Algorithms 1.0
Software Design 2.0
Computer Architecture
Programming Languages 5.0

Oral and Written Communications: None.
Social and Ethical Issues: None.
Theoretical Content: Finite automata and regular languages (2 weeks)
Context-free languages and parsing (3 weeks)
Type systems (0.5 weeks)
Operational and denotational semantics (1.5 weeks)
Dataflow analysis (0.5 weeks)
Problem Analysis: None.
Solution Design: Many of the lab projects require significant design of data structures and algorithms for parts of the compiler project.