X-l

ISR-9
August, I.965
X.

THE REVISED SYNTACTIC PROCESSING FOR SMART
A. Lemmon

1*

Introduction
The purpose of this section is to giv<

rief description of theuse and operation of the syntactic processing
system•bhe new SMART

The philosophy and principles involved are the same as thosepreviously described in Information Storage and Retrieval Report No13.
TSR-5, 7, and 8. However, due to changes in the SMART system as a whole,the various routines of the syntactic section have been rewritten andexpanded, and their operating instructions changed.
section is thus not compatible with the old one*

The new syntactic

Figure 1 shows the

structure of the complete syntactic section*

2.

Use and Function of System RoutinesA.

BTOKUN (Binary-TO-KUN Converter)
This BTOKUN routine has been left relatively unchanged*

Its function

is to convert from the new SMART text format to the format accepted asby the Kuno Multiple-Path English Syntactic Analyser*
have been made in BTOKUN.
format.

Two specific changes

The first is to accommodate the new binary tape

The new BTOKUN routine exped

tpe

introduced as 12-word records, and each senten

in which documents are
sists of one record of

10-word items. All sentences received by BTOKUN are prepared for the
Analyzer by this routine*TEXT

LOOKUP

Thes.
K

Looked--up text
STAT. PHRASEFINDER
Freq. cluster/ LIB.S^TAFiD /BTOKUN 1^L >/rSuffix•* Meanings

\'
SETUP
SYNTAX
EDIT^t
1

1 COLLAT/

Synt . a Sern. for each>word ir
- 1
|CRITER tf_

N

MATCH I

butp jt, weighted
concepts. \\ MERGE |Overall Organizations of the Syntactic Section
Figure 1

1-3
The other major change consists in modifying BTOKUN for use with
the INOUT routine to effect all input and output processing*permits the computer ;This routine

y to compute and perform input and output

operations.
B.

CRITER (CRITERion tree routine)
The purpose of CRITER is to find occurrences of certain standard

phrases (known as "criterion trees") in the sentences of a text. CRITER
makes use of the output of the English Syntactic Analyzer. A phrase issaid to "occur" in a sentence if, for each "node" in the phrase, a corresponding node may be found in the sentence, such, that?
(1) No two phrase nodes have the same correspondent
in the sentence;(2) If a phrase node depends upon another, then thesentence correspondent of the first must dependon that of the second, and;
(3) The correspondent of each phrase node must satisfy
certain restrictions on semantic values and syntactic
function.
When a match has been found, the fact is recorded In an output
table. This table contains a list of concept numbers and also a weight
for each one. Each of the concept numbers refers to a concept embodied,not necessarily in one word, but in a phrase. The weight indicates how
frequently, and how significantly the corresponding concept appears.
Ordinarily a weight of twelve is allotted for each appearance of a concept,

The user may, however, select any of the numbers,3«>U,6,12,18,2lj or J48 as

the weight allotment of a given occurrence*
These options, as well as others to be described, are controlledby special indicators stored with the tree, called "output concept numbers"(or "OCN's").

Each OCN specifies (l) a concept number, and (2) the weightwith which the number is to be recorded*

These specifications are decided

by the user when he makes up his library of criterion tree phrases.
The user has another option for specifying output concept numbers.
Instead of specifying a specific number, for example "280," he may say"The concept number(s) already attached to the correspondent of tree node"1."

Thus the number recorded in the output table will come directlyfrom the sentence. This option is used in connection with contexts devoted
to important ideas, e.g., "the central problem is ..." or "the subject of
this paper is •••".

Thus, a criterion tree phrase might be arranged tomatch "the central problem is •..," with node 1 (say) corresponding to theblank.

Then the concept numbers of the correspondent of node 1 (that is,

the word in the blank) could be recorded in the output table. In this way
important concepts can be recorded according to this context ilone.
It is also possible to attach any concept number to the correspondent of any node.

In this way idioms may be translated and important

information moved from place to place in the sentence. Appendix 1 gives
an example of this option. The phrase "error correction" is assigned
concept number 280. Whenever this phrase appears in a sentence, the number
280 will be attached to the appropriate node in the sentence, so that itX-5
can participate in later processing©
In the above discussion the phrase "later phrase" has been used.
This is a reference to the fact that the phrases are stored on tape in anordered sequence0

Each sentence is matched against all the phrases in turn.

The next sentence is then matched against all the phrases, and so on.
Successive sentences do not affect each other in any way*

Successive phrases

do, however, influence each other?s matches as described above.
Matches in themselves result in no permanent record.. The final
output of CRITER is taken from a table (mentioned briefly above), initiallyempty, in which are recorded the desired output concept numbers. The output table contains only one entry for each such number; a total point countis kept for each entry and updated whenever required. At the end., of each,document, the data in the output table is sorted, into concept-number order
and written out on tape, together with the name of the document.
The output concept numbers thus come from two different sources:
either they are specified by the user, or else they consist of numbers
already attached to the correspondents of certain phrase nodes. Similar]/,the concept numbers specified in these ways may be used in either of twoways:

they may be inserted into the output table, or attached as new con-

cept numbers to the correspondents of certain phrase nodes. The same output concept number may be used in either or both of these ways*
A given sentence node may correspond to more than one concept
number*This may arise because of ambiguity of the word represented bythat node, or because other concept numbers have been attached, by previous
trees.

X-6
If the user specifies that the "concept number" of such a sentence
node should be recorded in the output table, all of the numbers will berecorded, but with a weight (point count) equal to the specified weight
divided by the number of recorded, concept numbers©

Thus the total weight

added to the output table will be as specified by the user©
C.

TRECND (TREe maker, CoNBensed format)
This routine writes user-specified phrases (criterion trees) onmagnetic tape, in the format expected by CRITER©

TRECND accepts cards(or, more precisely, card images on magnetic tape) and. interprets the user's
specifications, writing out trees according to those specifications©
A given tree has four main parts or specifications:(1)

individual identification!

(2)

structure;(3) node restrictions in terms of semantic and syntactic values;(ii) action to be taken when match is found (OCN'a).
Of these the program usually supplies (2) and parts of (3) and (k)•Theuser may overrule these standard interpretations at any time*

The program

uses a file of standard phrase types, at present li| of them©

These standard

types include all the structual information and whatever syntactic values
are required. Also, unless otherwise specified, all of the OCNfs will, be
attached to the correspondent of one particular node, known as the "head"of the phrase. In the case of a noun phrase, for instance, the head isthe noun©
as well.

Under user control the numbers can be attached to other nodes

X-7

The user supplies two kinds of information:(l) a six-characteralphabetic name; and (2) a serial number <> less than 32$768, The user may
elect to have the program assign a number one greater than the last serial
number, or to omit the serial number entirely*
however, be supplied by the user*

All other information must,

If it is omitted, the routine will

reject the tree by not writing it out, and by giving an error message.
The format of the card images accepted by TRECND is as follows.
There are four fields:(1) The BCD Name field, columns 1 through. 6C(2)

The OCN field, extending from column 7 up to
but not including the first column containing
I,D, (, or /•This field consists *of subfields,

each introduced by = 0(3) The Relations field, beginning with I,D, (, or/ , and extending to, but not including, thefirst $•

It is composed of one or more node

fields, separated by / <>(h)

The Specification field, beginning after the
first $ and extending up to, but not including,the first blank*

It is composed of subfields

separated by commas•
The BCD name field may consist of any six characters, except thatit may not be filled completely with zeros, or blanks or five blanks
followed by an asterisk*

Also it may not begin with a slash©

The output concept number field may not, be empty.
is composed of up to four types of sub-subfields:

Each subfieldX-8(1) A decimal integer. This is the concept number
which is to be written out. It irrust be thefirst sub-subfield, if present.

There may be

only one sub-subfi. Id of this type0(2)

The letter N, followed by a decimal integer
less than 16. There may be any number of these,subject to the restriction that no two may havethe same integer*

These sub~subfields identify

the nodes whose correspondents specify the OCN's*
No sub-subfield of this type may appear with oneof type 1; at least one must appear if there isnone of type 1.
(3) A period, followed by nothing or by a decimal
integer less than 16. There may be any numberof these, providing that they are all specified
by different integers*

Each one refers to anode to whose correspondent the concepts of thisOCN are to be attached*

If the period is notfollowed, by an integer,, it means that the standard"head" node is to be ignoredo(h)An asterisk, followed by a decimal integer or nothing*
Only one of these may appear.. The integer becomes thepoint count (weight) for this OCNe

If this field isabsent, a weight is automatically assigned so that the
total height of all OCNJs is 12c

All unspecified weights

will be automatically assigned the same weight. If theinteger is absent but the asterisk is present, a weightof zero will be assigned*
The program is designed to automatically make the most logicalinterpretation whenever no option is specified by the user*

Thus it isX-9

sufficient to have an OCN field consisting simply of one or more integers,
each preceded by an "equals'* sign (as in the old TRECNE format).

Each ofthese will be given a point count of 12/ (number of OCN's) and will be
attached to the head node of each phrase generated by this card image.
The relations field consists of "node" subfields*
field consists of an optional "relation" part*

Each node sub-

The connection part consistsof the letter I or the letter D, followed by a decimal integer denoting theparent (D) or ancestor (I) of the present node0

This part will ordinarily

be omitted and the information supplied by the prestored types. The relation
part consists of one or more "relations" enclosed in parentheses. Each
relation consists of one or more "generators" separated by commas. Generators
are of two types:(l) unsigned decimal integers, interpreted, as concept

numbers; and (2) any BCD character, enclosed between apostrophes, thecharacter being interpreted as a syntactic value*, There must be at least
one relation in the relations field©
The specifications field is as described in report ISR-8, Section
VI, except that type 0 may be specified, in which case the tree is constructed entirely from data given on the card, and that new tree types may
be constructed from the description in the relations field of the card,
including both the structural and syntactic information*

This is specified

by the last subfield, which consists of a decimal integer, followed by theletter T or P, followed by from 0 to 1$ distinct integers less than 16,
separated by commas0

The integer before the letter indicates the number of

the tree type being (re) defined; the numbers after the letter denote thekey ("head") nodes0

The program will write a message on the output

X-10
tape indicating that the new type has been defined* Also if the letter
is P 5 binary card images are written on tape Bk9 suitable for loading
the new types with the program the next time*
This description closes with some examples of criterion tree
formats and interpretations of the various card fields. The motivation
behind these fields has been discussed earlier (ISR~85 Section VI), and isalso taken up in Appendix 1 to this section0,JLU e >.) -:•TYPE lit<0 • • «JL.2 o o © — U • o <D3 (»S«) /D3

BCD Name('0') /

1UT1

/ $Second node field:
Node 2_ depends on
node 3> and node 2 ? scorresp. must havevalue f 0 !

No OCN field required
if new type only

First node field:
Node 1 depends on
node 39 and node
l's correspo musthave value *S*

Third node
field: empty

Specification
field: Type111 is beinp
defined.
Node 1 is the
key node.

(a) Definition of a new typei6

62

(l S f)(IQI)

Illustration of TRECND Input Formats
Figure 2

1
-J-

• •

*

b ••*

10©e«

15 * © ©

X A M P L . 95.3v

20.,

CJ

© <,• «

(5 \ 7 ) / (8|) $ lii / 9

BCD Name

OCN Field. One OCN;
9$ will be attached
to node 3 but not
the head node, andalso Riven a weightof 12First node field,
one relation: thecorresp. of node 1
must have value
or value 7

Second node field.
Corresp, of node 2
must have value 8
Specification field©
Tree is of type llj
and has serial number
9
new "head" specified

3ii <-

original headis suppressed

-—j*
""Q

t*) b i030(5,7)(b)(<0<)(8)Use of a defined t y p e . Data from t h i s card a r e
underlined;o t h e r d a t a comes from storage©

Figure 2 .

(continued)

X-12
3*

Technical Considerations
The present part of this report covers some special problems inconnection with the criterion tree routine, CRITER, The basic function of
GRITER is the interpretation of syntactic-function stringsa

With one

exception (the inclusion of conjunctions by the new CRITER), the interpretation of a sentence by the present CRITER version is identical with thatof the previous version0

However, the representations are different, andthe algorithm has been considerably streamlined,.
The new algorithm is based on the fact that each string in theanalysis corresponds to a path in the tree, ending at a unique node. (SeeISR-5, Secso II and III*) Moreover> the tree is considered to be orderedin such a way that the path corresponding to the first string is at theleft edge of the tree*, Successive strings (one per word) then correspondto paths further to the righto
Thus it is sufficient to determine where each path deviates fromits predecessor*
The strings are processed one by one in the order in which they
appear in the sentence * The tree structure of the sentence is built up
as the necessary information becomes available*. Thus each string corresponds to the right-hand edge of the structure as it exists at the time
the string is processed*
When a string is processed.., it is examined one character at a time,
starting from the left. The path corresponding to a string deviates fromits predecessor at the first character that differs from the corresponding

X-13

character In the preceding stringy and thereafter becomes a new branch to
the tree structure• A deviation also occurs at the last character if thepresent string is not an R, a deviation Is made at the preceding character.
The reasons for these actions are discussed In ISR-5* Sec. II, p. 12.
The new CRITER algorithm replaces the cumbersome TABLE of the old.
version, by three vectors: OLDBUF, DEPVEC, PARENT, OLDBUF holds thepreceding string, broken up into characters «> DEPVEC keeps track of theright-hand edge of the tree; the ith entry in DEPVEC is the number of themost recent node at depth, (or level) i„

Finally, PARENT shows the parent(if any) of each node*
Once a deviation is detected, new nodes are created, forming a newpath*

The numbers of a new node is one more than the total number of nodes

found, so far — that is, the numbers are taken in serial order.

The parentof each node is the most recent node assigned one level backj that is, theappropriate entry in DEPVEC. When a node has been created, in this fashion,
its number is recorded in DEPVEC, since it now becomes the most recent node
on its levele
These various actions are shown in the flowchart of Fig, 3«

Note

first that many boxes are abbreviated, e,g0 "Made new node11; also note thedouble subroutine linkage to MATCH, which actually finds occurrences, andfrom MATCH to HIT for each occurrence found*This scheme is used to dis-connect MATCH from the rest of the program, so that it can be programmed
separately.

HIT is the entry to CRITER which causes Information to berecorded from matches.

ENTERi, BOJDO INITIAL
SETUP

BOD
SET UPOUTPUT TABLE^A

BOS
CLEAR COUNTS OFINODES, DEPTHS, VALUESJiiM
TRIPTG«-0

ATTACH SEMANTIC VALSTO MOST RECENT NODET

ENDQ*—1
GET A WORD
End of(COLLAIQ
-*x

nf

E"d

End
of filenr\

sentence

wori oni^ document
GET A STRING CH0

ENDQ<— 0m

IS IT A BLANK ? X^-M

TRIPTG*— 0

ASL

No
+SL

0

LAST STRING LONGER;TRIPTG:0

0
>

yes

NO

CURRENT DEPTH:MAX DEPTH, OLD STRING
/

UPTOG

•1

PRESENT CHAR:
SAM LEVEL, OLD STRING

TR: PTG«—1•/

MAKE NEWNODE ON PRECEDINGLEVELPRESENT CHARsR
cdjUPTOG^^cfl—V
MAKE NEWNODE ON
CURRENT LEVEL

CRITER Flowchart
Figure 3

ITRIPTG-(UPTOG:

oj*

x-is

£i
GET A TREE? 10 ° 1 0 r e J BOK,
No more m a t c h e s ^MAT C H _7
f find la "match
No moreMT
GET AN OCN fe

OK.
ANY CORRESPONDENCESREQUESTED?

.NO-

RECORD THE
OCN WITH SPECIFIEDWEIGHT(VALUE VECTOR) <(VAL.VECT) v (DEST.VECT.)COMPUTE SOURCE AND
DESTINATION VECTORSJLIS SOURCE A NUMBER?

Yes FIND OR MAKE A

M ROW IN VALUE TABLE

RECORDALL VALS IN
TEMPVL WITH
WEIGHT "NO"No (node-type)
SCAN SEMANTICVALUES_NQ_

VI 4—(SPECIFIED WT.)
9| -T- (*t VALS IN TEMPVL)

more

OK.
(VALUE VECTOR)A (SOURCE VECTOR)/(VALUE VECTOR) <r—(VOL.VECT.)v(DEST.VECT.)
RECORD VALUE p
IN
TEMPVL

Figure 3 (continued)

X-16

V.

-#0F ITEMS INOUTPUT TABLE

0
SORT OUTPUTTABLE BY VALUEWRITE DOC. NAMECONVERT FORMAT AND
MOVE TO OUTPUT BUFFER

VJRITE OUTPUT DATA,WITH 'ZERO' SENTINELCLEAR OUTPUT TABLESTORE DOCUMENTNAME

0ENDQ U-TERMINATE ALL TAPES}
REWIND, ETC.

WRITE FINAL MESSAGE

DISABLE ALL IRAPS<^ENDEND y
Figure 3 (continued)

X-17

I STRING POINT]INFORMATION[ OLDBUF' DEPVECPARENTPARTIAL STRUCTURF]
.

ISA

t

1

I_

0

(1)

1,S

ili

0,1

(DQi

01

ISA

t

(S) O 2ISAt
RETRIEVAL

1,S,A

^~ 3

9 3

0A,2

l1 bO

t

(l) 0

IS

1,2,3

0,1,2

1,S,A

1,2,3

0,1,2

(A) 6 3
(1) 0 1(s) 6 2(A) 0 3

(S)

IV

t

1,S,A

1,2,3

0,1,2

I^A

1>U,3

0,1,2,1IVti(S) 6 2(A) O 3(i) Q i

1,S,A

IS

T

(D Q i(S) 0 2(A) 6 3

Q2

(1)

QI

(s)020U(A)0 3USEFUL

(V)

(DQi

1C
_1,V,Aik»3

0,1,2,1

1,C,A

1,5,3

0,1,2,1,1(s)p2bu(A) O35(A)Stages in Interpretation of Strings in a Sentence by CRITER
Figure \\

^)

X-18

(a) Sequence of processing(b)

Information

ISA -Retrieval

IS

IS

IV

UsefulIC

Correspondence of tra with sentence

Figure h (continued)

X-19

Figure I4. shows the successive contents of OLDBUF, DEPVEC, andPARENT during the analysis of a small sentence*h*Summary
The syntactic section of the SMART system has been revised andexpanded to make it compatible with changes being made in the system as awhole.

These revisions do not require fundamental changes in the algorithms,

but rather consist of changes in format details. While the routines werebeing rewritten, the opportunity was taken to streamline cumbersome
procedures and to provide new and more general capabilities.

X-20

APPENDIX 1

This appendix demonstrates the operations of CRITER using a simple
sentence, to show the addition of concepts to sentence nodes.

Word

StringConception

Structure

Error

ISM

69

Compensating

ISA

275

Codes

IS

281

(s)C) \

Have

IV

1019

(V)/r"^

Many

10A

1086

Applications

10

6U4

U)Qk
(A)t)3(a) The sentence and its analysisI

1*0(27$)VI

6?
(V)(306)(V)x

I 2 O (69) *(0)(69,7O)(275)(b) Trees for "error corections"(69,A)

ctr*(280,275',A)O^LIJ(281,3)^ C £(1019,V^C>(1)(1086,A)(6Ul,0f)
Matches of a Simple Sentence
Figure 5'

W ( 6 9 )X(c)Match with t h i r d t r e e , and new additions r e s u l t i ng-

Key: Concept numbers alreadyin the sentence, allowing
a match to occur, areunderlined - - -d) Trees for "correction code"(69,A) h(280,275,A)(282.28:1,S)m
i(1086,A)(6lli,0)Concept numbers attachedto the sentence as aresult of a match are
underlined
Matches are shown bybold lines
Q^^Q
tree nodes to which
sentence nodes correspond are shown inbrackets C HCount 12points for concept 282.

(e) Final match, with added concept no.

Note that the match described in (e) above would not have occurred
had the concept number 280 not been attached to node 3 of the sentence.

Figure 5, (continued)

X-22

APPENDIX 2

The binary format of the criterion tree phrases has been radicallychanged.

The correction matrices have been replaced by a vector of pointers,

identifying the parent (direct corrections) or ancestor (indirect), if any,of each node. This reduces the space required, by one half. Also, relations
generators are now recorded in chronological order (because of new tablesearching policies in CRITER), and no longer bear relation

numbers, which

are now implicit in context. Finally, the OCN's have been greatly expanded.
Each OCN now occupies a full word bearing all the information specified.
Examples of the new format follow:

Prefixn - nodes, r = #relation gens., 0 OCN's, s « serial #^parent of node n
Correction

Sign is + if correction is direct
Sign is - if correction is indirect

parent of node 2
parent of node 1

Binary Tree Format
Figure 6

X-?3

OCN

J

,

l-N

I

S

r_N i

s

[ I N "• "'"S ~ ~ W~| ~ 5 | vNe r\r,t r nf. Snodes] V r ~D~S
i i respondents

f-N i
l

Relations

l+K

V

1
W
1_ J
fW1

D
D

T

f\

r+K i

1-

i

supply the OCN.

N ID is a vector oT
nodes to whose c<spondents the OCN(s)wil] be attached.

|±K }
l+K 1
r+K" i+K 'IJ i;. 0 i ! < 3 i s a
ic number.

W is a weight code:

rJ

1 I III I I I I
'

• • 3

14

V

J '

o 3 h 6 12 18 2h UP
The generators ofeach
relation are consecutive. The ni.cn cf thela st ( or only) ;: < n< rai orin each relation is + ;other generators are -.
K is 0 if V is a concept number .
K is 2 if V is theactual representati onof a syntactic character,the number ofthe node to which
the relation applies.

Figure 6. (Continued)

X-2k

TYPE 1U D3 ('SO

/ D3 ("00/ $ Hi T 1

Structural corrections:

Relation generators.
Octal representation of
Octal representation of

i0i

62

»S«

Key node vector*
Octal hOOOO means bit 1(a)Type definitions as recorded in memory
EXAMPL « 95.3. (5,7) / (8) $ Hi / 9, 1+__ 1 _-&

1r~ -*• —' 1 1E
J X j A|M | P [L
I
0_
L±_ i
i

3_
3

+1

-BCD

MM

__J_
Lo
L
-01

-OCTAL)RELATIONS

2

00QU6 10 I
_i i
OCTAL

2

L_2'

p»00062(b)-BCD-OCTAL- OCN -

i

'0 !

8

10

E X A _[_M ! P ! L

1

+0,

zsrzn
a

CONNECTIONS

95 U nooooi

PREFIX

1

1

-o|

1—

5_

+2_JX)0062

10+2!p0Qli6
^
OCTAL

,0
'—

1
2

lQ(5,7)
2 6(8):(5,7)0S')O O (8)C0-)(No node r e c e i v e s conc e p t number 9 5 , s i n c etype 1 has no node 3)

Binary formats a s w r i t t e n on tapeS p e c i f i c Examples of Binary Tree Formats
Figure 7