Formal grammars

(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).


Contents of the course

  1. 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; slides)
  2. Conjunctive grammars. Two definitions and their equivalence. Examples of grammars. (Wednesday, November 18, at 18:15-20:00, room 141)
  3. 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)
  4. 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; lecture notes)
  5. 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; lecture notes)
  6. Unambiguous grammars. Inherently ambiguous context-free languages. Parsing unambiguous Boolean grammars in square time. (Tuesday, November 24, at 18:15-20:00, room 141; lecture notes)
  7. 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; lecture notes)
  8. 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; lecture notes)


  1. Homework for the first seminar (Saturday, November 21, at 12:15, room 310).
  2. Homework 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. Eligibility criterion: every student who has attended to at least one lecture OR has successfully passed the examination is entitled to a piece.