TEACH ATNSUM (ATN SUMMARY) Chris Mellish February 1983
This file gives a short summary of a small subset of the ATN formalism.
For more details and an introduction, see * ATNS and especially the
references cited in it. This summary is necessarily simplified and
contains a core that is probably present in most ATN implementations,
even though all ATN systems differ in details. It is mainly the LISP
notation for ATNs that is described. The alternative diagrammatic
notation is usually easier for people to read, but is normally used only
as a device to summarise an ATN, since it does not readily show all
relevant detail.
--- NOTATION -----------------------------------------------------------
This summary will make use of a number of notational devices. Any string
of characters in between < and > are supposed to stand for any member of
the class specified, which must appear in this position. Thus, for
instance, one could describe the format of the VED command in POP-11 by:
ved <filename>;
This does not mean that one has to literally type the characters "<",
"f", etc. after the string "ved". Rather, one types any file name in
this position. A second convention concerns the use of the symbol "*" to
indicate that any number of items of a given class can appear in some
position. Using both notations together, the following:
vars <variable name>* ;
indicates one possible form of the POP-11 VARS statement.
--- THE NETWORK AS A WHOLE ---------------------------------------------
An ATN as a whole is a list of nodes. These are written in LISP notation
between brackets, and separated by spaces. I.e. the structure of the
network is:
( <node>* )
For example, the following are possible forms for an ATN:
( <node> )
( <node> <node> )
( <node> <node> <node> )
................
A node is a list consisting of the name of the node followed by the
representation of the arcs that leave this node, ie:
(<node name> <arc>*
So the following would be a node with 4 arcs leaving it:
(<node name> <arc> <arc> <arc> <arc>)
--- THE FORMAT OF ARCS -------------------------------------------------
Each arc specifies a special condition that must be satisfied for it to
be followed and a special action to be performed, as well as (usually)
an additional test and additional actions to be carried out when it is
traversed. We consider here 5 kinds of arc:
(WRD <word> <test> <action>*
This can be traversed if the next word in the input is the one
specified and in addition the test specified is true. The special
register * is given this word as its value and the input pointer is
moved on.
(CAT <category> <test> <action>*
This can be traversed if the next word in the input is of the
specified syntactic category and also the test is true. The *
register is given the word as its value and the input pointer is
moved on.
(PUSH <node name> <test> <action>*
This can be traversed if the test is true and the network starting at
the node named can successfully process part of the input string. If
this is so, the actions are performed with * set to the result
returned by that network. The input pointer is moved on as directed
by the path through the subnetwork.
(POP <value> <test>)
This can be traversed if the test is true. It indicates that the
current network has successfully processed part of the input. The
value specified is returned as the result of this work. The input
pointer is not moved.
(JUMP <node name> <test> <action>*
This can be traversed if the test if true. The arc has the node
specified as its destination. The * register and the input pointer
are not altered.
--- VALUES (FORMS) -----------------------------------------------------
In order to build syntax trees and other structures, an ATN must be able
to pass pieces of information around from place to place and to build
larger structures from smaller ones. There are various ways of
specifying these values.
(GETR <register name>)
This refers to the current value of the register named
*
This refers to the current value of the * register (it is a shorthand
for (GETR *))
()
This refers to the empty list (NIL)
(QUOTE <pattern>)
This refers to the constant value provided by the pattern. Constant
values are treated in this way to distinguish them from values that
have to be treated specially - a constant value stands for itself,
whereas something like "(GETR NP)" has to be specially interpreted.
However, constants appearing in BUILDQs (see below) do not have to be
explicitly marked.
(GETF <feature name> <register name>)
This refers to the value of a given property (eg plurality) of the
value of a register.
(BUILDQ <pattern> <register name>*
This refers to a structure built up from the given pattern by
substituting values of registers for occurrences of the symbol "+".
The value of the first register is substituted for the first "+", the
value of the second for the second, and so on. For example, if
register "A" has the value "(CAT)" and "B" has the value "DOG" then
the value of:
(BUILDQ (F + +) A B)
is (F (CAT) DOG)
(APPEND <list of values> <value>)
This refers to the list formed by appending the single value to the
end of the list specified.
--- TESTS --------------------------------------------------------------
The tests on ATN arcs either look for particular relationships between
different values, or are composed by logical operations of tests of that
form.
T
This is the test that always succeeds (T stands for "true")
(EQ <value> <value>)
This is the test that the first value is the same as the second
(AND <test> <test>)
This succeeds if the first test succeeds and the second test succeeds
(OR <test> <test>)
This succeeds if either of the two tests succeeds
(NOT <test>)
This succeeds if the test specified within it does not succeed
--- ACTIONS ------------------------------------------------------------
The actions on ATN arcs cause values to be associated with registers, or
particular events to occur.
(SETR <register name> <value>)
This causes the register to be set to the value (assignment)
(TO <node name>)
This causes processing of the network to continue from the node
named. Every arc except a JUMP or POP arc must have one of these as
its last action.
--- EXAMPLE ------------------------------------------------------------
Here is an example of a simple ATN, expressed in the LISP notation and
partially summarised in diagrammatic form.
(
(s (push np t (setr np *) (to s_np)))
(s_np (push vp t (setr vp *) (to s_vp)))
(s_vp (pop (buildq (s + +) np vp) t))
(np (cat det t (setr det (buildq (det *))) (to np_det))
(cat npr t (setr np (buildq (np (npr *)))) (to np_np)))
(np_det(cat n t (setr np (buildq (np (det +) (noun *)) det))(to np_np)))
(np_np (jump np_np1 t (setr pps ())))
(np_np1 (push pp t (setr pps (append (getr pps) *))(to np_np1))
(jump np_end t))
(np_end (pop (buildq (np + (pps +)) np pps) t))
(vp (cat verb t (setr verb *)(setr pps ())(to vp_v)))
(vp_v (push np t (setr obj *) (to vp_np)))
(vp_np (push pp t (setr pps (append (getr pps) *))(to vp_np))
(jump vp_np1 t))
(vp_np1 (pop (buildq (vp (verb +) + +) verb obj pps) t))
(pp (cat prep t (setr prep *) (to pp_p)))
(pp_p (push np t (setr np *) (to pp_pp)))
(pp_pp (pop (buildq (pp (p +) +) prep np) t))
)
*------* *------* *------*
| | NP | | VP | |
| S |---->-----| S/NP |---->-----| S/VP |----->
| | | | | |
*------* *------* *------*
*------* *--------*
| | DET | |
| NP |---->-----| NP_DET |
| | | |
*------* *--------*
| |
| |
NPR | *-------* | N
| | | |
`-->--| NP_NP |--<--'
| |
*-------*
|
|
.....
--- C.all/teach/atnsum -------------------------------------------------
--- Copyright University of Sussex 1988. All rights reserved. ----------