Introduction.Suggested exercises: install a Prolog interpreter on your computer and run the example that we have seen in class. Can you simplify that program to obtain the same effect?
Lectures and problem classes in Semester 1:
Lectures and problem classes in Semester 2:
A good Prolog textbook, which I suggest to buy and of which two copies are in the library, is:
Excellent lecture notes:
Prolog Programming and Unification by Paola Bruscoli.
A good textbook on compilers, which I suggest to buy and of which seven copies are in the library, is:
Some slides extracted from the textbook: about Lex, LR(1) parsing and Yacc.
A standard reference for compilers is:
Another recommended textbook is:
Yiannis Demiris has good material on compilers for his course at Imperial.
16.11.11—Lecture 1Introduction.
Suggested exercises: install a Prolog interpreter on your computer and run the example that we have seen in class. Can you simplify that program to obtain the same effect?
18.11.11—Lecture 2Procedure definitions and calls, success and failure, search tree.
Suggested exercise: write a program whose search tree has one failure and two success branches at the left of an infinite branch, and try it on your Prolog interpreter.
22.11.11—Problem Class and Lecture 3Exercises on search trees, answers as consequences, variable arguments, introduction to unification.
23.11.11—Lecture 4Prolog terms and lists.
Suggested exercise: write a deterministic Prolog program that recognises the lists generated by the regular expression (a.b*.b)*.
25.11.11—Problem Class 1Solution to the exercise given on 23.11.11 and discussion.
Suggested exercise: write a deterministic Prolog program that recognises the lists generated by the regular expression (a.b*.b)* and also generates all of them. This means that when invoked with a variable, the program generates every string in the language after a finite number of redos (semicolon). Do not use any special Prolog primitive, including numbers. Just use lists and the basic search tree mechanism.
29.11.11—Lecture 5List append, more on matching, binding environment.
Suggested exercises: please do (really!) the exercise suggested last week, plus design a program that reverses a list and allows for mixed input/output.
2.12.11—Problem Class 2Solution to the exercise given on 25.11.11.
Suggested exercise: try to understand the solution, which I sent you via email, and report to me any errors or suggestions for improvement.
6.12.11—Lecture 6Unification.
Suggested exercise: apply the hint given in class to simplify the program I sent you last time.
7.12.11—Lecture 7Examples of unification, several Prolog built-ins, the cut.
Suggested exercises: Unify f(X,Y,Z) and f(a,Z,h(a)); f(g(X),g(c),Y) and f(g(g(Y)),X,a); f(g(X),g(Z),Y) and f(g(g(Y)),g(X),Z); f(g(X),Y,h(Z)) and f(U,W,U); f(a,X,g(h(Y))) and f(Z,i(Z,W),g(W)); f(X,X,Y) and f(g(Y),g(g(Z)),g(a)). Program yourself all the procedures in the List Processing part of the slides.
9.12.11—Lecture 8Examples of unification, examples of use of cut, findall.
Suggested exercise: Use Prolog to solve the following problem. Let X and Y be two integers with 1 < X < Y and X + Y ≤ 100. The mathematician S is given their sum X + Y and the mathematician P is given their product X * Y. All this is known to S and P. The following conversation now takes place:
P: I do not know the two numbers.
S: I knew that you didn't know the two numbers.
P: Now I know the two numbers.
S: Now I know the two numbers.
What are the numbers?
13.12.11—Lecture 9Improvement to the solution of the (a.b*.b)* problem. Disjunction, negation.
Suggested exercise: Write a program that generates a list of integers from 1 to 100, then write a program that generates (X,Y) couples such that 1 < X < Y and X + Y ≤ 100.
14.12.11—Problem Class 3Solution to the exercise given on 13.12.11.
16.12.11—Lecture 10 and Problem ClassMore on negation, generate and test, forall and an exercise on bubblesort.
Suggested exercise: Write a program for quicksort.
6.2.12—Problem Class 4Discussion on the sum/product problem.
8.2.12—Problem Class 5Discussion on generating lists of numbers.
10.2.12—Problem Class 6Discussion on quicksort.
13.2.12—Lecture 11Introduction to compilers.
15.2.12—Lecture 12Bootstrapping a compiler. Introduction to languages for scanning and parsing.
17.2.12—Lecture 13Regular expressions, grammars and their classification.
20.2.12—Problem Class 7 and LecturePermuting and scanning lists in Prolog. Regular grammars.
Suggested exercise: give regular grammars for the regular expressions in Exercise 2.2 of the textbook.
22.2.12—Lecture 14Context-free grammars vs. regular grammars, derivations, parse trees, ambiguous grammars, the parsing problem.
Suggested exercises: 2.3, 2.4, 2.5 of the textbook.
24.2.12—Lecture 15Lexical analysis: symbol recognition via regular expressions and automata.
Suggested exercises: 3.4 and 3.6 (using Prolog instead of C) of the textbook.
27.2.12—Lecture 16Lex.
29.2.12—Lecture 17Top-down parsing and introduction to LL(1) grammars.
Suggested exercise: find a context-free grammar for a*b* that only requires one lookahead symbol to disambiguate production usage in top-down parsing.
2.3.12—Lecture and Problem Class 8Definition of LL(1) language. Question: is a regular language LL(1)? Exercise on aa*bb*: automaton and regular grammar.
5.3.12—Lecture 18Top-down parsing: factorisation, removal of left recursion and recursive descent.
Suggested exercise: By using the method of recursive descent, write in Prolog a top-down parser for the following LL(1) grammar:
Can you simplify this grammar, and the corresponding program, by keeping it LL(1)?
7.3.12—Lecture 19Bottom-up parsing: introduction to LR(k) parsing and the parse table.
Suggested exercise: go through every detail of the example in Section 5.3 of the textbook (provided in class as a handout).
9.3.12—Lecture 20Bottom-up parsing: how to build a parse table.
Suggested exercise: go through every detail of the examples in Section 5.4 of the textbook (provided in class as a handout).
12.3.12—Problem Class 9Derivation and use of an SLR(1) parse table.
14.3.12—Lecture 21Properties of LR languages and grammars. Introduction to Yacc.
In Endriss's lecture notes:
In Bruscoli's Prolog Programming slides:
Slide 14 in Bruscoli's Unification slides (note that the lowercase x's are variables).
In Hunter's The Essence of Compilers:
When you want to talk to me, just send me an email and we'll arrange for an appointment.
14.3.2012Alessio Guglielmiemail (replace AT by @)