Augmenting ATNS

AUGMENPN<l ~ Tim Finin an George Hadden Coordinated Science Laboratory, University of Illinois Urbana, Illino1s 61801

Augmented Transition Networks (ATNs) have become a popular and effective tool for constructing natural language understanding systems . Our own system, PLANES [Waltz 76] is based on a large "semant1c grammar" which is implemented as an ATN network. In developing our system, we were frustrated by numerous problems and shortcomings IN the basic ATN formalism. Consequently, we have augmented and extended the model to overcome some of these problems. We have also developed an optimizing compiler for ATN networks which translates them into LISP functions and an interactive program which allows one to easily extend and modify an ATN grammar.

Some o the extensions are relatively simple: the inclusion of new arc tvpes such as PHRASE (which matches two or more input words) and ROOT (which matches on the root form(s) of the current input word). Others have involved re-examining the basic ATN mechanism in order to alleviate more fundamental problems.

Extens}ons iQ ~ AIH ~

We have extended our ATN system to provide several control primitives which can be used to dynamically prune the tree of decision points on the developing "parse." One prirniti ve, FAIL (included both as an arc type and as an arc action) can propagate a failure message to any point on the decision tree. Other primitives allow one to save environments, both control and var ia.ble bind in~. This allows one to suspend the processing act1vated by a specified PUSH arc or action and to continue parsing as if it had failed. If subsequent attempts to find a parse fail, the suspended processing will automa.tically be resumed in the same environment.

Even with the ability to control backup, we have found that the ATN model still suffers from a paucity of control primitives . Evaluating an ATN state is conceptually a simple process in which one evaluates each arc leaving a state until one is found which can be taken (leading to a new state to be evaluated) which does not return failure . Thus the basic control primitive is the IF-THEN-ELSE-IF-ELSE ... applied to the arcs of a state. We have found it convenient to add the ability to conjoin or disjoin bundles of arcs leaving a state. For example, it is quite common to have a group of arcs leaving a state in which only one arc can possibly be taken.

In the standard ATN formalism, there is no easy way to encode the knowledge that if one of these arcs can be followed but eventually leads to failure 1 then the other arc(s) can not possibly be followea. Our ATN system supports a SELECT construct which will only allow one arc in the bundle to be followed. The SELECT construct has the additional benefit of signaling to the reader that the governed arcs are locally exclusive possibilities, distinguishing some of the deterministic from the non-deterministic aspects of a grammar.

In our own work we use long sequences of sin~le-arc states to parse special constructions or 1diomatic phrases. This auickly results in a spaghetti like network which is d1fficult to read and understand. To avoid this situation and to keep together code which logically belongs together, we have defined an AND construct which conjoins a bundle of arcs into a single unit. The destination of each arc in the bundle (except for the last arc, of course) is just the next arc in the bundle.

These extensions to the ATN model have been built into an efficient interpreter (written in MACLISP) which uses a simple recursive technique for simulating non-deterministic automata.

Anot er major componen o our ATN system is an optimizing compiler . ~hich translates A~N networks into compact, eff1c1ent LISP code. Th1s LISP code can then be passed through a standard LISP com{>iler to produce machine language code. Compilat1on of the ATN networks used in the PLANES system and several other lar~e parsing networks has resulted in correspond1ng machine language

A Co~piler ~ AIH Net~or~s

code which achieves a speed-up factor of 5 to 10 and a size reduction factor of up to 1/2. The translation of an ATN network into LISP code is straightforward processf each state in the network resulting in a simPle L SP function. Our compiler, however, attempts to produce ~f~ici~nt code by applying three sets of . opt1m1zat1on (expressed in a simple pattern match1ng language) rules at different stages of the translation.

The first set of rules defines source-to-source transformations on ATN networks and individual ATN states. For example, one rule will bundle any adjacent word arcs of a state into a single SELECT arc if the set of words tested bv the arcs are disjoint. ·

The second set of optimization rules is applied as the ATN network is translated into LISP code . The domain of these rules is the set of ATN arcs. For example one rule carefully examines the condition and actions on an arc to determine if they might cause a side-effect (e.g. set a register). If no side-effects are possible, then code for generating a new register context need not be included .

The final set of optimization rules defines LISP source-to-source translations which result in faster and/or more compact code. This set of rules also includes transformations which can optionally "open code" the more common built-in ATN actions (e.g. setting or accessing a re~ister).

~eave developed a special purpose editor, NETEDI [Waltz 76] [Hadden 77], which knows about the structure of ATN's and takes advantage of their redundancies.

- A N~twork .El1ilQ.r_

NETEDI expects as its main input a list. Each element of this list corresponds to a new arc in the ATN with the following exception: if some initial se~ment of the in{>ut list would correspond to a set of arcs already 1n the ATN, no · new arcs are added for these. The input list can be as simple as a list of words which form a sentence or phrase or complex enough to form any possible arc -- complete with embedded tests, LISP expressions, and transition modes.

Consider one of the elements of the input list. If it is an atom which begins with a "&" it represents a PUSH arc. When NETEDI sees one ot these, it adds register-setting code to the PUSH arc; the register will have the same name as the subnet PUSH-ed to. Any other atom in the input list represents a WRD arc.

Any arc (includin~ WRD and PUSH) can be represented by includ1n~ its name as the first element in a list, preced1ng the name with a ":" and putting the rest of the arguments in the list. For example, "(:CAT PREP)" would form a CAT (for category) arc which recognizes prepositions . So "((:CAT PREP) &NP)" would produce the code required to recognize prepositional phrases assuming the ATN contained a state called - ,&NP" which is the first state of a noun phrase recognizer.

RElE~~~C~S

[Gabrieabriel, R.P . and Finin, T.W.; "The LISP ~ditor"; Working Paper 1, Advanced Automat1on Group, C.S.L . , Univ. of Ill · 1975. . ,

[Hadden 77] Hadden, G.D.; "NETEDI: An Augmented Transition Network Editor", MSEE Thesis Univ. of Ill.· 1977. '

[Sussman 72] Sussman, G.J. and McDermott, D.V.· "From PLANNER to CONNIVER -- A Genetib Approach"; Proc. FJCC; 1972.

[Waltz 76] Waltz, D.L., et.al.; "The PLANES System: Natural Language Access to a Large Data Base"; C.S.L. Technical Reoort T-311· 1976. . I

The work described in this report was supported by the Office of Naval Research under contract number N00014-67-A-0305-0026.