Home

Back

F6S spring 2010 - Syntax and Semantics

Teacher: Andrea Valente (aaue.dk/~av)

Schedule: to be decided with the students. Possibly 1 lecture every 3 topics.

Course plan:

Lecture nr: Date: Topic: Literature: Comments:

1 B209 - 3 feb - 8:15 Syntax
Introduction to the course. Sets, Strings and Languages. Deterministic Finite Automata. Chapter 0 and Chapter 1.1 [TC] and JFlap. Notes(PDF) Remember to get a copy of the booklet with selected material from:
Introduction to the theory of computation, by M. Sipser
The booklet will be referred to as [TC]

2 Syntax
Nondeterministic Automata. Relationships with DFA. Chapter 1.2 [TC], Notes(PDF)

3 B209 - 10 feb - 8:15 Syntax
Regular expressions and finite automata. Chapter 1.3 [TC] Notes(PDF)

4 Syntax
Non-regular languages. Chapter 1.4 [TC] Notes(PDF)

5 B209 - 23 feb - 12:30 Syntax
Context-free languages and grammars. Chapter 2.1 [TC] Notes(PDF)

6 Syntax
Pushdown automata. Relationships with context-free grammars. Chapter 2.2 [TC] Notes(PDF)

7 B209 - 24 mar - 8:30 Syntax
Non-CF languages. What else is there? Chapter 2.3 [TC] and whatElse
parsing, interpreter pattern slides and code

XTRA Write an OO intepreter in minutes!
A general technique (with a working example) of how to build an interpreter for an imperative programming language, starting with its grammar and its semantics. While interpreter

8 B209 - 22 mar - 8:15 Semantics
Introduction to the formal semantics of programming languages. slides8 and Chapter 1 [SA], example of semantics functions in javascript. Get a copy of the online book:
Hanne Riis Nielson, Flemming Nielson - Semantics with Applications: A Formal Introduction. (PDF)
This book will be referred to as [SA]

9 Semantics
Natural and structural operational semantics for the language While. slides9 and Chapter 2.1,2.2,2.3 [SA] Alternative discussion: Matthew Hennessy
Structural Operational Semantics is The Semantics of Programming Languages: An Elementary Introduction Using Structural Operational Semantics (PS)

10 B209 - 29 mar - 8:15 Semantics
Relationships between natural and structural operational semantics for While.
Interpreters: their construction. Meta-circulat intepreters (here) slides10

11 Semantics
Operational semantics for extensions of While. Chapter 2.4 [SA]

12 B209 - 7 apr - 8:15 Semantics
Natural semantics for blocks and procedures (While). blocks_procedures and Chapter 2.5 [SA]

13 Semantics
Axiomatic semantics. Partial correctness of programs. Loop invariants. axiomatic semantics and Chapter 6,6.1,6.2,6.3 [SA]

14 B209 - 14 apr - 8:15 Semantics
Syntax and semantics of an object-based language. oo and articles ( 1 and 2)

15 Semantics Denotational semantics, fixed-point theory (short intro). Chapter 4.1 [SA] and this handout (from here)

Department for Software, Electronics og Mediatechnology - Aalborg University Esbjerg - Niels Bohrs Vej 8 - 6700 Esbjerg - Denmark
Phone: +45 7912 7666 - Fax: +45 7912 7710

Lecture nr:	Date:	Topic:	Literature:	Comments:
1	B209 - 3 feb - 8:15	Syntax Introduction to the course. Sets, Strings and Languages. Deterministic Finite Automata.	Chapter 0 and Chapter 1.1 [TC] and JFlap. Notes(PDF)	Remember to get a copy of the booklet with selected material from: Introduction to the theory of computation, by M. Sipser The booklet will be referred to as [TC]
2	B209 - 3 feb - 8:15	Syntax Nondeterministic Automata. Relationships with DFA.	Chapter 1.2 [TC], Notes(PDF)
3	B209 - 10 feb - 8:15	Syntax Regular expressions and finite automata.	Chapter 1.3 [TC] Notes(PDF)
4	B209 - 10 feb - 8:15	Syntax Non-regular languages.	Chapter 1.4 [TC] Notes(PDF)
5	B209 - 23 feb - 12:30	Syntax Context-free languages and grammars.	Chapter 2.1 [TC] Notes(PDF)
6	B209 - 23 feb - 12:30	Syntax Pushdown automata. Relationships with context-free grammars.	Chapter 2.2 [TC] Notes(PDF)
7	B209 - 24 mar - 8:30	Syntax Non-CF languages. What else is there?	Chapter 2.3 [TC] and whatElse parsing, interpreter pattern slides and code
XTRA	B209 - 24 mar - 8:30	Write an OO intepreter in minutes! A general technique (with a working example) of how to build an interpreter for an imperative programming language, starting with its grammar and its semantics.	While interpreter
8	B209 - 22 mar - 8:15	Semantics Introduction to the formal semantics of programming languages.	slides8 and Chapter 1 [SA], example of semantics functions in javascript.	Get a copy of the online book: Hanne Riis Nielson, Flemming Nielson - Semantics with Applications: A Formal Introduction. (PDF) This book will be referred to as [SA]
9	B209 - 22 mar - 8:15	Semantics Natural and structural operational semantics for the language While.	slides9 and Chapter 2.1,2.2,2.3 [SA]	Alternative discussion: Matthew Hennessy Structural Operational Semantics is The Semantics of Programming Languages: An Elementary Introduction Using Structural Operational Semantics (PS)
10	B209 - 29 mar - 8:15	Semantics Relationships between natural and structural operational semantics for While. Interpreters: their construction. Meta-circulat intepreters (here)	slides10
11	B209 - 29 mar - 8:15	Semantics Operational semantics for extensions of While.	Chapter 2.4 [SA]
12	B209 - 7 apr - 8:15	Semantics Natural semantics for blocks and procedures (While).	blocks_procedures and Chapter 2.5 [SA]
13	B209 - 7 apr - 8:15	Semantics Axiomatic semantics. Partial correctness of programs. Loop invariants.	axiomatic semantics and Chapter 6,6.1,6.2,6.3 [SA]
14	B209 - 14 apr - 8:15	Semantics Syntax and semantics of an object-based language.	oo and articles ( 1 and 2)
15	B209 - 14 apr - 8:15	Semantics Denotational semantics, fixed-point theory (short intro).	Chapter 4.1 [SA] and this handout (from here)