CISC / CMPE 458/858 - Winter 2017

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,
              Wed 14:00-15:00,
               or by appointment
Voice:     533 6054
Email:     cordy at cs • queensu • ca

Final Examination: TBA

Course Summary & Study Guide
Exam Review Lecture

Teaching Assistants
       Nicholas Petrielli
       Ben Wright

Office:    N/A
Email:     13np8 at queensu • ca
              12bcw at queensu • ca

Old exams are available in the Queen's Exambank
Answers to 2004 Exam

General Information

(Scheduling may be subject to change as course progresses)

Course Title

Programming Language Processors

Course Info    

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

Course Information Handout

Lectures

Wed evening 6:30-9:30 pm
Walter Light Hall 210

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
Walter Light Hall 210
(starting Thu Jan 19)
Tutorial materials will also be available
online

Project Advising

Tue evening 6:30-7:30 pm
CASLAB, WLH 310
Thu evening 7:30-8:30 pm
Walter Light Hall 210,
following tutorial

Labs

There is no scheduled lab time. Unscheduled lab time of at least 3 hours per week will be required to complete the course project.

Lectures

Week 1

Introduction and Basic Concepts

Lecture 1 Lecture 2 Lecture 3

Jan 11

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

Course Information Handout

References: Text chapters 1 and 2

Week 2

Syntax/Semantic Language

Lecture 4 Lecture 5 Lecture 6

Jan 18

Introduction to the 2017 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.

References: Text chapters 3,4 and 5, appendix 1.

Reading assignment: Read Appendix 2.

More S/SL References

Project details

Week 3

Scanners, Lexical & Syntactic Spec of Languages

Lecture 7 Lecture 8 Lecture 9

Jan 25

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.

References: Text chapters 6, 7 and 8.

Team contracts due

Assignment #1: Scanner/Screener - due Wed Feb 8

Week 4

Parsing

Lecture 10 Lecture 11 Lecture 12

Feb 1

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.

References: Text chapters 9 and 10.

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

Week 5

Runtime Organization I, II & III

Lecture 13 Lecture 14 Lecture 15 Lecture 16

Feb 8

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.

References: Text chapters 11 and 12.

Assignment #1 due Wednesday

Assignment #2: Parser - due Wed Mar 1

Week 6

Runtime Organization IV, Semantic Analysis I

Lecture 17 Lecture 18

Feb 15

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.

References: Text chapters 13 and 14.

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.
(
See example old Quiz #2)

READING WEEK BREAK

Feb 20-24

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


Week 7

Semantic Analysis II & III

Lecture 19 Lecture 20 Lecture 21

Mar 1

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.

References: Text chapters 15 and 16.

Assignment #2 due Wednesday

Assignment #3: Semantic Analyzer - due Wed March 22

Week 8

Semantic Analysis III, Implementing the Run Time Model I

Lecture 22 Lecture 23 Lecture 24

Mar 8

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.

References: Text chapters 16 (cont'd), and 17.

Week 9

Storage Allocation, Code Generation I

Lecture 25 Lecture 26

Mar 15

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.

References: Text chapters 18 and 19.

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

Lecture 27 Lecture 28 Lecture 29

Mar 22

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.

References: Text chapter 20.

Assignment #3 due Wednesday Sunday, March 26

Assignment #4: Code Generator - due Fri April 7 Thu Apr 13

Week 11

Code Generation IV, Direct Interpretation

Lecture 30 Lecture 31

Mar 29

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.

References: Text chapter 21, Direct interpretation handout.

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 Summary & Study Guide
Exam Review Lecture

Apr 5

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 Friday Thursday, April 13

Project self-evaluation

Previous CISC 458 / 858 exams are available in the Queen's Exambank - search for "458"

Tutorials

Tutorials and Project Assignment Help

Tutorials: Place TBA, tentatively Thu evening 6:30 -7:30
Advising: TBA

First tutorial:
Thu Jan 15

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

(Scheduling may be subject to change as course progresses)

Quiz #1

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

Example Quiz #1

Wed Feb 1

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.

Example Quiz #2

Wed Feb 15

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.

Example Quiz #3

Wed Mar 15

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.

Example Quiz #4

Wed Mar 29

Course Project

(Scheduling may be subject to change as course progresses)

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.

Project Description

Team Agreement

Project Criteria

Questions? See the CISC 458 Tutorials Forum

Assignment #1

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

Assignment #1

due Wed Feb 8

Assignment #2

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

Assignment #2

due Wed Mar 1

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 #3

due Wed Mar 22
Sun Mar 26, 11:59pm

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.

Assignment #4

x86 Machine References

due Fri Apr 7
Thu Apr 13, 11:59pm

Self-Evaluation

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

Project self-evaluation

(due by Wednesday April 12 or any time before exam)

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.