Lecture Notes

Notes (handout)	Notes (overhead presentation)	Resources
History	History	N/A
Functional programming	Functional programming	functional programming section 1
Logic programming	Logic programming	logic programming 2
Imperative models	Imperative models
Scanning and parsing - a reminder	Scanning and parsing	scanning and parsing
Semantic analysis	Semantic analysis	semantic analysis
Types and classes	Types and classes	types and classes
Subprograms	Subprograms	subprograms
Pointers, references, and memory management	Pointers, references, and memory management	pointers

Lecture recording

My lectures are recorded, as follows:

• The introduction (Lecture 1) was not recorded.
• History: Lecture 2
• Functional programming: Lecture 3, Lecture 4, Lecture 5, Lecture 6 (recording started a few minutes late), Lecture 7, Lecture 8
• Logic programming: Lecture 9, Lecture 10, Lecture 12
• Imperative models of computation: Lecture 13
• Lexical analysis (overview): Lecture 15
• Parsing (overview): Lecture 16
• Semantic analysis: Lecture 17, Lecture 18 (only the first about 45 minutes of the lecture were recorded), first about 40 minutes of Lecture 19 (which also includes about 8 minutes on Prolog programming and high-level programming languages in general)
• Types and classes: rest of Lecture 19, Lecture 20, first about 30 minutes of Lecture 21
• Subprograms: rest of Lecture 21, first about 45 minutes of Lecture 22
• Pointers: rest of Lecture 22, Lecture 23
• No recording of Lecture 24 is provided since it does not contain useful information.

A simple parser example

Consider these two figures. Figure 1 shows the grammar of a simple yet pretty realistic programming language. The possible token types are shown in the figure as capitalized words, parentheses, and operators. Note that the actual lexemes for the tokens IF, ELSE, WHILE, and BREAK are all in lower case. BASIC types are bool, int, char, and double.

We now aim to construct a recursive descent parser for this grammar. In order to do that we must convert the grammar in a form that is suitable for recursive descent parsing. The result is shown in Figure 2.

We can then proceed with the development of a recursive descent parser. The result is parser.cc. The input (program to be parsed) is read from the standard input stream. The output is a printout of the respective parse tree, produced to the standard output stream. Note that the parser is simplified as much as possible. In particular the lexical units in the language are separated by blank or newline characters (so that the lexical analysis does not need to use finite automata).

Footnotes

...¹

Here are some possibly interesting Haskell programs (with types): expressing dates and binary search trees.

...²

Here is a definition of binary search trees in Prolog: bst.pl.