Queen's School of Computing

CISC 458/3.0 Programming Language Processors

Original Author: Jim Cordy
Last Revised: September 25, 2006

Calendar Description

Introduction to the systematic construction of a compiler: grammars and languages, scanners, top-down and bottom-up parsing, runtime organization, symbol tables, internal representations; Polish notation, syntax trees, semantic routines, storage allocation, code generation, interpreters.

Prerequisites: CISC 121/3.0, 221/3.0, 223/3.0 (or 366/3.0).


This course introduces the student to the major concepts and techniques of programming language implementation, with emphasis on practical methods rather than theoretical issues. Students are provided with hands-on experience in modifying an existing compiler, and gain experience with one or more typical software tools that aid in compiler construction such as S/SL, LEX, YACC, GLA, GAG or others.


Overview, Basic Concepts, Compilers and Interpreters, Compiler Structure, Implementation Goals (1 week)

Lexical and Syntactic Specification of Programming Languages:
Regular expressions, Context free Grammars, Backus-Naur Formalism (1 week)

Lexical analysis:
Regular Expressions, Scanners, Scanner Generators (1 week)

Syntax analysis:
Parsers, Top-down and Bottom-up Parsing, Recursive descent, LL and LR techniques, Parser Generators (2 weeks)

Run Time Models:
Storage Organization, Expression Evaluation, Procedure Linkage, Abstract Machines (1 week)

Semantic Analysis:
Symbol tables, Scope Analysis, Type Analysis, Attribution (2 weeks)

Implementing the Run Time Model:
Evaluation and Procedure Stacks, Storage Allocation, Register Assignment (1 week)

Code Generation:
Code Templates, Arithmetic Expressions, Boolean Expressions, Control Structures (2 weeks)

Global, Local and Peephole Optimizers (1 week)

The course normally includes a practical course project consisting of implementing a small set of language extensions to an existing compiler for a modest programming language using standard compiler construction tools such as S/SL, LEX, YACC, GLA, GAG or others. The project is structured as a sequence of assignments carried out cooperatively in small teams guided by practical tutorials.

Possible Texts

  • Cordy, Introduction to Compiler Construction Using S/SL, Queen's.

  • Aho, Sethi, and Ullman, Compilers: Principles, Techniques, and Tools, Addison Wesley.

  • Appel, Modern Compiler Implementation in Java/C/ML, Cambridge University Press 1998