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 $\S$ 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
- 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
- Puns: similar representations with 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
- 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
- Language Independant Datatypes
- C
- SML
- Language design and implementation
- Readings
Composite Types
- Common Composite Types
- 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
- 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