CS 4110 Compiler Design (4) 2005

Catalog Description

Design and construction of high-level language translators. Formal language theory, parsing algorithms, interpreting, code generation, optimization. Construction of a small compiler. Prerequisites: CS 3120 and CS 3240

Course outline

Overview of compilers

Scanners: theory and implementation

  • finite state machines
  • regular expressions
  • implementation issues for lexical analyzers

Parsers:

theory and implementation

General

  • top-down and bottom-up parsing techniques
  • grammars, derivations, ambiguity
  • first and follow sets
  • error detection and recovery

Recursive Descent Parsers

  • suitable grammars
  • implementation

LL Parsers:

grammar and implementation issues

LR Parsers

  • shift-reduce algorithm
  • table construction methods
  • compiler generators

Symbol tables:

implementation issues

Code generation

  • intermediate code forms
  • techniques

Optimization:

topics, if time permits

Run-time organization and support

  • stack-based storage
  • heap storage issues
  • procedure calls
  • implementation of parameters

Texts

  • Aho, Sethi, Ullman, Compilers
  • Parsons, Introduction to Compiler Construction
  • Brinch-Hansen, On Pascal Compilers