A Deterministic Syntactic-Semantic Parser

1. Look ahead and semantic ambiguity

To show the connection between look ahead and choice or a meaning representation, let us consider the two sentences: "John makes a program in Simula" and "John makes a program conscious ".

Each sentence corresponds to a dirrerent mea­ ning or 'to make' and it is necessary to know what comes arter the rirst syntactic object to resolve the ambiguity . So , this part or the sentence should be processed berore choosing a meaning for the verb . The look ahead racility permits to examine simulta­ neously the 1st and 2nd complements. Looking at this latter , one can decide between 'makel ' and 'make2' and correctly attach the semantic structures. In case or truly ambiguous sentences, what remains are syntactic and semantic prererence heuristics.

2 . Interruption rules

We want to make it possible ror a structure to wait completion or another one and resume then . Ir SO , Sl , S2 , S3 are the viewed structures (the cur­ rent one plus the 3 in the rield of vision) and Rl the rule: IE Sl is a NP & S2 an adjective & S3 a PP, THEN ... ; and, ir this rule being active the rield or vision is:

SO=(VP( ... (Verb:MAKE))) , Sl=(Article:A) S2=(Noun:PROGRAM) , S3=(Adjective:CONSCIOUS)

then , it is visible that Rl does not apply , ror Sl is not a NP. So, t he NP and PP have to be generated rirst . This will be done by means or:

* R2: IF Sl begins a NP THEN generate a new pp & insert it berore Sl*& activate NP rules. IF S3 * begins*a PP THEN generate a new pp & inR3 : sert it berore S3 & activate PP rules.

R2 and R3 must be active at the time as Rl . There is no need to order them since t he conditions in Rl will be satisried only after R2 and R3 are applied . When they apply, they interrupt the development or the active structure by creating the NP and PP , and acti­ vating corr esponding rules. Once the NP and PP are detached, the interpreter goes back to Sl and arplies Rl.

C. Quasi simultaneous executi on**

This is another original reature or our parser. As we have shown , the stack mecanism does not permit the correct recognition or the end or a constituent

* These rules have a variable ($) in this place: ~ it appl ies either ir Sl or S2 or S3 matches the con­ dition part ( cr ) . This seems an improvement en tte "attention shirting rules" developped by Marcus.

** Inspired by SIMULA

"Quasi simultaneous" generation brings a new solution to this problem: a developping structure can be detached as soon as possible and elaborated latter if it is needed. This makes possible more in­ telligent choices in the situation of complex attach­ ment mentioned above: when attaching a new structure, the parser may consider all the previously detached ones.

Two operations are involved: detach and ~· They are to be performed in following cases: 1) Creating a new structure; means detaching the cur­ rent one before activating the new one. 2) End the current structure, which is then detached; the previous one being resumed. 3) Explicit detach instruction in a rule, implying that the last detached structure is resumed. 4) Similarly, explicit resume instruction in a rule.

Let us have some examples: "le cahier de l'etu diante que Jean a examine." ("The note book of the girl that John examined-'it'.") (In French, the verb has a mark permitting to distinguish between "exa­ mined it", the note book and "examined her",the girl)

We see that: .a deterministic processing of the relative clause needs to wait for its attachment until one has treated the verb, which has a gender mark capable of indicating the correct attachment . . "To examine" has several meanings depending on what is examined. The choice of a certain meaning needs a recognition of the actual object of examine, that is equivalent to the attachment of the relative clause. Here we have a couple of contradictory requirements.

Let us detail how a quasi simultaneous treat­ ment can get us out of this predicament. When the verb of the relative clause is seen,certain syntactic and semantic features of its object can be recognised; the parser then detaches the relative clause and resume the last seen NP, here, "the girl". There is no match with the 'it' mark, so the relative clause cannot modify 'girl'. This NP is then termi­ nated, and, the NP corresponding to 'note book' is resumed. This time, the relative clause is accepted as a modifier and can itself be resumed in order to solve the ambiguity in 'examine'.

We can also give examples of PP attachment: "John puts the wine on the table." "John drinks the wine on the table."

As soon as the noun 'the wine' has appeared, the NP can be detached, permitting the PP 'on the table' to be started. When considering possible at­ tachments for this PP, the rules allow to take into account the features of the verb.

The differences between 'put' and 'drink' ex­ plains that it is possible to attach the PP to the verb in one case and to the NP in the second case.

CONCLUSION

After examining the main factors of non-deter­ minism in parsers, we tried to solve the correspon­ ding problems. Actual experimentation confirms the interest of such an approach. We made a SIMULA pro­ gram of about 3000 instructions which parses sen~ tences of about 10 words in 2 seconds on a PDP10 (using an approximate total of 100 K core).

A LISP version is being considered.

The present conceptual representation permim to consider synonymy, homonymy and selection restri~ tions. Moreover, in a perspective of integration of the domain knowledge to linguistic competence, this representation (or a more frame-like one) will make possible not only these tasks but also more sophis­ ticated and useful inferences.

The program is already able to process the French forms of every example mentioned in the text, and we hope to make it usable to other re­ search teams in the next future.