Predictive Control Parser: Extended LINGOL

1. INTRODUCTION

The LINGOL, which was developed by V. Pratt, is a research tool for natural language processing. We implemented LINGOL on our T-5600 computer system about four years ago and used it for a while. The advantages of the LINGOL arc its program size, speed, and its neat format of grammar and dictionary. It is interes ting to note that the semantic in­ terpretation method of the LINGOL is simlar to that of Montague Grammar.

The result of our experiments, however, has revealed that Pratt's LINGOL has several de­ ficiencies mainly with respect to syntactic processing. One of them is that each augmented context-free rule does not enable us to examine their applicability. Another is that the morpheme analyzer of original LINGOL is too simple to analyze aggulutinative languages such as Japanese . In order to cope with these deficiencies, we have revised some portions of original L!NGOL and added new programs to it.

2. PREDICTIVE CONTROL MECHANISM

2. 1 <Advice> and <delayed-advice>

The Extended LINGOL incorporates a predictive control mechanism which enables us to examine the applicability of each rule in case of some situations. The string parser developed at New York University had implemented the same mecha­ nism in their top-down parser (1].

However, as the LINGOL uses both top-down and bottom-up parsing algorithms, the predictive control mechanism differs from that of New York University. Descriptive format of our diction­ ary is,

[<word> <syntactic-category> (<message-list> <cog>) < sem>]

Message-list is considered to be attached to the syntactic category of the <word> and is used later by predictive control mechanism as messages. (Fuct ions of <cog> and < sem> are the same as described in [3] and (4]) . The format of an augmented context-free rule in Extended

LINGOL is,

(<left> <right> (<advice> <cog>) <Sem>]

The <left>-<right> pair represents a context­ free rule of A ---+B (C). The <advice>, which is introduced in our Extended LINGOL, is an arbitrary LISP function for controlling parsing process. The evaluator of predictive control mechanism works as follows: For each <advice> or <delayed-advice> in rules,

if the evaluation value is true then do not apply the rule else apply it;

Suppose a Partially Parsed Tree with a root node E (PPT:E) is created at some intemediate stage of parsing. There are six possibilities to extend the tree. Four of them depend on the evaluation of <advice> in the following rules;

(Rl) A -+E or

(R2) A ~E F.

(See l'ig.l).

(3)

... ·---'

A

/ '\...,

6 ',!.'Goal E

(4) ~A*

F

6

Fig.l The result of the evaluation of advice

~)tv in Fig.l indicates that (Rl) and (R2) fail to apply. Fig.l(l) indicates that (Rl) applies to PPT:E. Fig.l(3) indicates that (R2) creates a new goal which predicts the next syntactic category F. In (4), a new goal is explicitly cancelled, while in (2) it is implicitly cancelled.

When a new goal is created as in Fig.l(3), we can record <delayed-advice> in the goal by us ing the Memo-Advice (MA) function in <advice> in the following way :

(MA <delayed-advice>)

The execution of <delayed-advice> is postponed until PPT:F will be created. (See Fig.2). Wi th respect to <delayed-advice>, there are two more possibilities in growing PPTs depending on the evaluation value of <delayed-advice>. The <delayed-advice> acts as though it were a look-forward demon which would be activated when a goal is satisfied later.

2.2 Control of Mes sages

In the field of advice and delayed-advice , we use messages to control parsing process. About 10 primitive functions arc prepared.

A. Creabng and Passing Me~-;ages: In <advice>, users can creat and pass any kind of mes sages from node to node upward in accordance with the growth of PI'T. There arc six primi­ tive functions as shown in Fig.3. The effects of the evaluation are also stated in Fig.3 .

B. Checking Messages: When applying a context-free rule to some PPTs and goals created so far, users can ask for messages at the root node of PPTs by using the function named QM. Recall the cases of Fig.l where (Rl) and (R2) have a very simple <advice> (QM 'm) .

[A E ( (QM 'm) . . ) ) ;A -E

[A (E F) ( (QM 'm) .. ) .. ] ;A --+E F If a mes sage m exist at the node E, (EVAL (QM 'm)) becomes true and two rules under consider­ ation can not be applied ((2) and (4)), other­ wise PPT:E grows in (1) or a new goal is created in (3).

C. Removing Messages: To remove a messages in the root node of PPTs, the function named RM is used.

3. EXAMPLES

In order to show how the predictive control mechanism works, we discuss two very simple examples, which inhibits the recursive appli­ cation of rules of left and right recursive definitions.

Example (a)

Let us consider the following rule. (R3) [NOUN (NLUN SUFFIX)

((OR (QM 'uncountable)

(QM 'suffix) (PMR 'suffix)) .. ) .. ]

and [estimation NOUN ((uncountable) .. ) .. ] (apple NOUN(() .. ) .. ]

[s SUFFIX ((suffix) .. ) .. ) Notice that the rule (R3) is left recursive, but it should not be applied recursively. The predictive control mechanism avoids the situation. The last three are from a dictionary.

• The <advice> in (R3) works as follows: If NOUN is not an uncountable noun and Noun is not followed by a suffix then create a goal by applying (R3) and pass a message named suffix upward if a goal SUFFIX is satisfied; else do not apply (R3);(See Fig.4(a)).

Example (b) The following rule (R4) is right recursive. (R4) (NOUN (PREFIX NOUN) ((MA (OR (QM 'prefix) (PM 'prefix)) ) .. ) ... I

The <advice> creates a <delayed-advice> (OR (QM 'prefix) (PM 'prefix)). By using Fig.4(b), it is easy to follow how the <delayed-advice> prevents the right recursive application of (R4).

4. CONCLUSION

We have discussed a new parser called Extended LINGOL which has been used in our laboratory for about 3 years. Predictive control mecha­ nism has offered us flexible methods to imple­ ment a grammar. As described in the preceding section, each context-·free rule works as an active process that can pass messages to an­ other process or creat a new process. The process can also notify the parser the appli­ cability of the rule attached. The newly created process works as if it were a look­ forward demon. The <advice> attached to each (context-free) rule expresses an action of the rule (or process). Semantic information will become available during parsing process through the message control mechanism if necessary.

Automatic segmentation algorithms in our Extended LINGOL are reported in [6). Various experiments have been carried out in our laboratory using Extended LINGOL. Some of them are reported in [5].

REFFERENCES

• [1) Grishman, R.: "Implementation of the string parser of English" in "Natural Language Processing", Algorithmic Press, 1973, 89-109.
• Heidorn, G. E.: "Augmented Phrase Structure Grammar", in Schank and Nash-Webber (Eds.) : "Theoretical Issues in Natural Language Processing", Cambridge, Mass. 1975, 1-5 .
• [3) Pratt, V. R.: "A Linguistic Oriented Programming Language", T.JCAI3, 1973, 372-381.
• Pratt, V. R.: "LINGOL - A Progress Report", IJCAI4, 1975, 422-428.
• [5) Tanaka, H., Sato, T. and Motoyoshi, r- · "EXPLUS--A Semantic Parsing System for .Japanese Sentences", 3rd USA-JAI'i\N Computer Conference, 1977, 236-240.
• [6) "Manual of Extended LIN(:OL", Machine Inference Section, Electrotechnical Laboratory, Tokyo, 1978 (in .Japanese version).