(November 2009, University of Wrocław, Poland)
The course presents formal grammars
from the perspective of their original application:
specification of syntax and parsing.
The lectures were given by Alexander Okhotin (in English),
with additional seminars
by Artur Jeż (in Polish).
The list of topics presented in the course is given below.
All classes took place at the Institute of Computer Science
of the University of Wrocław.
There were 8 lectures (18 total hours) and 2 seminars (4 total hours).
The second seminar shall take place on
Saturday, November 28,
12:15, room 310.
If you have any questions,
please come to room 340 on Friday,
on Saturday or on Monday.
The examination shall take place on Monday,
in room 340 (more details below).
The preferred time is 16:15-18:00,
but if you cannot make it,
you are welcome to come at 9-12 or at 13-16.
There will be a cake after the exam.
Lecture notes for lectures 4-8 posted.
Contents of the course
Inductive definition of syntax.
Context-free grammars: definitions by equations and by rewriting.
Limitations of context-free grammars.
Extensions of context-free grammars.
Complexity of parsing.
(Tuesday, November 17, at 18:15-20:00, room 141;
Two definitions and their equivalence.
Examples of grammars.
(Wednesday, November 18, at 18:15-20:00, room 141)
Further examples of grammars.
Transformation of a conjunctive grammar to a normal form:
elimination of empty conjuncts, elimination of unit conjuncts.
Outline of the Cocke--Kasami--Younger parsing algorithm.
(Thursday, November 19, at 17:05-18:50, room 103)
Boolean grammars and their semantics.
Normal form of Boolean grammars.
The Cocke--Kasami--Younger algorithm:
the Boolean grammars edition.
(Friday, November 20, at 16:15-18:00, room 325;
The bottleneck of the Cocke--Kasami--Younger algorithm.
Parsing through matrix multiplication.
Strassen's method of multiplying matrices.
(Monday, November 23, at 16:15-18:00, room 325;
Inherently ambiguous context-free languages.
Parsing unambiguous Boolean grammars in square time.
(Tuesday, November 24, at 18:15-20:00, room 141;
Parsing context-free languages by a Boolean circuit:
the Brent--Goldschlager--Rytter algorithm.
Implementation of the algorithm on a Turing machine.
The notion of a P-complete language,
P-completeness of the circuit value problem.
A Boolean grammar for a P-complete language.
(Wednesday, November 25, at 9:15-12:00, room 310;
Recursive descent parsing for context-free grammars,
and its generalization for conjunctive and Boolean grammars.
Ensuring linear time complexity.
Limitations of the recursive descent.
Generalized LR parsing for context-free, conjunctive and Boolean grammars.
(Thursday, November 26, at 18:15-21:00, room 103;
for the first seminar
(Saturday, November 21, at 12:15, room 310).
for the second seminar
(Saturday, November 28, at 12:15, room TBA).
This is going to be an oral exam.
Each student will get
one randomly chosen theoretical topic
among those presented in the course,
and one randomly chosen problem
not harder than those considered at the seminars.
About 15-30 minutes will be given for preparation,
and then the student is expected to tell
as much as possible on that topic,
as well as present a solution to the problem.
A few additional smaller questions may be asked
and additional problems may be given.
If the resulting mark does not satisfy the student,
it may be refused,
and will in this case be omitted from the records
as if the exam did not take place.
A cake will be provided.
every student who has attended to at least one lecture
OR has successfully passed the examination
is entitled to a piece.