ANALYSIS OF OONOUNCTIONS IN A ~JLE-~ PAKSER 
leonardo L~smo and Pietro Torasso 
Dipartimento di Informatica - Universita' di Torino 
Via Valperga Caluso 37 - 10125 Torino (ITALY) 
ABSTRACT 
The aim of the present paper is to show how a 
rule-based parser for the Italian language has been 
extended to analyze sentences involving conjunc- 
tions. The most noticeable fact is the ease with 
~4nich the required modifications fit in the previ- 
ous parser structure. In particular, the rules 
written for analyzing simple sentences (without 
conjunctions) needed only small changes. On the 
contrary, more substantial changes were made to the 
e~oeption-handling rules (called "natural changes") 
that are used to restructure the tree in case of 
failure of a syntactic hypothesis. T0~ parser 
described in the present work constitutes the syn- 
tactic component of the FIDO system (a Flexible 
Interface for Database Operations), an interface 
allowing an end-user to access a relational data- 
base in natural language (Italian). 
INTRODUCTION 
It is not our intention to present here a 
comprehensive overview of the previous work on 
coordination, but just to describe a couple of 
recent studies On this topic and to specify the 
main differences between them and our approach. 
It must be noticed, however, that both systems 
that will be discussed use a logic grammar as their 
basic framework, so that we will try to make the 
comparison picking out the basic principles for the 
manipulation of conjunctions, and disregarding the 
more fundamental differences concerning the global 
system design. It is also worth pointing out that, 
although the present section is ac~nittedly incom- 
plete, most of the systems for the automatic 
analysis of I~ural language do not describe the 
met~hods adopted for the interpretation of sentences 
containing conjunctions in great detail. There- 
fore, it is reasonable to assume that in many of 
these systems the conjunctions are handled only by 
means of specific heuristic mechanisms. 
A noticeable e~ception is the ~ facility 
of the U/R~%R system (Woods, 1973): in this case, 
The research project described in this paper has 
partially been m/pported by the Ministero della 
Babblica Istruzione of Italy, MPI 40% Intelligenza 
Artificiale. 
the conjunctions are handled by m~ans of a para- 
syntactic mechanis~ that enables the parser to 
analyze the second conjunct assuming that it has a 
structure dependent on the hypothesized first con- 
junct. The main drawback of this approach is that 
the top-down bias of the ATNs does not allow the 
system to take advantage of the actual structure of 
the second conjunct to hypothesize its role. In 
other words, the analysis of the second conjunct 
acts as a confirnution mechanism for the hypothesis 
made on the sole basis of the position where the 
conjunction has been found. Consequently, all the 
v~rious possibilities (of increasing levels of com- 
plexity) must be analyzed until a match is found, 
which involves an apparent ~aste of computational 
resources. 
The solution proposed in the first of the 
systems we will be discussing here is quite simi- 
lar. It is based on Modifier Structure Grammars 
(MSG), a logic formalism introduced in (Dahl & 
McCord, 1983), which constit%Ites an extension of 
the Extraposition Grammar by F. Pereira (1981). 
TNe conjunctions are analyzed by means of a special 
operator, a "demon", that deals with the two prob- 
lems that occur in coordination: ~he first conjunct 
can be "interrupted" in an incomplete status by the 
occurrence of the conjunction (this is not foresee- 
able at the beginning of the analysis) and the 
second conjunct must be analyzed taking into 
account the previous interruption point (and in 
this case, mainly because the second conjunct may 
ass~m~ a greater number of forms, some degree of 
top-down hypothesization is required). 
~e first problem is solved by the "backup" 
procedure, which forces the satisfaction (or "clo- 
sure" in our terms) of one or more of the (incom- 
plete) nodes appearing, in the so-called "parent" 
stack. T~e choice of the node to which the second 
conjunct must be attached makes the system 
hypothesize (as in SYSCONJ) the syntactic category 
of the second conjunct and the analysis can proceed 
(a previous, incomplete constituent would be saved 
in a parallel structure, called '~erge stack" that 
would be used subsequently to complete the 
interpretation of the first conjunct). 
Apar~ from the ccr~iderable pc~er offered by 
~LgGs for semantic interpretation, it is not quite 
clear why this approach represents an advance with 
respect to ~ ' a~roach. Even though the 
analysis times re\[x)zted in the appendix of (Oahl & 
McCord, 1983) are ~ry low, the top-down bias of 
180 
F~Gs produces the ~ problems as ATNs do. The 
'~:sckup" procedure, in fact, chooses blindly among 
the alternatives present in the parent stack (this 
problem is mentioned by the authors). A final ccm- 
ment concerns the analysis of the second conjtmct: 
since the basic grammar aims at describing "normal" 
English clauses, it seems that the system has so~ 
trouble with sentences involving "gapping" (see the 
third section). In fact, while an elliptical sub- 
ject can be handled by the hypothesizetion, as 
second conjunct, of a verb phrase (this is the 
equivalent of treating the sit~/ation as a single 
sentence involving a single subject and tw3 
actions, and not as tw~ coordinated sentences, the 
second of which has an elliptical subject; it 
a perfectly acceptable choice), the same mechanism 
cannot be used t~ handle sentences with an ellipti- 
cal verb in the second conjunct. 
The last system we discuss in this section has 
been described in (Huang, 1984). ThOugh it is 
based, as the previous one is, on a logic grammar, 
it starts from a qt/ite different asst~tion: the 
grammar deals explicitly with conjunctions in its 
rules. It does not need any extra-gramnatical 
mechanisms hut the positions where a particular 
constituent can be erased by the ellipsis ~ve to 
be indicated in the rules. Even though the effort 
of reconstructing the complete structure (i.e. of 
recovering the elliptical fragment) is mainly left 
to the unification mechanism of P~K)LOG, the design 
of the grammar is rendered s(~newhat more complex. 
%~e fragment of grammar reported in (Huang, 
1984) gives the i~pression of a set of rules 
"flatter" than the ones that normally appear in 
standard grammars (this is not a negative aspect; 
it is a feature of the ATNs too). The "sentence" 
structure co,rises a NP (the subject, which m~y be 
elliptical) , an adverbial phrase, a verb (which 
also may be elliptical), a restverb (for handling 
possible previous auxiliares) and a rest-sentence 
cc~nent. We can justify our previous comment on 
the increased effort in grammar development by not- 
ing that two different predicates had to be defined 
to account for the normal ccmlplements and the 
structure that Huang calls "reduced conjunction", 
see example (13) in the third section. Moreover, it 
se~ms that a recovery procedure deeply embedded 
within the language interpreter reduces the flexi- 
bility of the design. It is difficult to realize 
how far this problem could affect the analysis of 
n~re complex sentences (space contraints limited the 
size of the gra~m~ar reported in the paper quoted), 
but, for instance, the explicit assu~tion that the 
absence of the subject makes the system retrieve it 
from a previous conjumct, seems too strong. Disre- 
garding languages where the subject is not always 
required (as it is the case for Italian), in 
English a sentence of the fore "Go home and stay 
there till I call you" could give the parser store 
trouble. 
In the following we will describe an approach 
that overcomes som~ of the problems mentioned 
above. The parser that will be induced consti- 
tutes the syntactic com\[xm~t of the FIDO system (a 
Flexible Interface for Database Operations), which 
is a prototype allowing an end-user to interact in 
natural language (Italian) with a relational data 
base. The query facility has been fully implemented 
in E~ANZ LISP on a VAX-780 computer. The update 
operations are currently under study. Tne various 
com\[x~ents of the system have been described in a 
series of papers which will be referenced within 
the following sections. The system includes also an 
optimization ccmlmonent that c~nverts the query 
expressed at a conceptual level into an efficient 
logical-level query (Lesmo, Siklossy & Torasso, 
1985). 
ORGANIZATION OF THE PARSER 
In this section we overview the principles 
that lie at the root of the syntactic analysis in 
FIDO. We try to focus the discussion on the issues 
that guided the design of the parser, rather than 
giving all the details about its current implen~n- 
tation. We hope that this approach will enable the 
reader to realize why the system is so easily 
extendible. For a more detailed presentation, see 
(Lesmo & Torasso, 1983 and Lesmo & Torasso, 1984). 
The first issue concerns the interactions 
between the concept of "structured representation 
of a sentence" and "status of the analysis". These 
t%~ concepts have usually been considered as dis- 
tinct: in ATNs, to consider a well-known exa~le, 
the parse tree is held in a register, but the glo- 
bal status of the parsing process also includes t/he 
contents of the other registers, a set of states 
identifying the current position in the various 
transition networks, and a stack containing the 
data on the previous choice points. In logic gram- 
mars (Definite Clause Granmars (Pereira & Warren, 
1980), Extraposition Grammars (Pereira, 1981), 
M~difier Structure Grammars (Dahl & ~L-~Drd, 1983)) 
this book-keeping need not be completely explicit, 
but the interpreter of the language (usually a 
dialect of PROLOG) has to keep track of the binding 
of the variables, of the clauses that have not been 
used (but could be used in case of failure of the 
current path), and so on. On the contrary, ~e 
tried to organize the parser in such a way that the 
two concepts mentioned above coincide: the portion 
of the tree that has been built so far "is" the 
sta~/s of the analysis. Tne implicit assunlDtion is 
that the parser, in order to go on wi~/~ the 
analysis does not need to know how the tree was 
built (what rules have been applied, what alterna- 
tives there were), but just what the result of the 
previous processing steps is 4. 
Of course, this assumption implies that all infor- 
mation present in the input sentence must also be 
AWe must confess that this assumption has not been 
pushed to its extreme consequences. In some cases 
(see (Lesm~ & Torasso, 1983) for a more detailed 
discussion) the backtracking mechanism is still 
needed, but, although we are not unable to pro- 
vide experimental evidence, we believe that it 
cou/d be substituted by diagnostic procedures of 
the type discussed, with different purposes and 
within a different fomTalism, in (Weischedel & 
Black, 1980). 
181 
present in its struct-ttred representation; actually, 
what happens is that new pieces of information, 
which were implicit in the "linear" input form, are 
made explicit in the result of the analysis. These 
pieces of information are extracted using the syn- 
tactic knowledge (how the constituents are struc- 
tured) and the lexical knowledge (inflectional 
data). 
The main advantage of such an approach is that 
the whole interpretation process is centered around 
a single structure: the deL~ndency structure of the 
constituents composing the sentence. This enhances 
the modularity of ~he systam: the mutual indepen- 
dence of the various knowledge sources can be 
stated clearly, at least as regards the pieces of 
knowledge contained in each of t_~; on the c~n- 
trary, the control flow can be designed in such a 
way that all knowledge sources contribute, by 
cooperating in a more or less synchronized way, to 
the overall goal of comprehension (see fig.l). 
A side-effect of the independence of knowledge 
sources n~_ntioned above is that there is no strict 
coupling between syntactic analysis and s~T~%ntic 
interpretation, contrarily to what happens, for 
instance, in Augmented Phrase Structure Grammars 
(Robinson, 1982). This moans that there is no one- 
to-one association between syntactic and semantic 
rules, a further advantage if we succeed in making 
the structured representation of the sentence rea- 
sonably uniform. This result has been achieved by 
distinguishing between "syntactic categories", 
which are used in the syntactic rules to build the 
tree, and "node types", whose instantiations are 
the ele_,~nts the tree is built of. z Since the number 
of syntactic categories (and of syntactic rules) is 
considerably larger than the ntm~ber of node types 
(6 node types, 22 syntactic categories, 61 rules), 
then so,~ general constraints and interpretation 
tales may be expressed in a more compact form. 
WiL-hout entering into a discussion on semantic 
interpretation, we can give an exile using the 
rules that validate the tree from a syntactic point 
of view (SY~IC RULES 2 in fig.l). One of these 
rules specifies that the subject and the verb of 
the sentence must agree in nun~r. On the other 
hand, the subject can be a noun, a pronoun, an 
interrogative pro~)un, a relative pro~m~n: each of 
them is associated with a different syntactic 
category, but all of them will finally be stored in 
a node of type REF (standing for REFerent) ; 
independently of the category, a single rule is 
used to specify the agreement constraint mentioned 
above. 
let us now have a look at the box in fig.l 
labelled "~IC RULES i: EXTENDING THE \[~a~". 
~Six node types have been introduced (each node is 
actually a o~91ex data structure): REL (~a- 
tions, mainly verbs), REF (R\]~Ferents, no~s, pro- 
nouns, etc. ), CO~ (CONNectors, e.g. preposi- 
tions), OET (DETerminers), ADJ (ADJectives), and 
MOD (MCOifiers, ~ainly adverbs). Be~nd these six 
types, a special node (TOP) has been included to 
identi~ Z the main verb(s) of the sentence. 
SYNTACTIC 
RULES 1 : 
EXTENDING THE TREE II 
I SYNT"C iC I |1 \] 
RULES 2: I~{IRE 
IVALZDATZNG\[ , I T"=T E I / 
NATURAL \[ 
CHANCES: \[ 
RESHAPING\[ 
THE TREE\[ 
SEMANTIC I 
KNOWLEDGE l: 1 
VALIDATING I 
THE TREE I 
(STRONG1 J 
RE' SENTATIO INKNOW E GE 
ANNOTATING \[ /' THETRE  1 
ANAPHORA 
RESOLUTION: 
DISAMBIGUATING 
THE TREE 
FiE.l: A single structure is the basis of the 
whole interpretation process. 
The rules that are logically contained in that box 
are the primary tool for performing the syntactic 
analysis of a sentence. Each of them has the form: 
~ITION ---> ACTION 
where PR~ONDITION is a boolean expression ~nose 
ter~tg are elementary conditions; their predicates 
allow the system to inspect the current status of 
the analysis, i.e. the tree (for instance: '"~hat is 
the type of the current node?", "Is t.here an en~pty 
node of type X?") ; a look-ahead can also be 
included in the preconditions (maxirman 2 words). 
The right-hand side of a rule (ACTION) consists in 
a sequence of operations; there are two operators: 
CRLINK (X,Y) 
which creates a new instance of the type X and 
links it to the nearest node of type Y existing in 
the rightn~Dst path of the tree (and moving only 
upwards) 
FILL (X,V) 
which fills the nearest node (see above) of type X 
with the value V (which in most cases coincides 
with the lexical date about the current input 
word). 
'\]\[he rules are grouped in packets, each of 
which is associated with a lexical category. It is 
worth noting that the choice of the rule to fire is 
non-deterministic, since different rules can be 
executed at a given stage. On the other hand, the 
non-determinism has been reduced by making the 
preconditions of the rules belonging to the same 
packet mutually e~uzlusive; consequently, the status 
is saved on the stack only (but not always) if the 
input word is syntactically ambiguous. Note that 
nothing prevents there being exceptions to this 
rule. For e~le, in ~glish the past indicative 
and the past participle u.~ually have the same form: 
in this case, ~ different rules of the V~ 
packet could be activated if the context allows for 
both interpretations. 
182 
Currently, the syntactic categories of an 
ambiguous word are ordered manually in the lexicon; 
since the "first" rule is deten~ined by that order, 
the selection of the rule to execute depends Only 
on the choices made by the designer of the lexicon. 
Same experiments :,a~e been made to include a 
weighting mechanism, which should depend both on 
the syntactic context and on the semantic knowledge 
(Lesmo & Torasso, 1985). 
A second "syntactic" box appears in fig.l. It 
refers to rules that are, in a sense, weaker than 
the rules of the set discussed above. The rules of 
the first set are aimed at defining acceptable syn- 
tactic structures, where "acceptable" is used to 
maan that the resulting structure is semantically 
interpretable (for instance, a determiner cannot be 
used to modify an adjective). On the contrary, the 
rules of t~he second set specify which of the mean- 
ingful sentences are well formed; in particular, 
they are used to check gender and number agreement 
and the ordering of constituents (e.g. the fact 
that in ~glish an adjective should occur before 
the noun it refers to, whereas this is not always 
the case in Italian). The separation between the 
rules of the two sets is the feature that makes the 
system robust from a syntactic point of view (see 
(Lesmo & Torasso, 1984) for further details). 
It may be noticed that, in fig. i, both the 
second set of syntactic rules we have just dis- 
cussed and a part of the semantic knowledge have 
the purpose of '~alidating the tree", independently 
of t.he fact that the second-level syntactic con- 
straints can be broken (they are "weak" con- 
straints), whilst the semantic constraints can not 
(they are "strong" constraints), sane action must 
be performed when the structure hypothesized by the 
first-level rules does not match those constraints. 
The task of the rules called "natural changes" (see 
fig.l) is to restructure the tree in order to pro- 
vide the parser with a new, "correct" structure. We 
will not go into further details here, since the 
natural changes (in particular t_he one concerning 
the treatn~nt of conjunctions) will be discussed in 
a following section; however, in order to give a 
complete picture of the behavior of the parser, we 
must point out ~.hat the natural changes can fail 
(no correct structure can be built) . In this case, 
the parser returns to the original structure and 
issues a warning m~ssage, if the trigger of the 
natural changes ~as a weak constraint; otherwise 
(semantic failure) it backtracks to a previous 
choice point. 
A~LYSIS OF CDNJUNL~IONS 
Before starting the description of the n~chan- 
isms adop~=d to analyze conjunctions, it is worth 
noting that the analysis of conjunctions was 
already mentioned in a previous paper (Lesmo & 
Torasso, 1984). The present paper represents an 
advance with respect to the referenced one in that 
new solutions have been adopted, which greatly 
enhance the homogeneity of the parsing process (not 
to mention the fact that the behavior of ~ parser 
was treated very sketchily in the previous paper). 
The presentation of the solution we adopted is 
based on the classification of sentences containing 
conjunctions reported in (Huang, 1984) : we will 
start from the simpler cases and introduce the more 
ccmplex examples later. A last remark concerns the 
language: as stated above, the FIDO system works on 
Italian; in order to enhance the readability of the 
paper, we present ~glish examples. Actually, we 
are doing some experiments using a restricted 
~glish grammar, but it must be clear that the 
facilities that will be described are fully i~@le- 
mented only for the Italian grammar (the cases 
where Italian behaves differently from I~glish will 
be pointed out during the presentation). 
As for all other syntactic categories, the 
category "conjunction" also has an associated set 
of rules: the set contains a single, very simple 
rule: it saves the conjunction in a global regis- 
ter, which is available during the subsequent 
stages of processing. %~e simplest case of conjunc- 
tion is the one referred to in (Fmang, 1984) as 
"unit interpretation" : 
(i) Bob met Sue and Mary in London 
Normally, the rules associated with hOLmS 
hypothesize the attachrrent of a newly created REF 
node to a connector that (if it does not already 
exist) is, in turn, created and attached to the 
nearest node of type REL above the current node (or 
to the current node itself if it is of type REL). 
After the analysis of "Bob mat", the situation of 
the parse tree would be as in fig.2.a (and p~l is 
the current node). Tne analysis of "Sue" would pro- 
duce the tree of fig.2.b. The noun rules have bee_n 
changed to allow for the attachment of more than 
one noun to the same connector (should a conjunc- 
tion be present in the register). In fig.2.c, the 
tree built after the analysis of sentence (1) is 
reported. 
It must be noted that the most common exar~le 
of natural change (the one called MOVEUP) is also 
useful when a conjunction is present. Cons ider, 
for instance, the sentence : 
(2) John saw the boy you told the story and the 
girl you met yesterday 
After the analysis of the fragment ending wir/n 
"story", we get the tree of fig.3.a (and REF4 is 
the current node). According to the previous 
disc-assion, the noun "girl" would be stored in a 
~EF node attached to CONN4. On the other hand, the 
semantics would reject this hypothesis, since the 
case frame (TO '~r: SUHJ/PERSON; DIROBJ/PERSON; 
INDOBJ~) is not acceptable. The portion of 
the tree representing "and the girl" would be 
'~ved up" and attached to CONN2, thus yielding the 
tree of fig.3.b (that would be expanded subse- 
quently, by attaching the relative clause "you nnet 
yesterday" to Faro'5). 
Unlike what happens in the previous cases, a 
new rule had to be added to account for the other 
types of conjt~ctions. This rule is a new natural 
change, that the system executes when the conjunc- 
tion implies the existence of a new clause in the 
sentence. ~he need for such a rUle is clear if we 
183 
REL~ ~¢ 
I soe I H I 
(a) 
ggL~~ 
(b) 
Fig.2 - 
I',-o NEET I,IHI,ITt 
¢oww:P ~ CONN~ 
(c) 
Different phases of the interpretation of 
the sentence "Bob met Sue and Mary in 
London". 
H means "head" and indicates the position 
of the node filler within the sequence of 
dependent structures. 
UNM means "Unmarked" and indicates that 
the corresponding verb case is not marked 
by a p~-eposition 
(a) 
(b) 
Fig.3 - Two phases in the analysis of the sentence 
"John saw the boy you told the story and 
the Eirl you met yesterday" (the subtree 
relative to "you met yesterday" is not 
shown). 
consider one of the basic assumptions of the 
parser. In a sense, the parser knows that it has to 
parse a sentence because, before starting the 
analysis, the tree is initialized by the creation 
of an empty REL node. Analogously, when a relative 
pronoun is found, the relative clause is "initial- 
ized" via the creation of a new empty REL node and 
its attachment to the REF node whictl the relative 
clause is supposed to refer to. The only exception 
to this rule is represented by gerunds and partici- 
ples, which are handled by means of explicit 
preconditions in the VERB rule set. Of course, 
this can give rise to ambiguities when the past 
indicative and the past participle have the same 
form, as in the well known garden path: 
(3) The horse raced past the barn fell 
In the case of sentence (3), the choice of the 
indicative tense would be made, and the past parti- 
ciple rule would be saved ~o allow for a possible 
backtrackLng in a s~nt phase, as would actu- 
ally occur in example (3) (we must note here that 
such an ambiguity does not occur in Italian). A 
further co~Tent concerns the relative clauses with 
the deleted relative pronouns (as in (2) above): 
this gaencmenon does not occur in Italian either; 
v~ believe that it could be handled by means of a 
184 
natural change very similar to the one described 
below. 
Wecan now turn hack to the prob1~ of c~m- 
junctions. Let's consider first a sentence where 
the right conjumct is a complete ~rase. 
(4) Bob mint Sue and Mary kissed her 
After the analysis of the sentence as far as 
"Mary", the stru~=e of the tree would be as in 
fig.2.c (apart ~ the subtree referring to "in 
Lond~"). ~ "kissed" is four~, no empty 
~ga_~ exists to ac~----.---~umte it, thus the natural 
cha.~es are triggered and, because of the preconai- 
tions, the new one (caLled De~) is executed. 
It operates according to the following steps: 
I) A conjunction is looked for in the right subtrse 
2) It is detached together with the structure fol- 
lowing it 
3) The conj~tion is inserted in the node 
the first I~ that is found going up in the 
hierarchy (in fig.2.c, starting from C~NN2 and 
going u~s, we find 1:m.'.1 and the node above 
it is TOP) 
4) A new empty REL is created and attac~ed to the 
L~d__e found in step 3 
5) The structure deteched in step 2 is attached to 
the new REL, inserting, when ~, a cc~nmc- 
tot. 
The e.~.~cution of INam~z~L in the case of example 
(4) produces the s~-uc~n~e depictad in fig.4, that 
is completed subsequently, by inserting "TO KISS" 
in REL2 and by creating the branch for "her" in the 
ususl way. 
~Wo more complex examples show that the abil- 
ity of the parser to analyze conjunctions is not 
limited to main clauses: 
(5) Henry heard the story that John toid Marl, and 
BOb told Ann 
With regard to sentence (5), wa can see the 
result of the analysis of the portion ending with 
"Bob" in fig.5.a. It is apparent that the execution 
of the steps described above causes the insertion 
of a new REL node at the same level of R~2 and 
attached to ~Y2; this seems intuitively acceptable 
and provides FIDO with a structure consistent with 
the ~sitive semantics adopted to obtain the 
formal query (Easing, Siklossy & Torasso, 1983). 
11"op l,l^No I,I 
I'm "e'TI IHITI I 1,1 
lUNM I '1 lu,,,,', lu',',"ltl 
leo,, I '1 I I I'1 
FIE.4 - Pamtial structure built durin E the 
analysis of the sentence "Bob met 
Sue and Mary kissed he~". 
An even more interesting exanlple is provided 
by the following sentence: 
(6) ~ ~-d the story John told Wary and Bob 
tola Ann his opinion 
~ere the I~TREL and MDVEOP cooperate in build- 
ing the right tree. What happens is as follows: 
after the execution of I~IREL (in the way 
described above) "his opinion" is attached to REL3. 
~he selection restrictions are not respected 
because four um-~rked cases are present for the 
verb "to tell" (including the elliptical relative 
extracted from the first conjtnnct), so the 
smallest right subtres ("his opinion") is m~ved up 
and attached to RELI; again, the hypothesis is 
rejected (three unmarked cases for "to hear"). The 
tree returns to the original sta~zs and MOVEJP is 
tried again on a larger subtree (the one headed by 
~mT~}. Since a conjunction is found in the node 
above REL3, it is moved t~o and the analysis 
finally succeeds. 
~he last type of sentences that we will con- 
sider involves gapping. An example of clause- 
internal ellipsis is: 
(7) I played football and John tennis. 
the name "John" is encountered, a ~it 
interpretation is attempted ("football and John ") 
and it is rejected for obvious reasons. The only 
alternative left to the parser is the execution of 
15~KTREL, which, working in the usual way, allows 
the parser to build up the right interpretation. 
Note that an empty node is left after the 
analysis of the sentence is completed, which is not 
done in the examples described above. This is han- 
dled by non-syntactic routines that build up the 
se,~ntic interpretation of the sentence (formal 
query oonstruction in FIDO). However the ac~al 
~rb is made available as soon as possible, because 
the interpretation routines do not wait until the 
analysis of the o~,,=nd is finished before begin- 
ning their work. 
As the reader will see frum the following 
examples, no ~uble is caused for the parser by 
the other kinds of gapping: 
- left-peripheral ellipsis with ~ NP-remn ns. 
For example: 
(8) Max gave a nickel to Sally and a dime to 
Harvey 
(unit interpretation "to Sally and a dime" 
attampted and rejected; I~E~L executed; the 
semantic routines also have to recover the 
elliptical subject). 
- left-peripheral ellipsis with one NP remnant and 
nDn-NP remnant(s). For example: 
(9) Bob met Sue in Paris and Mary in London 
(e~Jctly the same case as (8); the parser makes 
no distiction between NPs and non-NPs) 
- Right peripheral ellipsis concomitant with clause 
int~mm%al ellipmis. For example: 
185 
(I0) Jack asked Elsie to dance and Wilfred Phoebe 
(same processing as be~re; more complex semantic 
recovery of lacking constituents is necessary). 
Not very different is the case where "the right 
conjunct is a verb ~rase to be treated as a clause 
with the subject deleted". As an example consider 
the following sentence: 
(11) The ~sn kicked the child and threw the ball. 
In this case, the search for an empty REL node 
fails in the usual way and II~SERTREL is executed as 
discussed above, except that the ccmjuncticn is 
still in the register and no structure follows it, 
so that the steps 1,2, and 5 are skipped. 
Finally, the "Right Node Raising", exemplified 
(12) The man kicked and threw the ball. 
%T~ problem here is that the left conjunct is not a 
complete sentence. However, the syntactic rules 
have no troubles in analyzing it; it is a task of 
semantics to decide whether "the man kicked" can he 
accepted or not. In other words, "the ball" could 
he considered as an elliptical object in the first 
clause; although the procedures for ellipsis reso- 
lution are unable, at the present stage of develop- 
ment, to handle such a case, it is not difficult to 
imagine how they could be extended. 
To close this section, two cases must be men- 
tioned that the parser is unable to analyse 
correctly. In sentence (13) 
(13) John drove his car through and completely 
demolished a plate glass window 
a preposition (through) has no NP attached to it. 
The problem here is very similar to that of "dan- 
gling prepositions" (and, like the latter, it does 
not occur in Italian). A simple change in the syn- 
tax would allow a CONN node to be left without any 
dependent R~:. Less simple would be the changes 
necessary in the anaphora procedures to allow them 
to reconstruct the ~=aning of the sentence (the 
difficulty here is similar to the "Right Node Rais- 
CONM£ 
J t JN/~ 
R~-I=~ ~ ' 
r i'A,,,o I, I 
(a) 
RELI p 
I ,..,N: 
REF~. f,, 
Fig. 5 - Two phases in the analysis of the sentence: "Henry herd the story 
that John told Mary and Bob told Ann". 
186 
ing" discussed above). 
The last problematic case is concerned with 
multi-level gappings, as in the folluwing example: 
(14) Max wants to try to begin t~ write a novel and 
Alex a play. 
In this case, the insertion of an empty REL node to 
account for the second conjunct ("Alex a play") 
does not allow the parser to build a structure that 
corresponds to the one erased by the ellipsis. We 
have not gone deeply into this problem, which, 
unlike the preceding ones, also occurs in Italian. 
H~wever, it seems that, also in this case, the 
increased power of the procedures handling ellipti- 
cal fragments could provide some reasonable solu- 
tions without requiring substantial changes to the 
presented approach to parsing. 
CONCLUSIONS 
AS stated in the introduction, a proper treat- 
• ent of coordination involves the ability to inter- 
rupt the analysis of the first conjunct when the 
conjunction is found and the ability to analyze the 
second conjunct taking into account what happened 
before. 
~he system described in the paper deals with 
the two probl~s by adopting a robust and modular 
bottom-up approach. The first conjunct is extended 
as far as possible using the incoming words and the 
structure building syntactic rules. Its complete- 
ness and/or acceptability is verified by n~_ans of 
another set of rules that fit easily in the pro- 
posed framework and do not affect the validity of 
the other rules. 
~he second conjunct is analyzed using the s~me 
standard set of structure building rules, plus an 
excep~ion-~%ndling rule that accounts for the pres- 
ence of a whole clause as second conjunct. The need 
~o take into account what happened before is satis- 
fied by the availability of the portion of the tree 
that has already been built and that can be 
inspected by all the rules existing in the system. 
qhe paper shows that the approach that has 
been adopted enables the system to analyze 
correctly most sentences involving conjunctions. 
Although sane cases are pointed out, where the 
present i~plementation fails tm analyze a correct 
sentence, we believe that the solutions presented 
in the paper enlight some of the advantages that a 
rule-based approach to parsing has with respect to 
the classical grammar-based ones. 
V.Dahl, M.MmCord (1983): Treating Coordination in 
Logic Grammars. AJCL 9, 69-91. 
X.Huang (1984) : Dealing with Conjunctions in a 
Machine Translation Environment. Proc. COLING 84, 
Stanford, 243-246. 
L.Lesr~, L.Siklossy, P.Torasso (1983): A Two Level 
Net for Integrating Selectional Restrictions and 
Semantic Knowledge. Proc. IEEE Int. Conf. on Sys- 
tems, Man and Cybernetics, India, 14-18. 
L.iesmo, L.Siklossy, P.Torasso (1985): Semantic and 
Pragmatic Processing in FIDO: a Flexible Interface 
for Database Operations. Information Systa~s 10, 
n.2. 
L.Lesmo, P.Torasso (1983) : A Flexible Natural 
Language Parser Based on a T~o-ievel Representation 
of Syntax. Pro(:. ist Conf. ACL Europe, Pisa, i14- 
121. 
L.Lesmo, P.Torasso (1934): 
tally Ill-Formed Sentences. 
ford, 534-539. 
Interpreting Syntacti- 
Pro(:. COLING 84, Stan- 
L.Le~, P.Torasso (1985): Weighted Interaction of 
Syntax and Semantics in Natural Language Analysis. 
9th IJCAI, Los Angeles. 
F.Pereira (1981) : Extraposition Grammars. AJCL 7, 
243-256. 
F.Pereira, D.Warren (1980): Definite Clause Gram- 
mars for Language Analysis: A Survey of the Formal- 
ism and a Comparison with Transition Networks. 
Artificial Intelligence 13, 231-278. 
J.J.Robinson (1982): DIAGRAM: A Grammar for Dialo- 
gues. Ccmm. ACM 25, 27-47. 
R.M.Weischedel, J.E.Black (1980): Responding Intel- 
ligently to Unparsable InpUts. AJCL 6, 97-109. 
W.A.Woods (1973): An Experimental Parsing System 
for Transition Network Grammars. In R.R~stin (ed.): 
Natural Language Processing, Algorithmics Press, 
New York, Iii-154. 
187 
