Bi-Directional Parsing for Natural Language Processing

Giorgio Satta
Dipartimento di Elettronica ed Informatica
Universita` di Padova, Italy
October 24, 1995

While natural language is usually analyzed from left to right, bi-directional
parsing is very attractive for both theoretical and practical reasons.
In fact bi-directional parsing can exploit head information as early
as possible, thus reducing local ambiguities in the input sentence,
and prove useful in cases of ill-formed or ``noisy'' input,
again reducing the amount of nondeterminism that needs to
be simulated by a deterministic algorithm.

Pursuing the approach based on grammar covers, first proposed
in (Leermakers, 1989), I will develop a uniform framework
that offers a systematization of bi-directional parsing and facilitates
the design and the analysis of new parsing algorithms for these strategies,
when dealing with phrase rewriting systems based on a context-free backbone.
Some algorithms for head-driven and island-driven parsing will be presented.
In the head-driven algorithms, the syntactic analysis of a constituent
is always triggered by some fixed element within it,
chosen on the basis of its information content.
In the island-driven algorithms, syntactic analysis starts
from any dynamically chosen positions within the input sentence,
combining bottom-up and top-down processing without redundancy.


(Joint work with Mark-Jan Nederhof and Oliviero Stock)
Seminar Schedule