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.
Course participants