|
Courses and Workshops
|
| Title: | Introduction to parsing algorithms for NLP |
| Lecturer(s): | Giorgio Satta (University of Padua) |
| Type: | Introductory Course |
| Section: | Language and Computation |
| Week: | First | | Time: | 9.00-10.30 (Slot 1) |
| Webpage: | http://www.dei.unipd.it/~satta
|
| Reader: | Download | | Room: | A3 |
Description This course is an introduction to tabular algorithms for context-free
grammar parsing, with particular attention to those algorithms that
are currently used in natural language processing. We will cover
basic techniques as shift-reduce (bottom-up) and predict-shift
(top-down), along with standard algorithms as Coke-Kasami-Younger,
Earley, Graham-Harrison-Ruzzo, Left-Corner and generalized LR (Tomita
algorithm).
Theoretical, computational and implementational aspects of the above
tabular methods will be taken into account. The basic approach that
will be adopted is to view tabular parsers as developed by means of
the specification of a nondeterministic push-down automaton, which is
then simulated through dynamic programming techniques, following the
approach first proposed by Bernard Lang (1974). This framework
favours direct comparison of parsing algorithms, makes their
implementation easier, and provides a theoretically grounded approach
to the development of new parsing methods.
The course will be addressed to students with basic knowledge about
formal languages and computer algorithms. Course material will be
based on the draft of a book about parsing algorithms that the teacher
is writing in collaboration with Mark-Jan Nederhof.
|
© 2003, 2004 LORIA, Carlos Areces. |
2003-11-25
| |
