In this paper we are concerned with the syntactic analysis phase of a
speech analysis system. The input for the syntactic analysis phase
in such a system is a *word lattice*, and the output is a packed
representation of all possible parse trees. Syntactic analysis is
performed on the basis of some grammar *G*. Following Bernard Lang we
can thus characterize the syntactic analysis phase as the computation
of the intersection of a finite state automaton (the word-lattice) and
the grammar *G*. This intersection is a grammar that derives exactly
all parse trees for the input.

Note that we allow the input to be a full FSA (possibly including cycles, etc.) in order for certain techniques to handle ill-formed input to be applied. Whereas an ordinary word-graph always defines a finite language, a FSA of course can easily define an infinite number of sentences.

It can be shown that the computation of the intersection of a FSA
and a CFG requires only a minimal generalization of existing parsing
algorithms. We simply replace the usual string positions with the
names of the states in the FSA. It is therefore straightforward to
show that the complexity of this process is cubic in the number of
states of the FSA (in the case of ordinary parsing the number of
states equals *n* + 1) [4,2] (assuming the grammar is
in bilinear format).

In this paper we investigate whether the same techniques can be
applied in case the grammar *G* is a constraint-based grammar rather
than a CFG. For specificity we will take *G* to be a *Definite
Clause Grammar* (DCG) [5]. A DCG is a simple
example of a family of grammar formalisms that are widely
used in natural language analysis (and generation).
The main findings of this paper can be extended to the other members
of that family of constraint-based grammar formalisms.

1998-09-29