New Building Website

CSA 474/574 Compiler Design (3 credits)

 

Occasionally offered during the spring semester.

Catalog description:

Examination of the nature of programming languages and programs which implement them. Compiler and interpreter design and implementation techniques. Review of grammars and languages (context free, context sensitive, regular). Design of interactive interfaces. Parsing of context free languages. Lexical analysis. Semantic analysis and code optimization.

 
Prerequisites:

(CSA274 or CSA606 or equivalent) and (CSA278 or equivalent).

 

Course Objectives:

  • To examine the nature of programming languages.
    • to appreciate the various formal methods of specifying syntax.
    • To differentiate between syntax, semantics, and pragmatics.
  • To understand the operating and design principles behind language transducers.
    • To understand the major components of a compiler: scanner, parser, code generator, and code optimizer.
    • To have a working knowledge of at least one parsing technique.
  • To experience a large systems programming project.

Learning Outcomes:

CSA474.1: To describe and differentiate among the features of programming languages that can be described by language syntax versus semantics.
CSA 474.1.1     Employ a regular expression to describe tokens.
CSA 474.1.2     Use a context free grammar to describe the syntax of a context free language.

CSA474.2: To describe and differentiate among the purposes of the major components of a compile: scanner, parser, code generator, code optimizer, and symbol table.

CSA474.3: To demonstrate an understanding of some of the standard parsing techniques.
CSA 474.3.1     Given a particular parsing problem, to choose the most appropriate parsing techniques using various criteria such as efficiency, complexity, etc.
CSA 474.3.2     Given a context free grammar for a small language, create a recursive descent parser for that language.
CSA 474.3.3     distinguish between top-down and bottom-up parsing techniques.
CSA 474.3.4     Create an LL(1) parsing table for a small language. 

CSA474.4: To demonstrate an understanding of semantic processing.
CSA 474.4.1     Given an attribute grammar for a language, to be able to use this grammar to process a simple language.
CSA 474.4.2     Explain the information that is recorded in a symbol table.
CSA 474.4.3     Explain the way that variable types are handled in a compiler, including type equivalence and type conversions. 

CSA474.5: To work in a small team to implement a compiler for a small programming language that includes multiple control structures, functions, parameters, and a symbol table.
 

Required topics (approximate weeks allocated):

  • Overview of the translation process (.5)
  • Formal notations (1)
    • review of regular expressions
    • review of formal grammars
  • Compiler tools (1.5)
    • currently available tools (e.g., lex and yacc)
  • Lexical analysis (2)
    • regular expression
    • automata
    • tokens
  • Syntax analysis (3)
    • parsers
    • context-free grammars
    • top-down parsing
    • bottom-up parsing
    • LL(1) grammars and parsing
    • LR grammars and parsing
    • parser generators
  • Semantic processing (3)
    • syntax-directed translation
    • symbol tables
    • type checking
    • type systems
    • type equivalence
    • type conversions
    • run-time environments
    • attribute grammars
  • Code optimization (1)
  • Code generation (1)
  • Compiler project (1)
  • Exams/Review (1)

Graduate students:

Students enrolled in CSA 574 will be given additional readings and/or assignments.