Next:
Introduction
 
Contents
CS2111: Design and Implementation of Programming Languages
Pete Jinks
September 30, 1999
CS2111: Design and Implementation of Programming Languages
Pete Jinks pjj@cs.man.ac.uk
Introduction
Syllabus etc.
Examples of Language design - declaring and using variables and strings
Interpreters and Translators
Some example programs and their languages
GREP
and
EGREP
LEX
and
YACC
Strategies for Describing and Implementing Computer Languages
Representation and Meaning
Parse trees
Exercises
Readings
Expressions: Operators
Number of Operands (per operator)
Overloading
Precedence
Associativity
Subexpression evaluation order
Lazy and eager evaluation
Assignment
C
SML
Language design and implementation
Exercises
Readings
LEX
Postfix calculator in
LEX
Descriptions of expected inputs
grammar rules from
3.1
LEX
definitions
Actions, C declarations and code
How
LEX
is used
Using
LEX
to make an infix calculator
Language design and implementation
Overloading
Exercises
Readings
YACC
YACC
program for an infix calculator
Format of the grammar rules for
YACC
YACC
definitions
Actions, C declarations and code
How
YACC
is used
Using
LEX
and
YACC
together
YACC
declarations
LEX
declarations and actions
How
LEX
and
YACC
are used together:
Language design and implementation
Exercises
Readings
YACC
: Further usage
Grammar rules
sequence
invoke
choice
optional
repetition (1 or more)
optional (0 or more)
Left and right recursion
Getting the order of actions correct
Precedence and associativity
Grammatical errors: handling incorrect inputs
Language design and implementation
Exercises
Readings
Inside
LEX
and
YACC
: State Machines
Inside
LEX
: Finite State Automata (FSA)
Inside
YACC
: Push Down Automata (PDA)
Left and Right recursion
Language design and implementation
Exercises
Readings
Debugging
YACC
grammars
How
YACC
works and fails
Debugging an example grammar
Language design and implementation
Exercises
Readings
Parse Trees
Language design and implementation
Passes
Concrete and Abstract
Building parse trees for expressions
Exercises
Readings
Language Design
Error detection and correction
C is deformed because its parents were frightened by keywords
Control structures
Declarations
CPP
Puns: similar representations with different meanings
Overloading symbols
When is white space significant?
Multiple name spaces: same name, different meanings
Synonyms: different representations, similar meanings
Orthogonality
Exercises
Readings
Expressions: Code Generation
Computer structures
Code sequences for S= U*V + X*Y
Code Generation Algorithms
Exercises
Readings
Control structures
From GOTOs to Structured Programming
Concatenation
Selection
Repetition
Repeaters and Completers
Exceptions
Exercises
Readings
Procedures and functions
Introduction
Parameter passing
Call by value
Call by reference
Call by copy/copy back
Call by procedure
Call by name
Polymorphism
First Class Subprograms
Readings
Identifiers: Static and Dynamic Semantics
Semantic Model
Static and dynamic properties
(Static) Scope and (Dynamic) Extent
Declarations
Variables
Readings
Scope and Extent
Classical Block Structure
Recursion
The Stack Model
Function Values
The Heap
Exercises
Readings
Types
Values and types
Strong typing
Type equivalence
Type Coercion
Widening
Narrowing
Primitive types
integer
real
character
boolean
enumerations
subtypes
new types
Language Independant Datatypes
C
SML
Language design and implementation
Readings
Composite Types
Common Composite Types
sets
structures (records, tuples)
unions (variant records)
vectors
strings
Recursive Data Types (RDTs)
sequences
Pointers (references)
Language design and implementation
Readings
Vectors and Arrays - Language design and implementation
Vector Declarations and element access
Implementation
Bound checking
Implementation
Multi-dimensional arrays
Implementation
Static and Dynamic arrays
Implementation
Operations on vectors, including slicing
Implementation
Exercises
Readings
Abstract Data-Types, Modules, Classes and Objects
Abstract Data Types (ADTs)
Modules e.g. ADA
Classes: Object-Oriented Programming Languages (OOPLs)
C++
Readings
Language Design and Implementation - Identifiers
Dictionaries
Using a dictionary
Property entries
Keywords and predefined identifiers.
Binding
Exercises
Readings
Building a Compiler: recognising the input
Chomsky's classification of grammars
Macro pre-processing
Lexical analysis (itemisation, scanning, tokenisation)
Syntactic analysis (parsing)
Semantic analysis
semantic actions for executable statements
Readings
Building a Compiler: generating the output
Code generation
code generator tools
executor program
back-end translator
automatic generation of back-end translator
Code optimisation
Making best use of registers
Constructing a compiler from tasks: Passes
Exercises
Readings
Syntax-directed Translation
When to use a tool or technique
How to combine tools and techniques - Passes
A typical 1-pass organisation
A typical multi-pass organisation
Phases of Compilation
A small example - Parse Tree after Semantic Annotation
Example run of lex calculator
Example run of yacc calculator
A larger example illustrating the Phases of Compilation
Example C program
Dictionary
Parse Tree
CS2111: Design and Implementation of Programming Languages
Pete Jinks
About this document ...
Pete Jinks
1999-09-30