CISC / CMPE 458/858 - Generic Outline

Contacts - General Information - Lectures - Tutorials - Quizzes - Project - Resources - 458 / 858 Discussion Forum

Programming Language Processors

"Nobody believed that I had a running compiler and nobody would touch it.
They told me computers could only do arithmetic." - Rear Admiral Grace Hopper (1906-1992)

Contacts

Professor
        J.R. Cordy

Office:    Goodwin Hall 625,
              TBA or by appointment
Voice:     533 6054
Email:     cordy at cs • queensu • ca

Final Examination:
TBA

Course Summary & Study Guide (PDF)
Exam Review Lecture (PDF)

Teaching Assistant
       TBA

Email:     TBA

Old exams are available in the Queen's Exambank

General Information

Course Title

Programming Language Processors

Course Info    

An introductory course in engineering compilers and interpreters for computer programming languages

Course Information Handout (PDF)

Lectures

Wed evening 6:30-9:30 pm
Location TBA

Textbook

Cordy, Introduction to Compiler Construction Using S/SL, 5th Edition, Queen's 2006

CISC 458 / 858 Discussion Forum

Tutorials

Thu evening 6:30-7:30 pm
Location TBA

Project Advising

Tue evening 6:30-7:30pm,
School of Computing CASlab, WLH 310

Lectures

Week 1

Introduction and Basic Concepts

Course introduction, basic concepts of translators, compilers, interpreters. Compiler structure, the PT Pascal compiler.

Week 2

Syntax/Semantic Language

Introduction of the 2012 course project.

S/SL language and model. SL - S/SL without mechanisms, basic rules, actions. Semantic mechanisms, S/SL whole programs. S/SL implementation - the S/SL machine, translation of S/SL to bytecode, the S/SL processor, the table walker.

Week 3

Scanners, Lexical & Syntactic Spec of Languages

Scanners - tokens, compounds, single token vs co-routine scanners. Character classes, the Buffer mechanism. Screeners - keywords and identifiers, hash functions, constant evaluation, include files. Scanner/Screeners in S/SL.

Lexical and Syntactic Specification of languages - lexical vs syntactic structure. Terminology - alphabet, string, language. Specification of lexical structure - regular expressions, finite state automata, transition matrices. Regular languages in S/SL. Limitations of regular languages.

Syntactic Structure - push-down automata (PDA's), grammars, Backus-Nauer form (BNF), parse trees. Precedence and associativity. Ambiguous grammars, the if-then-else ambiguity.

Assignment #1: Scanner/Screener

Week 4

Parsing

Parsing I - Bottom-up parsing, shfit-reduce parsers, LR grammars.

Parsing II - Top-down parsing, recursive descent implementation, difficulties, deterministic top-down parsers, LL grammars.

Parsing III - SL parsers, SL parsing technique. Parsing power of SL. Syntax error recovery, recovery loops, handling free form languages.

Quiz #1: Basic concepts and terminology, compiler structure, S/SL. Scanners and screeners, implementation in S/SL. Textbook chapters 1-6 inclusive.

Week 5

Runtime Organization I, II & III

Runtime Organization I - Kinds of semantics, operational models, abstract machines. The expression stack (ES) model, relation to postfix. The PT expression stack, T-code for expressions.

Runtime Organization II - Scopes, static, automatic and dynamic variables, the Run Stack model. Maintaining the Run Stack, the Dynamic Pointer Stack. Static visibility, lexical levels, (LL, ON) addressing. The Display, addressing local variables using the Display, maintaining the Display.

Runtime Organization III - Procedures, calling & returning. Value, reference, name and value-result parameters. Passing parameters. Function results. Procedure entry and exit, the markstack register.

Assignment #1 due

Assignment #2: Parser

Week 6

Runtime Organization IV, Semantic Analysis I

Runtime Organization IV - Storage layout, arrays, 1-, 2- and n-dimensional array layout in storage, subscripting computation and code. Records, arrays of records.

Semantic Analysis I - What is semantic analysis? Validation, annotation. The Semantic phase - interface to other phases, attributed trees, triples, quadruples, abstract machine code. Shared tables.

Quiz #2: Lexical and Syntactic structure, grammars, PDA and BNF, bottom-up and top-down parsing. Runtime model of expressions. Textbook chapters 7 - 11 inclusive.

READING WEEK BREAK

Skiing. Rest. Gather energy for second half of term.


Week 7

Semantic Analysis II & III

Semantic Analysis II - How is it done? Tabulation, simulation. Simulation - the symbol stack, effective access attributes. The type stack, effective type computation. Handling declarations. Semantic mechanisms, semantic operations, S/SL conventions.

Semantic Analysis III - Tabulation. Evolution of symbol table structures - the basic symbol table, procedures, nested scopes, user defined types.

Assignment #2 due

Assignment #3: Semantic Analyzer

Week 8

Semantic Analysis III, Implementing the Run Time Model I

Semantic Analysis III (cont'd) - Scope control - imports/exports, records and classes, saved scopes.

Implementing the Run Time Model I - Mapping the model to real machine structures (storage allocation and code generation). Machine architectures - stack vs register machines, memory, addressing modes. Example machine architectures - IBM/360, PDP-11, x86, RISC, windowed RISC.

Implementing the ES - ES on stack, ES in registers, mixed strategies. Implementing the RS - static variables, automatic variables, faking a hardware stack, implementing the Display.

Week 9

Storage Allocation, Code Generation I

Storage Allocation - Base/displacement model, data descriptors. Data descriptors - relation to variables and LL,ON, relation to target architectures and addressing modes. The addressing modes table, missing addressing modes, addressing code. Storage allocation - size and alignment, characterizing a machine, primitive types, arrays and records, the fundamental allocation algorithm.

Code Generation I - code optimization. Global optimization - code motion, strength reduction, common sub expression elimination. Local optimization - coalescence, constant folding, local strength reduction. Peephole optimization.

Quiz #3: Runtime model of scopes and storage, arrays and records, calling and returning. Semantic analysis, validation and annotation. The symbol and type stacks, semantic mechanisms. Evolution of symbol tables, scope control. Textbook chapters 12 - 16 inclusive.

Week 10

Code Generation II & III

Code Generation II - code templates, operand conditions, code decision trees (IST's). Subscripting templates - static, automatic and reference parameter cases. Scaling and folding of subscripts. Record field selection templates. Addressability, reducing modes.

Generating code for expressions - the delay principle. The operand stack - code selection in S/SL. Example: addition code selection rules in S/SL. Managing temporary registers.

Code Generation III - Boolean expression templates, data model, control model. Condition descriptors, data vs control model. Control model templates using condition descriptors and the Operand stack.

Assignment #3 due

Assignment #4: Code Generator

Week 11

Code Generation IV, Direct Interpretation

Code generation IV - Statement templates - if statement, loops, case statement. The fixup stack. Call statements. Separate compilation, external calls. Linking and relocation, static and dynamic linking.

Implementing the Run Time Model II - Direct interpretation. Abstract machine interpreters. Virtual machine implementation, microprogrammed bytecode interpreters. The PT abstract machine interpreter. Just-in-time (JIT) compilers.

Quiz #4: Implementing the Run Time Model - stack vs register machines, choices for the ES. Storage Allocation - base/displacement model, data descriptors, addressing modes, allocating arrays and records. Code Generation I - global, local and peephole optimization methods. Textbook chapters 17-19 inclusive.

USAT Course Evaluation (in class before Quiz).

Week 12

Overflow & Review

Course review and study outline.

Exam format, example exam walkthrough and hints.

Project self-evaluations.

Format of the examination will be similar to previous examinations, with all answers written on the exam paper. Questions will be much like those on previous examinations.

Assignment #4 due

Project self-evaluation (PDF)

Tutorials

Tutorials and Project Assignment Help

Tutorials: TBA
Advising: TBA, CASLab, WLH 310

You can find more information about tutorials, including tutorial handouts and slides, questions and answers online in the Tutorial section of the CISC 458 discussion forum.

CISC 458 Forum

Quizzes

Quiz #1

Basic concepts and terminology, compiler structure, S/SL. Scanners and screeners, implementation in S/SL. Textbook chapters 1-6 inclusive.

Quiz #2

Lexical and Syntactic structure, grammars, PDA and BNF, bottom-up and top-down parsing. Runtime model of expressions. Textbook chapters 7-11 inclusive.

Quiz #3

Runtime model of scopes and storage, arrays and records, calling and returning. Semantic analysis, validation and annotation. The symbol and type stacks, semantic mechanisms. Evolution of symbol tables, scope control. Textbook chapters 12 - 16 inclusive.

Quiz #4

Implementing the Run Time Model - stack vs register machines, choices for the ES. Storage Allocation - base/displacement model, data descriptors, addressing modes, allocating arrays and records. Code Generation I - global, local and peephole optimization methods. Textbook chapters 17-19 inclusive.

Course Project

Project
Description

The course project consists of implementing a small set of language extensions to an existing compiler for a modest programming language. The project will be done in teams of 3 to be chosen by the students. The project is designed to give you realistic experience in the practice of software engineering as well as providing hands-on experience in building a compiler.

The compiler system you will be working with uses a practical compiler construction technique (S/SL) which is the same one used in IBM high-quality compilers for Cobol, C and other languages.

You will be working in the Unix /Linux environment using Unix command line programming.

Assignment #1

In this assignment you will modify the PT Scanner/Screener to recognize the lexical tokens of the new extended language.

Assignment #2

In this assignment you will modify the PT Parser to parse programs written in the new extended language.

Assignment #3

In this assignment you will modify the PT Semantic Analyzer to analyze and generate T-code for programs written in the new extended language.

Assignment #4

In this assignment you will modify the PT Code Generator to generate Intel x86 assembly code for programs written in the new extended language.

Self-Evaluation

Every member of each group must submit a project self-evaluation - it forms a part of your project mark!

Resources

References about PT Pascal

PT Pascal Syntax Charts

Syntax charts from the PT Report appendix in the course textbook.

The Pascal Programming Language

History and other information about the programming language Pascal, of which PT is a small subset.

References about S/SL

An Introduction to S/SL: Syntax/Semantic Language

Definitive 1982 ACM Transactions paper on S/SL, from the ACM journal archives (Queen's access only).

S/SL Revisited

A public IBM experience paper on using S/SL in an unusual way in the IBM COBOL compiler, from the ACM archives (Queen's access only).

SL Parses the LR Languages

A paper proving that the SL subset of S/SL can parse the LR(k) languages. (Queen's access only).

Automatically Generating SL Parsers from LL(1) Grammars

A paper desribing a simple method for constructing SL parsers from LL(1) formal grammars. (Queen's access only).

Unix Command Line Programming

University of Surrey Unix Guide

The University of Surrey introduction to Unix command line programming.

Bash Scripting Guide

Linux Documentation Project guide to scripting the Bourne shell (Unix sh and Linux bash).

The Unix VI Text Editor

VI Quick Reference Card

A handy one-page pocket-foldable guide to VI commands.

An Introduction to Display Editing with VI

The FreeBSD Unix project introduction to the VI editor, by Bill Joy and Mark Horton.

The Intel x86 Machine

gcc x86 Assembly Quick Reference

Linux x86 Gnu assembly languge "cheat sheet". Quick reference to assembly language notation and basics.

Introduction to Linux Intel Assembly Language

Introduction to the Gnu Intel x86 assembly language on Linux.

History Links

Grace Hopper

Quotes and biography of Rear Admiral Grace Murray Hopper, co-inventor of COBOL and designer / implementer of the world's first widely known progamming language compiler (Remington-Rand's "Math-Matic").

"But Grace, then anyone will be able to write programs!" - Unknown, circa 1954.