A Powerful Grammar Formalism

The grammar formalism I will define in this chapter is closely related to other formalisms currently in use in computational linguistics. These formalisms are known as `unification-based', `constraint-based', `information-based' and `feature-logic based'. Members of this class are for example Definite Clause Grammars [65], PATR II [85], Functional Unification Grammar [45] and formalisms underlying linguistic theories such as Generalized Phrase Structure Grammar [23], Lexical Functional Grammar [10], Unification Categorial Grammar [113], Categorial Unification Grammar [93] and Head-driven Phrase Structure Grammar [69].

A general characterization of such constraint-based formalisms is given in [32]. They also show how the nice properties of logic programming languages carry over to a whole range of such constraint-based formalisms, by abstracting away from the actual constraint language that is used. I define such a constraint-based formalism in which the underlying constraint language, , consists of path equations. The most important characteristics of the formalism are:

- The formalism consists of definite clauses, as in Prolog; instead of
first-order
*terms*the data structures of the formalism are*feature structures*. - The formalism does not assume that concatenation is the sole string-combining operation (in contrast to FUG, DCG, PATR II, LFG, GPSG and UCG).
- The formalism is defined in an abstract framework, which facilitates the extendability of the techniques I develop in later chapters, to formalisms based on other (more powerful) constraint-languages.

Firstly, the principal `data-structures' of the formalism are feature structures, rather than first-order terms such as in Prolog. The motivation is that such feature structures are closer to the objects usually manipulated by linguists. Furthermore, in writing grammars the use of first-order terms becomes rather tiresome because it is necessary to keep track of the number of arguments functors take, and the position of sub-terms in such terms. Using path equations to define feature structures achieves some sort of data abstraction. As an example consider a program which manipulates terms such as the following

and suppose furthermore we want to refer to a specific part
Cat of
such a term
T. In Prolog we are then forced to mention all
intermediate functors, and for each functor we need to mention all its
arguments (possibly using the `anonymous' variable `_'):

On the other hand, using path equations, it is possible to refer to
such an embedded term by its *path*, in this case
the value of
Cat is obtained by the equation
Cat
T *syn* *head* *cat*.

This said, it should be stressed though that the difference between
the two approaches is not very decisive. In fact first-order terms may
be used in an implementation of such graph-based formalisms
[29], and data-abstraction can also be achieved by other
means such as syntactic macro's, or by auxiliary predicates.

From a linguistic point of view, the second characteristic is the most salient one. The formalism to be proposed, does not enforce that concatenation is the sole operation to combine strings. This choice can be motivated by:

- Increased symmetry of parsing and generation
- Increased expressive power
- Other applications

If we do not incorporate a concatenative base, then we allow for investigation of other types of string combinations in natural language grammars. Several researchers, see for example [8], [67], [71] and [15], have noted that analyses of a whole range of linguistic phenomena (most notably those involving discontinuous constituents) may be simplified by assuming other types of string operations. Some of the proposals are discussed in chapter 4.

As I will demonstrate below, if no assumptions about the construction
of phonological representations, or semantic representations, are
defined, then the parsing and generation problem of the formalism is
generally not decidable. An important theme of this thesis is, to
investigate parsing and generation procedures which can be applied
usefully, for linguistically motivated grammars. In
chapter 4 I describe a parsing algorithm for a subset of
(), in which strings are constructed by operations which are to
*linear* and *non-erasing*. This algorithm thus imposes some
requirements on the ways strings are built, but these requirements are
less restrictive than concatenation.

Another reason for developing a formalism which is not based on
concatenation is the observation that other (non-linguistic) problems
can be encoded in a unification-grammar as well, if we are not forced
to manipulate strings. In chapter 5 I show how the
resulting formalism can be used to define relationships between
language specific logical form encodings (chapter 5), as
the transfer component of a machine translation system. Furthermore,
the formalism is also used to define meta-interpreters in -- this
usage of the formalism also entails that no assumptions about string
construction are built-in.

The third characteristic states that the resulting formalism is a member
of a class of constraint-based formalisms.
Therefore, results that hold for this class carry over to the present
formalism. In the other direction, it is easy to see how the current
formalism can be *extended* to allow for other, perhaps more
complex constraints. This is very useful as in the last few years a
whole family of different constraints have been proposed that do
extend formalisms such as PATR II. An overview of these proposals can
be found in [109]. The formalization of
[32] makes it possible to see how these extended
formalisms belong together. In a somewhat idealized view,
parsing and generation algorithms defined for a member of the
class of constraint-based formalisms, can be used for other members of
this class, provided the appropriate *constraint-solving*
techniques are available for the constraints incorporated in these
other formalisms. For example, the generation- and parsing algorithms
to be presented in the chapters 3 and 4,
can easily be used for formalisms that include versions of negation
and disjunction.

- The constraint language:
- Adding definite relations
- Procedural Semantics
- Parsing and generation
- Post Correspondence problem
- Conclusion

1998-09-30