Incremental Syntactic and Semantic Processing

1 Introduction

The construction of a semantic representation for a nat­ ural language sentence involves at least the three steps of

1. "compositional" semantics (constructing a semantic form by the use of ,8-conversion)
2. determining the scopes of the quantifiers
3. anaphora resolution

The most obvious sequential order of the three steps, which causes the least technical problems for the implementation, is the one given above ( cf. [Kamp and.Reyle, 1991, Asher and Wada, 1988]). But there are also proposals to merge these operations during processing. [Johnson and Klein, 1986] describe how discourse representation structures (DRS's, see [Kamp and Reyle, 1991]) are constructed during the syntactic processing and how anaphora resolution can be integrated into this construction process 1 . However, they ignore the problem of generating different quanti­ fier scopings. In [Johnson and Kay, 1990], the second phase of the construction of semantic representations (i.e. the generation of quantifier scopings) has been in­ cluded into the construction procedure where a Definite Clause Grammar (see e.g. [Clocksin and Mellish, 1987]) serves as the syntactic basis.

*This research ha.s been ma.de possible by a. Monbusho­ schola.rship (Japanese Ministry of Education). I wish to thank Ma.koto N a.ga.o, Yuji Matsumoto, and the two anony­ mous referees. The responsibility for errors resides with me.

Pereira describes the integration of compositional se­ mantics, quantifier scope generation, and anaphora res­ olution on an abstract level [Pereira, 1990]. The key idea is that not only one half of a functional calcu­ lus should be used, which is the functional applica­ tion operation (,8-conversion) but that the other half, i.e. functional abstraction deserves to be taken un­ der consideration, as well. Functional abstraction, so to speak, allows for hooking up the compositional se­ mantics with the contextual information. The context of an utterance can be considered as a set of addi­ tional assumptions which help to derive the current sen­ tence [Pollack and Pereira, 1988]. Additional assump­ tions have to be "discharged" after successful derivation in order to perform a sound reasoning. The discharg­ ing of assumptions is exactly the task of functional ab­ straction. Thus, a broadened view on compositionality can be taken. In particular, Pereira's suggestions imply that the mechanisms for dealing with contextual infor­ mation no longer are mere procedural appendage of the logically well-understood step of compositional seman­ tics but that these mechanisms are part of the logical system which specifies how to construct a semantic rep­ resentation for a sentence (or a text).

In the following, we investigate how Pereira's sug­ gestions can be implemented in the framework of the currently fashionable lexicalized approaches to grammar [Pollard and Sag, 1987, and many others], in our case a basic categorial grammar 2 .

1 Simila.r approaches have been implemented by other peo­ ple, see e.g. [Geurts, 1990].

2 Ba.sic ca.tegoria.l grammars are a subsystem of Combina­ tory Categorial Grammars, see e.g. [Steedman, 1989] .

2 The construction calculus

An abbreviated version of Pereira's construction calculus is given in figure 1 in a modified notation which allows to turn it easily into a parsing algorithm. Thus, instead of semantic types, we use syntactic ones (i.e. those of categorial grammar). We assume that a proposition is a pair which consists of a syntactic category X; and a (partial) semantic representation S; (a special case are variables u;). The symbols quant and pron are distin­ guished categories which designate "stored" quantified expressions and pronouns respectively 3 . The partial se­ mantic representation of a quantified phrase is prefixed by the variable u; which is bound by its main quantifier.

as a hypothetical proposition with category quant. In the quantifier abstraction rule ( absq) such a hypothesis is discharged, i.e. the quantified expression is removed from the store and applied to an intermediate parse result. The pronoun licensing rule (licp) transforms a pronoun into a regular noun phrase which can be used in the sub­ sequent derivation. The initial pron-proposition is con­ sidered as a hypothetical one, which has to be discharged by applying the pronoun abstraction rule ( absp) to per­ form anaphora resolution. A derivation is successful if all stored quantified expressions and all pronouns have been discharged. For more details see [Pereira, 1990].

The application rules (app\) and (appl) perform the purely compositional part of the construction of a seman­ tic representation. The quantifier licensing rule (licq) "stores" the semantic form of a quantified noun phrase Figure 2 shows the derivation of the sentence "he ordered a beer" under the assumption that the pre­ ceding sentence reads "a man entered." Instead of con­ structing a traditional predicate logic formula, a dis­ course representation structure (DRS) is built. A DRS is either a pair of a list of discourse referents and a list of conditions, or a two-place term with functor"::}" and two DRS's as arguments. Intuitively, an undischarged quantified expression corresponds to what is meant by

3 For the sake of simplicity we assume that pronouns are the only kind of anaphoric expressions, and that anaphora can only take quantified expressions as their antecedents.

Figure 3: Modified construction calculus - accumulation method

the term accessible discourse referent in Discourse Rep­ resentation Theory. If a quantified expression is still undischarged at a certain node in a derivation tree, the~ its scope covers at least the phrase at the leaves of thiS subtree.

3 Implementation issues

In the following, we explain how the construction calcu­ lus can be implemented. Nevertheless, we will stick to the natural deduction format to represent various pos­ sible algorithms. Because of the similarity of. natural deduction rules and Horn clauses (several premiSes and one conclusion), a Prolog implementation can be derived in a straightforward way.

The construction calculus in definition 1 is not yet a specification of an efficient algorithm. A theorem prover which is derived from this definition has to exploit the pecularities of the individual rules in order to increase the efficiency. One of its main tasks is to keep track of the additional propositions which are brought into the derivation by the licensing rules. We will focus on the handling of the set of undischarged quantified expres­ sions. In order to ease the access, they have to be put into a separate data structure.

3.1 Accumulation method

The most obvious method is to simply accumulate the information about undischarged quantified expressions starting from the leaves of the tree. For this purpose, propositions are now indexed by a set Q of_undischarged quantified expressions (or to be more efficient, by a set of pointers to undischarged quantified expressions):

Set union and set membership is indicated by a comma. Lexical entries are assumed to come with empty sets. In the application rules the quantifier sets of the two daughter are simply combined. The quantifier licensin~ rule adds a quantified expression to the set, the quanti­ fier abstraction rule removes an element. The pronoun manipulation rules do not change the set. Figure 3 shows the revised calculus.

The suggested flow of data makes clear that under certain circumstances anaphora can be resolved before the quantifier scopes in a sentence have been completely determined. In the example

"Every man who loves a woman follows her to some country."

the pronoun "her" may find its antecedent before the relative scopes of the quantifiers "every" and "some" are known.

3.2 Threading method

If we assume that we are dealing with anaphora only, i.e. that cataphora do not occur, a further change of the data structure will allow for a slight simplification of the calculus. Anaphora want to know their left con­ text therefore it is sufficient to collect information from ' . . left to right in the well-known manner of mformat10n "threading". Information is not only accumulated from the leaves towards the root of a derivation tree, but prop­ agated down to the leaves which are located further right than the nodes where the information was originated.

Each constituent can be characterized by the states of the set of accessible quantified expressions before and after it has been derived. Hence, each proposition will be indexed by two sets Q1 , Q2 of undischarged quantified expressions:

The set Q1 is the input set, and Q2 the output set. The similarity to difference lists in Prolog is not accidental. For lexical entries, the input and the output sets are equal. The input set of the first word of a sentence mi~ht either be empty or equal the output set of the precedmg sentence. The newly revised calculus is presented in fig­ ure 4. An application rule connects the output set of its left premise with the input set of the right premise. The output set of the conclusion of the quantifier licensing rule contains one element more than the output set of its premise; for the quantifier abstraction rule, the in­ verse relation holds. The rules (licp) and (absp) would read in the "threading" notation:

Figure 4: Modified construction calculus- threading method

However, a quantified expression can only qualify as a potential antecedent of an anaphor if it occurs in the left context of the anaphor, i.e. if the quantified expression is a member of the input set of the anaphor. Hence, the pronoun can access directly the set of its potential antecedents without making reference to a larger subtree of the derivation. The combined rule must perform the two tasks of the original rules (licp) and (absp) which are the formation of a result proposition (np : u) and the substitution of the variable up by the variable u 9 :

The modified rule works fine on the logical level. It will cause problems with the processing, because, in gen­ eral, the input set will not be instantiated at the moment when the pronoun is encountered by the parser. The search in the set of possible antecedents has to be frozen as long as the variable which represents the set is still uninstantiated. The task of waiting until the appropri­ ate part of the derivation has been built up is delegated to an underlying mechanism instead of mentioning it ex­ plicitly in the rule (absp)· In the framework of concur­ rent logic programming languages, which provide a sus­ pension mechanism, the set of undischarged quantified expressions may be considered as a stream.

Since we presented the algorithm in the natural de­ duction format, one might assume that there are the usual structural roles silently working in the background. However, for a parser, the presence of the structural rules is harmful. Propositions should not be arbitrarily omitted, duplicated or permuted. The weakening role which allows for the omission of premises will be never needed unless vacuous abstraction is considered a legal phenomenon. In the case of the original construction cal­ culus, the task of the permutation role is to guarantee the arbitrary access to the quant- and pron-propositions. A first step has been done by representing the "syntactic" propositions and the purely semantic ones in two differ­ ent data structures. In the threading method, the need for a separate data structure for the undischarged pro­ nouns has disappeared, since pronoun licensing and pro­ noun abstraction have been merged into one rule. Only for the handling of the list of undischarged quantified expressions, the permutation rule must be available in order to turn the list into a set. Hence, the permuta­ tion rule need not be used in the calculus itself. The contraction role does its work tacitly to prepare the way for applications of the rule (pron). Obviously, a quantified expression might serve as the antecedent of several pronouns. This is the only the case where the use of a structural rule cannot be eliminated. But fortunately, by coupling it with the responsible rule (pron), the prop­ erties of the parser are not affected and the number of occurrences of the contraction rule is restricted to the number of pronouns in a sentence or a text.

The limited use of the contraction rule (i.e. copy rule) implies that the global stream of undischarged quantified expressions is finite. In addition, the stream is acyclic because it represents a traversal of an acyclic tree struc­ ture. All frozen tasks (of.pronoun resolution) are ar­ ranged along this finite, acyclic stream, hence there will be neither the trap of an infinite search space nor the danger of a deadlock. Thus, the algorithm is quaranteed to terminate for any input.

3.3 Concurrent parsing

Concerning the processing methods which have been pre­ sented in the last sections, full search for all possible derivations is most easily performed by using the Pro­ log backtracking mechanism. This leads to two known drawbacks. Firstly, usually a lot of redundant work has to be done because the backtracking mechanism does not allow to reuse successful subderivations. Secondly, since all data is local to one proof structure, there is hardly any basis to attempt several proofs in parallel. Standard solutions to these problems exist already in the form of table-based parsing, or chart-parsing. For Prolog im­ plementations, the more conventional approaches realize the chart as a set of Prolog data base entries, see e.g. [Pereira and Shieber, 1987].

For a parsing method which also handles the process­ ing of contextual information, the Prolog data base ap­ proach becomes quite expensive. Every time when an application step has been carried out, the data base en­ tries which represent the nodes in the right daughter tree have to be exchanged in order to update their input sets. If one adopts, however, the somewhat more uncon­ ventional approach of parsing with nested streams, cf. [Okumura and Matsumoto, 1987, Matsumoto and Sug­ imura, 1987], the destructive operation of updating the context lists is done inexpensively by the Prolog unifica­ tion operation.

The propositions which cover portions of the deriva­ tion starting at the same position in the sentence form a stream / 1 . Furthermore, each proposition is connected to the stream / 2 of its alternative right neighbor con­ stituents:

or more pictorially:

Figure 5 shows the rules of the stream-based parsing al­ gorithm. The rule (lkup) realizes the lexical lookup offor a word w with category x and its right neighbor string a. The applications rules do their usual work. However , one important feature of the Prolog data base approach must be simulated here. Each data-base lookup of an entry returns a new copy of this entry. Looking up a proposition in the stream, however, returns the identi­ cal proposition for all accesses. In order to avoid variable clashes, the new proposition Q1 (x : (S1Sa)] Q~ must re­ sult from combining a copy q; (y : Sa) Q~ of the propo­ sition Q2 (y : Sa) Q3 with the functor proposition. This kind of copying does not lead to the appearance of two copies of the same proposition in one (virtual) construc­ tion calculus derivation. The use of copies is reserved for alternative derivations, only 4 . The rules (pron), (licq), and ( absp) add new elements to the stream. Since this happens "spontaneously", the appropriate control struc­ ture must be provided to let these rules apply at most once to each stream element, e.g. by creating a process per rule and per stream.

4 A more comprehensive argument for the soundness of this style of copying with regard to a chart parsing algorithm which handles hypothetical propositions has been given in [Konig, 1990].

4 Conclusion

Based on Pereira's semantic construction calculus [Pereira, 1990), we have defined algorithms which per­ form the three phases of the construction of a seman­ tic representation (composition, quantifier scoping, and anaphora resolution) in an interwoven manner. The in­ vestigation of the data flow lead to a stream-based al­ gorithm which allows for a high degree of AND-parallel processing.

In previous approaches, at least the anaphora res­ olution module had to access the semantic form, cf. [Johnson and Kay, 1990]. Now, the semantic construc­ tion operations work independently of the underlying semantic representation. The only link between the con­ struction algorithm and the specific semantic represen­ tation is the A-conversion operation, which could be re­ placed by other, possibly weaker constructors, e.g. based on unification.

What we have suggested so fa~ is an algorithmic skele­ ton of extended compositional semantics. This skele­ ton will only become a full-fledged body if one adds the wealth of heuristics about anaphora resolution and constraints on quantifier scopes. Further investigations concerning efficient structure sharing methods for se­ mantic representations and contextual information are necessary in order to improve the overall performance when parsing highly ambiguous input. The algorithms seem still rather far away from the presumed way of cog­ nitive language processing. Information about possible antecedents for anaphora flows only along the paths of the derivation tree. Improvements should be made to­ wards a word-to-word transport of information which, of course, has to be filtered by the structural constraints.

Based on the notion of extended compositionality as it is realized in the construction calculus, even seman­ tic representation languages like Kamp's Discourse Rep­ resentation Structures which have the reputation of be­ ing non-compositional can be handled in a compositional manner.

Constructing semantic representations for a natural language utterance (and interpreting it) has some sim­ ilarity to the evaluation of a computer program: pro­ grams are processed with regard to a given context (i.e. machine state) . The similarity between programs and natural language has been observed in the literature, e.g. [van Benthem, 1989), and has given rise to research programs concerning "dynamic logic" for natural lan­ guage, e.g. [Groenendijk and Stokhof, 1990, Muskens, 1990]. Further investigation of the dynamics of natural language might give insight how to use parallel process­ ing mechanisms for natural language analysis in a more sophisticated way.