# Logical Methods in NLP, Spring 2005

## General Course Information

Lectures

Lectures take place Tuesday mornings, 11.15 -- 13.00, in room 131 of Kromme Nieuwegracht 80.

Lecturer (for the first part of the course, at least): Jan van Eijck. Teaching assistant is Matteo Capelletti.

Course material

Practice sessions

Practice sessions take place Thursday, 9.15 -- 11.00, in room 131 of Kromme Nieuwegracht 80.

Computer Lab sessions

Computer lab sessions take place on Thursday, 11.15 -- 13.00 in room 108 CL of Kromme Nieuwegracht 80.

Homework Assignments

You will be asked to hand in homework assignments as the course progresses. Each homework assignment has a deadline. Handing in your homework assignments on time is a necessary condition for taking credit for the course.

## Specific course information

3/5:

• Lecture: very brief introduction to Haskell. Slides are here.
• Haskell code from the slides is here.
• Lecture: first steps in parsing as deduction. Paper of Shieber, Schabes and Pereira is here.

10/5:

• Parsing as deduction: (i) the CYK algorithm, (ii) the recursive descent (top-down) algorithm, (iii) the shift/reduce (bottom-up) algorithm, (iv) Earley's algorithm.
• Earley's paper An efficient context free parsing algorithm.

12/5:

• Practice session: pen and paper exercises with Haskell. The following exercises from Chapter 1 of The Haskell Road to Logic, Maths and Programming: 1.9, 1.10, 1.13, 1.14, 1.15, 1.17.
• Lab session: try out your solutions to 1.9, 1.10, 1.13, 1.14, 1.15, 1.17. Next, solve 1.18 and 1.19.
• In Earley.hs you will find an implementation of the deductive version of Earley's parsing algorithm. A function for stand-alone use of the parser is parse.hs. Try this out, by trying to parse expressions with the example grammars below. The parsing command is

runhugs parse grammar0 'a b'

or

runhugs parse grammar4 'John hated the man that Mary loved'

Next, try to understand the code of Earley.hs and parse.hs. (Further explanation next week.)

• Example grammars: grammar0, grammar1, grammar2, grammar3, grammar4.
• Write your own grammar for a fragment of Dutch (or for your favorite language) and parse it with the Earley algorithm. Make sure the program can read your grammar file.
• Homework: solutions to 1.20 and 1.21, plus your example grammar. Email these to Matteo Capelletti with a cc to Jan van Eijck. Deadline Tuesday 17/5, before the lecture.

17/5:

• Lecture: Lists, lambdas and databases. Course slides are here.
• Haskell code from the slides is here.
• Further explanation of the Haskell implementation of Earley's parsing algorithm. A slightly extended version of the algorithm, with documentation is here. A proof of your understanding is requested in the homework assignment for this week.
• Parsing with mildly context sensitive grammar formalisms: preview only. More info next week.

19/5:

• Practice session: pen and paper exercises with Haskell. Discussion of last week's homework, plus the following exercises from Chapter 4 of The Haskell Road to Logic, Maths and Programming: 4.44, 4.48, 4.49, 4.50.
• Lab session: try out your solutions to 4.44, 4.48, 4.49, 4.50. You will need the code for Chapter 4 of the textbook; it can be found here.
• Homework: use the Haskell code for the Earley parsing algorithm as a starting point to implement your own Recursive Descent parsing algorithm, using the Shieber/Schabes/Pereira recipe. Consult the Haskell documentation if you run in trouble with Haskell syntax. Make sure that your program works by trying it out with a few example grammars. Call the file RecursiveDescent.hs and email it to Matteo Capelletti with a cc to Jan van Eijck. Deadline Tuesday 24/5, before the lecture.

24/5:

• Parsing with sequentially indexed grammars. The course slides are here.
• A paper version with a documented program for parsing with sequentially indexed grammars is here.
• Haskell code of this program is here.
• Induction and recursion: chapter 7 from The Haskell Road to Logic, Maths and Programming, sections 2 and 3.

26/4:

• Practice session: pen and paper exercises with Haskell. Discussion of last week's homework, plus introduction to the notion of recursion on trees (Section 7.4 of The Haskell Road to Logic, Maths and Programming). Exercises from Chapter 7 of the book: a selection from 7.14, 7.16, 7.28, 7.29, 7.30, 7.34, 7.36, 7.37.
• Lab session: try out your solutions to the exercises in the list 7.14, 7.16, 7.28, 7.29, 7.30, 7.34, 7.36, 7.37 that you understand. You will need the code for Chapter 7 of the textbook; it can be found here.
• Homework: 7.33. Email your solution to Matteo Capelletti with a cc to Jan van Eijck. Deadline Tuesday 31/5, before the lecture.

31/5:

2/6:

• Combined practice session and lab session in the computer lab room, starting at 10 am. Recursion in list processing exercises from the book: 4.51, 4.53, 7.46. Further exercise: write your own version of nub.
• Parser combinators: write a parser for a small natural language fragment using the parser combinators given here.
• Homework Write a parser for a small natural language fragment using the Parsec library. Email your solution to Matteo Capelletti with a cc to Jan van Eijck. Deadline Tuesday 7/6, before the lecture.