Weighted Interaction of Syntax and Semantics in Natural Language Analysis

WEIGHI'ED INTERACTION OF SYNTAX AND SEMANTICS IN NA'ruRAL IANGUAGE ANALYSIS

Leonardo Lesmo and Pietro TOrasso

Dipartirrento di Inform:ttica - Unive rsita' di 1brino Via Valperga Caluso, 37 - 10125 TORINO - ITALY

ABSTRACT

The present paper discusses the extensions to the parsing strategies adopted for FIDO (a Flexible Interface for Database Operations). The parser is ~le to deal with ill-formed inputs (syntactically ~11 - formed sentences, fragrrents, conjunctions, etc.) because of the strict cooperation am::mg syn­ tax and semantics. The syntactic knowledge is represented by means of packets of condition-action rules associated with syntactic categories. The non-determinism is xrainly handled by means of rules which restructure the parse tree (called "natural changes") so that the use of backtracking is strongly limited.

In order to deal with difficult cases in which no clear-cut mechanism exists for excluding an interpretation, a ~ighting mechanism has been added to the parser so that it is possible to explore few different hypotheses in parallel and to choose the best one on the basis of oomplex interaction among syntax and semantics.

INI'RODUCTION

If one considers the evolution of camputerized natural language understanding systems (Charniak, 1~81), it beoornes apparent that the role of syntac­ t1c knowledge can vary frcrn being the basis of the process to being campletely neglected. In the first case, the conversion fom a linear sequence of words to a corresponding structured representation (parse tree) is guided only by the syntactic knowledge, whereas the other knowledge sources (xrainly semantics) have the task to translate the parse tree into a meaning representation; within the other approach the understanding process is vie~ as a whole and no special role is played by syntactic knowledge (given that such a knowledge is assumed to exist).

As regards purely semantic approaches, they present some problems with respect to the perspicu­ ity of the model. In particular, the structural inforxration (e.g. the fact that in English the adjectives precede the noun necessarily, whilst in Italian they do not) has to be duplicated for the different entities or represented in procedural form wi thin the analysis program. Since ~ believe that structural inforxration is fundarrental in the analysis process, and that its explicit representa­ tion increases the understandability (and the modi­ fiability) of the systerns, ~ will take in the fol­ lowing the opposite view, trying to start from syn­ tactic approaches and to justify the increasing role of semantics within them.

The aim of this introduction the sexrantics can be used effectiveness of N.L. analysis. is to discuss how to increase the In particular,

three points will be set forth:

• frcrn the point of view of efficiency of process­ ing, the grarrrnar-based approaches have to use semantic inforxration as soon as possible
• the human ability to understand ill-formed frag­ ments suggests to reduce the predcrninance of syn­ tactic knowledge and, again, to use more heavily semantic inforxration
• the phencrnenon of garden paths shows that two different modes of operation exist: norxral and backup. H::lwever, purely syntactic approaches fail to account for the phenomenon in a perspicuous way.

If ~ consider a grammar only from the point

of view of expressive power, of course ~ can, after a thorough analysis of the phencrnena aceur­ ring in natural language use, hope to find a gram­ mar that characterizes all and only the sequences of words that consti tute "acceptahle" sentences. The study of the required power of N.L. grammars received considerable attention in the past (for a recent and thorough overview see (Pullum, 1984) ; some prominent positions are described in (Per­ rault, 1984)).

Hbwever, it has often pointed out that a canprehensive (and useful) N.L. understanding sys­ tem should also take into account higher-level problerns; in particular, it should also provide the researcher with some insights about the relation­ ships existing be~n syntactic structures and semantic interpretation.

M:>st classical studies, both within the field of forxral languages and wi thin the field of natural languages vie~ the semantic interpretation as a process "appended" to the syntactic analysis. It is widely accepted that this way of using semantics is highly inefficient: the nurober of alternative parses is often so high (especially when preposi­ tional phrases are present) , that i t is not cost effective to delay the intervention of semantics (Sagalowicz, 1980); on the contrary, it is prefer­ able to use semantics both as a meaning­ construction process and as a source of further a:mstraints for the analysis, as soon as possible during the analysis itself (~s, 1980).

Hbwever, some other problems deserve atten­ tion. The first of them concerns the idea of "correctness" that, as stated above, is at the basis of the grammar-based approach. It is ~11 known that in rrost cases, humans are able to under­ stand the rreaning of sentence fragrrents that are syntactically ill-formed without any apparent dif­ ficulty. It' s worth observing that the l.ocution "ill-formed sentences" does not r e fe r exclusively to sentences that can reasonably be rejected on syntactic grounds. For example, the existence of a conjunction (Huang, 1984) can result in a sentence fragment that is ill-formed, although the entire sentence must be considered correct under any plau­ sible definition of syntactic correctness. The problern of parsing ill-formed inputs has become very popular recently; a nurober of papers appeared in ii soecial issue of the ACL Journal (AJCL, 1983). It must be noted that the approaches can be roughly categorized in two classes: extensions of grammati­ cal formalisms and semantic-based analyzers. As stated above, we will not discuss here the senantic approaches; as rega.rds the other ones, we can say that an extension of a grammatical formalism lends itself rather well to the relaxation of some syn­ tactic constraints (e.g. nurober agreerrent), less well to others (e.g. the absence of a reqtlired con­ stituent) and meets big difficulties in handling ordering problems (out of order constituents). This is obviously due to the fact that formal grarn­ nars have the task of describing "strings" of sym­ bols, i.e. objects where the order is fundanental. It is not sufficiently proved that in natural langLHge sentences, in their aspect of information conveying tools, the order of constituents is as fundanental. This observation leads to a last remark: in languages where the order is not as strict as in English (almost free word-order languages as Italian or Japanese) grammars that are not based on the ccmron concept of rewrite rules (nainly related with case systems) are receiving greater and greater attention (Nitta et al., 1984; Sakanoto et al., 1984) ·

Another problern that should be rrentioned is based on psychological IOC>tivations. Although this paper is not intended to present a psychologically valid mode l of natural language processing, we believe th?.t some well known fhenanena cannot be disregarded, because they help in making rrore clear what should (or should not) happen in a N. L. analyzer. The phenomenon we will COI1>5ider here is that of garden paths. It gives a hint about the existence of t~ pcocessing m::des in the interpre­ tation of a sentence: normal analysis and backup. 7\i: firsi: s Lght: this remark confirrn.s t.he a.<.loption o E standard, n<:>n-detetministic parsin:J methods: wh:c,: b.icktracking is a usual. technique. On the other hand, the number of tirres a normal ATN parser (to consider a well known tool) backtracks is not justified by the relative rarity of garden paths. The efforts in the development of deterministic parsing (Marcus, 1980) tried to characterize the normal processing m::de, by stating that PARSIFAL would fail to analyze a sentence in cases where a person would garden path. However, it has been shown (Milne, 1982) that the three-constituent­ buffer approach adopted by Marcus does not predict with sufficient accuracy the occurrence of garden paths. Again this can be seen as a failure of approaches based only on syntactic knowledge (a grammar-based one ATN - and a rule-based one - PARSIFAL) to account for a linguistic fhenomenon: the solution should be looked for in a rrore effec­ tive cooperation between syntax and semantics.

It is not possible to close this introduction without quoting a r ecent paper, which addresses sarne of the problems rrentioned above in a thorough way. In (SChubert, 1984) the section 2.3 deserve s attention. It is entitled "Lack of provision for integration with semantic/pragnatic preference principles". What is shown in the paper is that hunan r eaction to sentences that have exactly the sarre syntactic structure nay vary considerably depend ing on the semantics of occurring words. Although the analysis is carried on in a way dif­ f erent from ours, the concept of "potentia l" as a rreans to balance the syntactic and senantic infor­ mation is similar to our weighting of alte rnative hypotheses.

Anothe r work close ly r e lated with the present one is reported in (Pazzani, 1984) · In that case also, the need of a strict cooperation between syntax and semantics is explicitly acknowledged. On the other hand i t seems tha t the absence of a weighting mechanism could make the IAZY parser fail in some cases wher e no c l ear-cut choice is possi­ ble.

In the second section of the pr esent paper we will describe the structure of the syntactic pro­ cessor inc luded in t.'le FIDO system. Although the system (which is fully implerrented in FRANZ LISP on a VN< ll/ 780 computer) does not hand l e all the phenorrena discussed in this introduction, the presentation will a llow us to clarify the basic operating principles, in order to describe in the third section the extensions of the parser we are currently implementing.

STh"'TACI'IC ANALYSIS IN FIDO

FIDO (a Flexible Interface for Database Opera­ tions) is a prototypal system that allows the user to access in N.L. (Italian) the data stored in a re lationa l database. Afte r a previous approach to building natura l language interfaces (Lesrro, M3.g­ nani, 'Ibrasso 1981) 1 we r ealized that one of the main concerns had to be to guarantee the portabil­ ity of the system; this was achieved by adopting a strongly modular approach. Same efforts have been made to deve lop e fficient methods to store semantic informa tion (Lesrro 1 Siklossy 1 'Ibrasso 1983) and to optimize the r esulting query1 expressed in rela­ t ional algebra (Lesrrol Siklossyl 'Ibrasso 1985). The organization of the parser was described in (Lesrrol 'Ibrasso 1983) and its suitability to the analysis of ill-formed sentences in (Lesrro1 'Ibrasso 1984); in particular 1 the extensions introduced to deal with conjunctions a re decribed in (Lesmo & 1brassol 1985) · We will overview here the basic design choices.

'Ihe syntactic knowledge source is composed of a set of condition-action rules1 where the condi­ tion examines the current status of the analysis, i.e. the parse tree that has already been built1 wher eas the action extends in some way the parse tree 1 hypothesizing the attachment point and the syntactic role of a new constituent. The parse tree is built accord ing to the head and modifier approach and an example is reported in fig.l.

Six node types have been de fined ; each ncrle label in fig .1 has the form TYPEi: the node labelled XXj is the j-th instance of the type XX that has been built during the analysis. The types appearing in the figure are: REL (standing for RELation, nornally associated with verbs); REF (REFerents: nouns and pronouns) ; OJNN (OJNNectors, mainly for prepositions; it can happen that the filler of the node is UNMARKED: it means that the corresponding verb case is not marked by a preposi­ tion); DET (mainly DETerminers). The other node types are ADJ (ADJectives) and MOD (MDDifiers, e.g. adverbs).

The syntactic rules are grouped in packets associated with syntactic categories. When an input v.ord is syntactically arnbiguous, different packets are activated and all conditions are tested. If just one of them succeeds, then the action is exe­ cuted and the analysis goes on deterministically. Otherwise, the status of the analysis is saved to allow for possible backups in a subsequent phase, and the first action is executed (the different rules are erdered manually) · Facilities are pro­ vided in the lexicon to handle canned phrases (e.g. "di corsa" - on the run) and canpound v.ords (e.g. "darrmelo" - give it to me) · It must be noted that sare conditions require a lookahead (2 v.ords max­ imutn); this is done in order to increase the discriminating power of the conditions and to reduce the nurober of choice points.

In order to give an idea of the control struc­ ture of the analysis, let us see what happens when the first v.ord of the example in f ig .1 is found (we must stress again t'nat FIOO works on corrmands in Italian: we will go on with English examples in orde r to increase G,e readability of the paper. In Italian the !lOSt direct translation of "which" is "quale", though its use differs slightly when it is used as a relative pronoun).

There are three different lexical entries for "which", each of which is associated with a dif­ ferent syntactic category: QADJ (interrogative adjective), QPRON (interrogative pronoun), and REL­ PRON (re lative pronoun). The analysisbegins with an empty REL node (RELl) as current node. lbughly speaking, all conditions of QADJ rules require that the next v.ord is an ad jecti ve or a noun, the QPRON rules apply in the rema1n1ng cases, whereas the RELPRON rules can be activated just in case a pre­ vious REF node can be used as an attach:nent point for the relative clause. In our case the QADJ

interpretation is selected and, al!Ong the rules of the packet, the one is chosen that applies when the current node is an empty REL node. That rule builds a CONI'I node (and fills it with tM-1ARKED), a REF node (and leaves it empty) and a DET node (and fills it with the current v.ord, i.e. "which") · The resulting structure is shown in fig.2. Then, the controller of the parsing process is awaken; it looks for another v.ord and finds it in the looka­ head buffer (it was used to discriminate between QADJ and QPRON). The NOUN packet is activated and a rule is selected, which fills the empty REF (REFl) with "course". We leave at this point the example, assuming that it gave an idea about how he analysis of a sentence is carried on.

Instead, some more specific points have to be made clear. The nodes in the figures have been represented very sketchily. Each node is actually a ccmplex data structure, with various slots arrl some procedures attached to the prototype. For example, a REL node includes slots as HEAD (the verb), FORM (active vs. passive), TENSE, NUMBER, MCX>D (indica­ ti ve, con juncti ve, etc. ) , ROLES ( the case frame) and others. Notice that the slot AUX irrlicates the presence of an auxiliarY verb in the sentence. The actual form of the auxiliary is not reported since it can be inferred by taking into account the values of MOOD, FO~, TENSE, etc. 'Ihe associated procedures are called RELHEADPROC (operations to be done when the HEAD slot is filled, e.g. computing the tense of the verb), RELAGREEPROC (checking the nurober agreement with the subject), and RELSR1PROC (checking the acceptability of the actual case frame and beginning to build the semantic interpre­ tation). When a node is operated upon, one or l!Ore procedures can be scheduled for execution. They can accept or reject the operations done by the parser (syntactic hypothesis). A simple way to make G,e parser more robust is to relax some of the con­ straints embodied in the procedures. For instance, an agreement failure can produce just a warning message, without requesting a reorganization of the parse tree, a reorganization which is always attempted in case of semantic failure. Such relax­ ation techniques can also be introduced in other formalisms, such as ATN (Kwasny & SOndheimer, 1981) · r.bre interesting, the proposed formalism handles easily also erdering errors. In fact, G,e attachment of cases to verbs and of adjectives to nouns is always allowed (in Italian the adjectives can occur both before and after the noun) and only when the node is closed (a node is closed, i.e. it is considered to be c:arplete, when an attachrrent is proposed to a node above i t in the tree) the CHECKORDER procedure verifies that the rules which govern the erdering of constituents are respected. Also in this case, a failure of CHECKORDER results in the issuing of a warning rressage, wi thout any reorganization of the parse tree.

It has probably been noted the use of the term "reorganization of the tree" in the discussion above. In fact, such rrodifications, that we call "natural changes" to point out their simplicity and natura lness, are the primary tool for handling non-determinism. 'Ihe brief presentation of the structure build ing rules failed probably to make clear one· important point: when the action part of a rule is executed, it usually adds a subtree to the current tree; the attachrrent point of the new subtree is the nearest node of the required type that is above the current node. Of course, this choice is made only on syntactic grounds, so it may happen that it is not acceptable from a semantic point of view. In a Standard ATN frarrework, this problern is solved backtracking: the subnets allow­ ing, for example, PP modifiers include an linplicit choice point (in correspondence with the position where a PP could be present or absent) and a seman­ tic failure would involve backing up to such a pre­ vious choice point. Although the introduction of scrce special tools (of the kioo of well-forrred sub­ string tables or chart parsers) a llows the system to avoid the re-analysis of the PP component, same bookkeeping is needed to save the status of the ana lysis at the choice points. The natural changes rrechanisrn makes that work use less, in that the choice points are implicitly available in the structure of the parse tree aoo can be easily looked for by the modification rules. A further advantage is the high flexibility of the tool: the natural changes are expressed in the form of pattern-action rules (as the standard rules) so that, in principle, an action could restructure the tree in a very cornplex way. In fact, we use them also to handle some problems related with the ana lysis of conjunctions (Lesrno & Tbrasso, 1985) and with scrce special forrns of relative clauses. As often happens, the natural changes are actually too powerful; at this time we have not pursued the study of what are the reasonable constraints that rnust be put on the operations of the changes. we want to stress, however, that the introduction of the natural changes does not substitute the backup cornpletely: this remark is in agreernent with the discussion about the existence of different pro­ cessing niedes in the analysis of N.L. sentences. Although we are not able to state now the correspondence between the use of backup and the occurrence of garden paths, we can notice that the saving of the status is llinited (in rnost cases) to syntactically arnbiguous words such that rnore than one syntactic category is acceptable in the current context: this strongly reduces the nurober of choice points, as predicted by the garden path fhencrcenon.

EXTENSIOOS 'IO THE PARSER

Before going on we have important point: whereas the to make clear an parser embodied in FIDO works on I talian sentences, in order to per­ form the tests that led to the version described in this section, we had to deve lop a small se t of rules for English. The reason why we did this was to have at disposal a wide corpus of thoroughl y analyzed examples (i.e. the ones appearing in the r e ferenced papers by Milne and Schubert). This approach to testing has both an advantage and a disadvantage: the adaptability of the parser to a different language is partially dernonstra ted, but the nurober of syntactic t:Oenc:mena tha t has been taken into account in building the English rules is not very high, so that sorne ad -hoc solutions could have been adopted.

we can now start by seeing what happens when syntactically arnbiguous sentences a r e processed by FIDO (old ve rsion). A first exarnple is dr awn f rorn Schubert 's paper:

1. John bought the book which I had se l ect ed for .Mary

After the analysis of the f irst portion of the sen­ tence (as far as the word "selected") the status of the tree is the one of fig. 3. Upon encountering the preposi tion "for", a rule would propese i ts a ttach­ rrent (in a OONN node ) to the node REL2 (i. e . as a verb rrodifier) · The subsequent attachrrent of a REF node (containing "Mary") to the newly creat ed con­ nector would trigger the semantic check procedures, which give a positive ans>ver (case frarre : 'IO S:ELEX::T; SUBJ: PERSON, OBJ: 'IHING, FüR: PERSON) and allows the systern to confirrn the proposed analysis. On the contrary, in the exarnple belaw:

1. John bought the book which I had selected at a lower price

after a sequence of steps analogous to the one described above (exteooed to handle the de terminer and the adjective), the semantics would r e j ect the syntactic hypothesis. The natural changes would be triggered, the attachrrent of the PP to "book" would be tried aoo again rejected on semant1c bases. Finally, the atternpt to a ttach "at a l ow price" to "buy" succeeds and the analysis is canpleted.

It is apparent tha t this process does not work in cases such as :

(3) John carried the groceries for :·,lary

'Ihe attachrrent of "for Mary" to "groceries" 1.>0uld be attempted; it cannot be rejected by the seman­ tics, thus the final analysis is the one reported in fig .4 (contrarily to ~1e expected one ).

Another exarnple concerns a pair of garden path sentences. In

(4) The building blocks the sun

we obta in the s tructure reported in f ig. 5 · I f the actual input sentence were

1. The building blocks the sun faded are red

then the analyis 1.>0uld be blocked at "are" (in fact, "faded" 1.>0uld be used as a rrodifier for "sun"; see (6)) and a backup 1.>0uld rrake the systern build the right structure.

• (b) 'i'he builäing blocks the sun faded behind t.'1e hills

Again, although the model predicts the correct behavior in the examples above, it fails to charac­ t erize the difference between (7) and (8) :

1. The table rocks during the earthquake
2. The granite rocks during b e earthquake

In these sentences we assume , according to the rcsults of r'1ilne 's experiments that (8) rrakes fJE-'0ple garden path , whilst (7) does not. In fact , the only W6Y FIDO has at d isposal to express prefeL­ ences (lexical, in this case ) is to t ake into account the order of the l exica l entries . 'Ihus, we are able to say that "rock" is rrore comrronly used in its nominal sense than in its verba l sense , but not to say that (to use Milne's words) "people like grani t e rocks , but don ' t like table rocks". In other words, FIDO is not able to express pre fer­ ences on the basis of the context.

The solution we adopted to overcome the prob­ lems mentioned above was to introouce o limiteä degree of parallelism in the analysis, and t o evaluate and upda t e t.'1e weights of the different alternatives that are being carried on in parallel , until a definite decision can be taken. Notice that we don't claim that the chosen alternative is always the right one , nor we would like to get such a result: in some cases the systern can take the wrong wa y , a s hurrans do when they ga rden pa th ·

In implernenting such a rrodel, we took advan­ tage of our research on expert systems based on fuzzy production rules (LeSI!O, Saitta, Torasso 1985): in fact , the weighting mechanism we adopted is based on possibility theory (Zadeh, 1979). We will not ana lyze here the advantages of a possibil­ ity based approach with respect to approaches based on probability theory or on heuristic methods (the interested reader can see (Lesrro, Saitta , Torasso 1985)) , but , as we did in the previous section , we will try to let the reader understand how the weighting mechanism has been rnerged with ti1e facil­ ities previously available in FIDO. We have only to say that the weight (that, from now on, will be called Confidence Degree - CD) is a value r anging from 0 to l, ;.~here 0 means that the hypothes is can­ not be accepted at all and l rreans that the hypothesis is surely the right one .

The basic design choices that must be made concern:

• What alternatives must be considered (how rrucn parallelism should be supported)?
• How long must the diffe rent paths be pursued (when should the final decision be taken)?
• What knowledge sources contribute to the weight­ ing (and how can the weights be adjusted)?

It is interesting to note that the structure of the parser described in the previous section gives a hint about the first choice . In fact, two sources of ambigui ty are present: rrore than one rule may be activated at the sarre tirre and the attachrnent point of a consti tuent is not uniquely deterrnined . Thus , to test the validity of the pro­ posed approach we had to change the basic control structure in only two ways:

1. The different rules whose conditions are satis­ fied are executed in parallel. Although t."'lere is no a-priori upper limit to the arrount of paral­ l elism, the constraints embodied in the condi­ tions keep low the number of alternative hypotheses (accord ing to the Observation made in the previous section about the reduction of the number of choice points).
2. Instead of waiting for the results of the seman­ tic checks, the natural changes are scheduled as

soon as an attachrrent is proposed. 'Ihe natural changes have been rrodified in a simple way: no detachment is made, but the different alterna­ tives are added to the proposed one (note that this is just a first, low-cost solution: what we are studying now is the possibility to eliminate the natural changes mechanism; this can be done if all attachment points can be found at a glance by the linking procedures).

As regards the second choice (when should the fina l decision be taken?), we decided to distin­ guish aga in the sources of ambiguity described above. The reason why different solutions were rea­ sonable stood in the different computational cost of carrying on alternatives : whereas the rule ambi­ guity seemed to require a real maintenance of dif­ ferent trees, the role (attachment) ambiguity irnplied only that different links are included in the same tree. In the first case, after trying dif­ ferent alternatives (no lookahead, one-word looka­ head , just the lookahead required by the cond i­ tions) we had the pleasant surprise that in most cases the different states had not to be main­ tained. In fact, the only thing we had to do was to defer ti1e decision about the rule to apply after the execution of the semantic check procedures: they provided the parser with the information about the semantic preferences that was lacking in the previous version of the system. As regards the role ambigui ty, we let the analys is go on until the filler of the node which is the root of the attached subtree has been found: this means that we wait until the semantic checks can be done. For example, if sentence (1) were changed into:

1. John bought the book that I selected for �~e nice blond-haired girl that you know

ti1en the choice would be delayed until the ward

"girl" is found.

Note that in both cases, though the behavior of the parser is different, the parser pursues dif­ ferent paths until the system allows the semantics to provide it with some evidence about the most reasonable choice.

Finally, tl1e third problern concerns the knowledge sources involved in the weighting pro­ cess . Apparently, we had to attach CD's to lexical entries, syntactic rules, and semantic information. On the other hand , the semantic information (which in FIDO consists in a semantic net representing the selectional restrictions, see (Lesmo, Siklossy, Tbrasso 1983)) overcomes the information that could be attached to lexical entries . In fact, the choice is made on the basis of the possibility of attachment of a pair of "concepts" : this provides the system with more detailed information than the possibility of occurrence of a single interpr eta­ tion. 'Ihat is, if the system knows that CD (TO RCCK, SUBJ :'l'ABLE) = 0.8 and CD (RCCK, MODIF:TABLE) .1, CD (TO ROCK, SUBJ:GRANITE) = 0.6 and CD (ROCK, MODIF:�R~ITE) = 0.9, it can disregard the fact that CD (TO ROCK [CAT:VERB] ) = 0. 7 and CD (ROCK [CAT: NOUN]) = 0.9. The solution we adopted is to associate with the arcs appearing in the semantic net a CD expressing the preference of the system. It is not possible here to discuss the deta ils of the implementation (actua lly, not all arcs have a CD), because such a discussion would reguire a description of the semantic net . It must be noted, however, that this solution r eguires the explicit introduction of all possible semantic con­ nections. This is consistent with a database inter­ face , because the associations carry the informa­ tion about the correspondence with the database schema . In a general N.L. understanding system this is guite expensive and some way to propagate the CD's according to the degree of match with the declared selectional restrictions should be included in the system.

As regards the syntactic knowledge source, we attached CD's to the structure building rules and we dec ided to compute the CD's of the attachment points on the basis of their distance (number of nodes to traverse) from the "current" node. In par­ ticular, the current node is assigned a CD egual to 1 and, for each node that is traversed to find an alternative, the CD is decreased by a constant fac­ tor (currently 0.1). Apart from this latter , all CD's (both in the net and in the rules) have been assigned manually. 'Ihis allowed the system to succeed on a wide set of examples; of course, a l ess heuristic determination of CD values would be useful, but it reguires a !arge research effort per

se.

OONCWSIONS

As Winograd states in (Winograd, 1983), the r esearch on N.L. understanding is being carried on today within a new paradigm: the computational paradigm. Its main differences with respect to the previous (generative) one , stands in the "attention to process organization" and the "relevance of non-linguistic knowledge".

It is not the aim of this paper to take into account all the problems that non-linguistic knowledge conveys into N.L. analysis, but to make clear that the in-depth understanding of the respective roles of syntactic and semantic knowledge sources and the clarification of the way they interact to construct the interpretation of natural language sentences is fundamental to building N.L. interpr eters. We claim that ne ither syntax nor semantics can be assigned the role of "guide" of the interpretation process, but they must operate on a parity basis. Both of them pro­ vide the analyzer with information about the choices that must be made during the interpreta­ tion.

'Ihe approach outlined in the paper is just a first attempt to satisfy these principles: many problems must be examined and some substantial changes can be introduced, but we maintain the fun­ damental role of the "rule " concept in the con­ struction of N.L. analyzers and the necessity of being able to weight the contributions of different knowledge sources: the interpretation is not a categorical (yesj no) process, but it must be based on the idea of preference (Wilks, 1975) (or subjec­ tive evidence) ·

'Ihe paper shows how a rule-based approach has been modified to take into account both syntactic and semantic preferences. We hope to have given a feeling about the ease with which the reguired rrodifications were embodied in the previous system. 'Ihe available space did not allow us to consider sane other [ilenüm:'!na that FIOO is able to handle quite easily: they concern the analysis of ill­ formed sentences. Although many aspects of ill­ formedness were already handled by the old version of the system, the introduction of CD's and the modifications of the natural changes are useful also to characterize in a more perspicuous way the analysis of conjunctions: also in this case, the CD's are used to compare the different alternatives regarding the role the second conjunct can assume.

REE'ERENCES

1. A.A.V.V.: Special Issue on Ill-FOrmed Parsing, AJCL 9, no.3-4 (1983).
2. E.Charniak : Six TOpics in Search of a Parser. Proc. 7th IJCAI, Vancouver (1981),1079-1087.
3. X.Huang : Dealing with Conjunction in a Machine Translation Environment. Proc. COLING 84, Stanford (1984), 243-246.
4. S.C.Kwasny , N.K.Sondheimer: Relaxation Tech­ niques for Parsing Grammatically Ill-Formed Input in Natural Language Understanding. AJCL 7 (1981), 99-108.
5. L.Lesmo, D. l-1agnani, P.TOrasso: A Deterministic Analyzer for the Interpretation of Natural Language Commands . Proc. 7th IJCAI, Vancouver (1981), 440-442.
6. L.Lesmo, L.Saitta, P.TOrasso : Evidence Combi­ nation in Expert Systems. Int. J. of Man­ ~Bchine Studies , vol.22 (1985).
7. L.Lesmo, L.Siklossy, P.TOrasso: A 'IWo Level Net for Integrating Selectional Restrietions and Semantic Knoovledge. Proc. IEEE Int. Conf. on Systems , ~an and Cybernetics, India (1983), 14-18.
8. L.Lesmo, L.Siklossy, P.TOrasso: Semantic and Pragmatic Processing in FIOO: a Flexible Interface for Database Operations . Information Systems 10, n.2 (1985).
9. L. Lesmo , P. TOrasso: Language Parser based tion of Syntax. Proc . Pisa (1983), 114-121. A Flexible Natural on 'DNo-Level Representa­ lst Conf. ACL Europe,
10. L.Lesmo, P.TOrasso: Interpreting Syntactically Ill-Formed Sentences. Proc. COLING 84 , Stan­ ford (1984), 534-539.
11. [ll] L.Lesmo, P.TOrasso: Analysis of Conjunctions in a Rule-based Parser. Proc. 23rd ACL Meet­ ing, Chicago (1985).
12. H.Marcus : A 'Iheory of Syntactic Recognition for Natural Language. MIT Press (1980).
13. R.W.Milne: Predicting Garden Path .sentences . Cognitive Science 6, 349-373 (1982).
14. Y.Nitta et al. : A Proper Treatment of Syntax and Semantics in Machine Translation. Proc. COLING 84 , Stanford (1984), 159-166.
15. M.J.Pazzani: Conceptual Path Sentences . Proc. (1984), 486-490. Analysis of Garden­ OJLING 84 , Stanford
16. C.R.Perrault (ed.): Special Issue on Mathemat ­ ical Properties of Grammatical FOrmalisms. Computational Linguistics 10 (1984) , 165-202.
17. G.K.Pullum: Syntactic and Semantic Parsabil­ ity. Proc. OJLING 84 , Stanford (1984), 112122.
18. Y.Sakamoto et al.: Lexical Features for Japanese Syntactic Analysis in MU-Project-JE. Proc. Coling 84 , Stanford (1984 ), 42-47.
19. D.sagalowicz: Mechanical Intelligence: Research and Applications. Final Tech . Report, SRI Int., Menlo Park (December 1980) ·
20. L.K.Schubert: On Parsing Preferences. Proc. Coling 84, Stanford (1984), 247-250.
21. Y.A.Wilks: A Preferential Pattern-Seeking Semantics for Natural Language Inference, Artificial Intelligence 6 (1~75), 53-74.
22. T.Winograd: Language as a Cognitive Process. Vol.l: Syntax, Addison Wesley (1983).
23. W.A.Woods: Cascaded ATN Grammars. AJCL 6 (1980) , 1-12.
24. [24 ] L.A.zadeh: A Theory of Approximate Reasoning. In E.Elcock, D.Michie, L.Mikulich (eds.): Machine Intelligence 9, Ellis Horwood (1979), 149-194.