Next:
Introduction
CS2121: The Implementation and Power of Programming Languages
Pete Jinks pjj@cs.man.ac.uk
October 26, 2004
Introduction
From some viewpoint, differences vanish
What doesn't fit?
So what?
What are we actually going to do in CS2121?
Two halves make a whole
Epilogue
Exercises
Readings - missing
Representation and Meaning
Expressions
Implementing Programming Languages
Implementing Representation - Dealing with Grammars
GREP
and
EGREP
LEX
and
YACC
Parse trees
Epilogue
Exercises
Readings
LEX
Postfix calculator in
LEX
Descriptions of expected inputs
grammar rules from
2.1
LEX
definitions
Actions, C declarations and code
How
LEX
is used
Epilogue
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
Epilogue
Exercises
Readings
YACC
: Further usage
Grammar rules
sequence
invoke
choice
optional
repetition (1 or more)
optional (0 or more)
Left and right recursion
Getting actions in the right order
Precedence and associativity
Grammatical errors: handling incorrect inputs
Epilogue
Exercises
Readings
How lexers (e.g. from
LEX
) and parsers (e.g. from
YACC
or J
AVA
CC) work
Lexers - Finite State Automata (FSA)
Parsers - Deterministic Push Down Automata (PDA)
Top-Down Parsers
Bottom-Up Parsers
A more detailed look at
YACC
parsers
Epilogue
Exercises
Readings
Ambiguous and confusing grammars
Ambiguous grammars
How to confuse parsers
Confusing
YACC
An example of a shift/reduce conflict
An example of a reduce/reduce conflict
Epilogue
Exercises
Readings
Parse Trees
Language design and implementation
Passes
Concrete and Abstract
Building parse trees for expressions
Epilogue
Exercises
Readings
Variables and Types
A simple example
Multiple types
Compilers and interpreters
Declarations
Compile-time visibility - Scope
Run-time memory - Stack frames
Implementing scope - Dictionary
User-defined types and classes
Epilogue
Exercises
Readings
Composing Programs
LEX
and
YACC
Chomsky's classification of grammars
Rewriting programs to only use Repetition and Choice
e.g. a single function
e.g. simple function call
e.g. function call allowing for recursion, parameters, local variables etc.
Epilogue
Readings
Putting it all together
When to use a tool or technique
What are the components of a Compiler
Lexical analysis (itemisation, scanning, tokenisation)
Syntactic analysis (parsing)
Semantic analysis
Code generation
How to combine components, tools and techniques - Passes
A typical 1-pass organisation
A typical multi-pass organisation
Epilogue - Syntax-directed Translation
Exercises - missing
Readings
Phases of Compilation
A small example C program being analysed
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
Left and Right recursion
More examples of Ambiguous and confusing grammars
Ambiguous expressions
A deliberately confusing example
More examples of shift/reduce and reduce/reduce conflicts with
YACC
An example of a reduce/reduce conflict
An example of multiple shift/reduce conflicts
A longer example, with shift/reduce and reduce/reduce conflicts
About this document ...
Pete Jinks
2004-10-26