"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)
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)
Programming Language Processors
An introductory course in engineering compilers and interpreters for computer programming languages
Course Information Handout (PDF)
Wed evening 6:30-9:30 pm
Cordy, Introduction to Compiler Construction Using S/SL, 5th Edition, Queen's 2006
CISC 458 / 858 Discussion Forum
Thu evening 6:30-7:30 pm
Mon, Tue evening 6:30-7:30pm,
Introduction and Basic Concepts
Course introduction, basic concepts of translators, compilers, interpreters. Compiler structure, the PT Pascal compiler.
Introduction of the 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.
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
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.
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
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.
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
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.
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.
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
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).
Overflow & Review
Course review and study outline.
Exam format, example exam walkthrough and hints.
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 and Project Assignment Help
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
Basic concepts and terminology, compiler structure, S/SL. Scanners and screeners, implementation in S/SL. Textbook chapters 1-6 inclusive.
Lexical and Syntactic structure, grammars, PDA and BNF, bottom-up and top-down parsing. Runtime model of expressions. Textbook chapters 7-11 inclusive.
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.
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.
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.
In this assignment you will modify the PT Scanner/Screener to recognize the lexical tokens of the new extended language.
In this assignment you will modify the PT Parser to parse programs written in the new extended language.
In this assignment you will modify the PT Semantic Analyzer to analyze and generate T-code for programs written in the new extended language.
In this assignment you will modify the PT Code Generator to generate Intel x86 assembly code for programs written in the new extended language.
Every member of each group must submit a project self-evaluation - it forms a part of your project mark!
References about PT Pascal
Syntax charts from the PT Report appendix in the course textbook.
History and other information about the programming language Pascal, of which PT is a small subset.
References about S/SL
Definitive 1982 ACM Transactions paper on S/SL, from the ACM journal archives (Queen's access only).
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).
A paper proving that the SL subset of S/SL can parse the LR(k) languages. (Queen's access only).
A paper desribing a simple method for constructing SL parsers from LL(1) formal grammars. (Queen's access only).
Unix Command Line Programming
The University of Surrey introduction to Unix command line programming.
Linux Documentation Project guide to scripting the Bourne shell (Unix sh and Linux bash).
The Unix VI Text Editor
A handy one-page pocket-foldable guide to VI commands.
The FreeBSD Unix project introduction to the VI editor, by Bill Joy and Mark Horton.
The Intel x86 Machine
Linux x86 Gnu assembly languge "cheat sheet". Quick reference to assembly language notation and basics.
Introduction to the Gnu Intel x86 assembly language on Linux.
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.