|
Courses and Workshops
|
| Title: | Basic parsing techniques for natural language |
| Lecturer(s): | Bertrand Gaiffe (LORIA) and Guy Perrier (LORIA) |
| Type: | Foundational Course |
| Section: | Language and Computation |
| Week: | Second | | Time: | 14.00-15.30 (Slot 3) |
| Webpage: | http://www.loria.fr/~perrier/
|
| Reader: | Download | | Room: | A1 |
Description The aim of this course is to introduce beginners to fundamental parsing
techniques and conceptual tools applied to formal grammars.
Lecture 1: Context-free grammars
Context free grammars are almost the simplest possible means to
describe natural languages. In this first course, we present context
free grammars as devices dedicated to generating trees. We then show
how the result of the parsing of a sentence with a CF grammar is
naturally expressed as a CF grammar. This leads us to the notion of
intersection between a CF grammar and a string to parse. We then
present basic parsing algorithms and show how the result grammar is
extracted from the chart obtained.
Lecture 2: Feature structures
In this second course, we introduce (untyped) feature structure as
information structures. We present both the notations for feature
structure (the syntax) and the associated models (direct acyclic
graphs). We conclude with the two important notions of subsumption and
unification of feature structure.
Lecture 3: Unification grammars
This third course aims at combining context-free grammars and feature
structures. We begin with equations associated to a context free
skeletton. We then generalize to unification grammars with feature
structure as non-terminals. The algorithms of the first course are
generalized to take those grammars into account. Of course, we insist
in this course on the undecidability of the recognition problem for
unification grammars in general and show some cases where the probelm
is decidable.
Lecture 4: Parsing with polarities
The notion of polarity aims at capturing the resource sensitivity of
natural languages : syntactic constituents are viewed as available and
expected resources that seek to neutralize mutually. By integrating
this notion in unification grammars, syntactic composition can be
presented as a mechanism of tree superposition controlled by
polarities. This paradigm is illustrated by a new presentation of
Categorial Grammars, more precisely their original kernel: AB
Grammars. The advantages and the limitations of this paradigm are
explored through the modelling of various linguistic phenomena.
Lecture 5: Underspecification and tree descriptions
The capability of linguistic formalisms to model underspecification is
crucial for expressing linguistic generalizations and factorizing
grammatical information. A way of introducing underspecification in
the paradigm of the previous lecture is to replace trees with tree
descriptions as basic syntactic objects. A tree description is a set
of constraints defining a family of syntactic trees, so that grammars
appear as constraint systems and parsing a sentence reduces to solving
a constraint satisfaction problem. This new point of view is
illustrated by revisiting Lambek Grammars, the usual kernel of
Categorial Grammars. Its linguistic relevance is tested through
examples of modelling linguistic phenomena.
The course need no prerequisite and the authors have taught this
material for several years at the University of Nancy. The course design
and materials are based on this experience.
|
© 2003, 2004 LORIA, Carlos Areces. |
2004-07-07
| |
