ISR-7

June 196U

VI-1

VI.

SYNTAX AND CRITERION PHRASE PROCEDURES
Alan Lemmon

1.

Introduction
The syntactic procedure incorporated into the SMART system may

be separated into three distinct parts. The first is an editing program(BT0KUN) which converts binary data produced by the SMART dictionary lookup process into the binary coded decimal (BCD) form required by the syntactic
analysis programs. The second is the Kuno Syntactic Analyzer, described inReports NSF-8 and NSF-9 by the Computation Laboratory of Harvard University,and not further discussed in the present report. 1 ' 2The last and functionallymost important part of the syntactic procedures deals with the comparison of
selected, syntactically analyzed sentences extracted from the documents witha dictionary of so-called "criterion" trees or phrases. These phrases arepreanalyzed and furnished with concept indicators.

If the proper match is

obtained between a given sentence in a document and a criterion phrase, thecorresponding concept indicators can then be used as additional concept
indications for the document.
In the present section the input editing (BT0KUN), as well as the"criterion" routines are described in detail. The actual sentence matchingprocedure and the methods used to setup the criterion tree dictionary arecovered in later sections by Sussenguth, Evslin and Lewis, respectively.

VI-2

2.

The Input Editing Problem
The SMART system processes data largely in binary form. However,the syntactic analyzer used by the system expects to receive input data in
BCD form.

For this reason, a code conversion operation is necessary.

Additional format changes are, however, also required:in the first place,a selection must be performed to obtain those sentences from a document
which are to be syntactically analyzed.
code construction must be effected.

Second, and more importantly, aIndeed, the dictionary supplies syntactic

codes for the stems of words, and also identifies the suffix (if any); theanalyzer, however, requires single codes giving information assembled fromboth the stem (i.e. part of speech) and from the suffix (tense and number).
It is thus necessary to correlate the syntactic information pertaining tostem and suffix before the analyzer takes over. BT0KUN is a routine tohandle these conversion tasks.
The details of the input format required by the analyzer are given
in NSF Reports 8 and 9

15 2

and in the manual of operating instructions

supplied with the syntactic analyzer.

Basically, the form is as follows:(1) A ,rstart" sentinel (one record).
(2) Sentences:(a) A count of the words in the sentence (one record).
(b) The words of the sentence.

Several records may

exist for one word, showing different possible
syntactic types (codes) for that word.
(c) An "end of sentence" sentinel (one record),(3) An "end of text" sentinel (one record).
(k)

End of file.

VI-3
The syntactic codes used by the syntactic analysis programs arechosen from a l i s t of about 180 BCD symbols.

Each of these indicates ap a r t of speech, and, if the word i s a noun, pronoun, or verb, then the tense,
number, and/or case are also given.

Fortunately, as w i l l be seen, thearrangement in the l a t t e r case i s simple and d i r e c t (see Table 1 ) , and corresponds rather closely to the organization of the output of the lookup programused in SMART.
Three different inputs are needed by BT0KUN.

The f i r s t i s , of course,

the t e x t as recorded on magnetic tape in t e x t order as nine-word binary items.
Each item corresponds t o one t e x t word, and has the following format:(1)

Four binary words, consisting of 2k BCD characters which
store the text word i t s e l f :

(2)

(3)

One binary word:(a)In the decrement (position 3-17), the numberof the sentence;(b)

In the address (position 21-35), the p o s i t i o nof the word in the sentence.

Two binary words, consiting of six 12-bit bytes, each ofwhich represents a "concept number" or "semantic value";(k)

Two binary words, divided into nine 8-bit bytes:(a)Eight bytes (6I4. b i t s ) , part of speech code;(b)

One byte (eight b i t s ) , identifying the l a s t
suffix of the word, i f any.

These nine-word items are recorded consecutively on magnetic tape.
does not require any special blocking.

BT0KUN

However, a t most 1,000 nine-worditems may appear on the t e x t tape ( i . e . 9,000 binary words).

vi-Jb.

Infinitive(I)

Singular

PluralEitherPast Present
Part. Part.

1

III

VI1S

viip

VI1C

PH

RI1

GI1S

2

112

VT2S

VI2P

VI2C

PI 2

RI2

GI2S

3

113

VI3S

VI3P

VI3C

PI 3

HI 3

GI3S

1

IT1

VT1S

VT1P

VT1C

PT1

RT1

GT1S

2

IT2

VT2S

VT2P

VT2C

PT2

RT2

GT2S

3

IT3

VT3S

VT3P

VT3C

PT3

RT3

GT3S

k

nh

VTitS

VTliP

VTUC

PTli

RTii

GTliS

$

IT5

VT5S

VT^P

VT^C

PT5

RT5

GT^S

6

IT 6

VT6S

VT6P

VT6C

PT6

RT6

GT6S

6-1

IT6 1

VT6S1

VT6P1

VT6C1

PT6 1

RT6 1

GT6S1

7

IT 7

VT7S

VT7P

VT7C

PT7

RT7

GT7S

7-1

IT7 1

VT7S1

VT7P1

VT7C1

PT7 1

RT7 1

GT7S1

Type

Intransitive

Transitive

F i n i t e Forms

Nouns
Type

Singular

PluralEitherAny noun use

N0US

N0UP

N0UC

Subject or o b j e c t

N0VS

N0VP

N0VC

Numbers

NUMS

NUMP

NUMC

Organization of Syntactic Word Class Codes for Input
to Syntactic Analyzer
TABLE 1

Gerundvi-5
Foil coring the text, a file of up to £0 sentence numbers is required,preceded by a load command to load the file. The load command stores in its
decrement a count of the number of sentences (N £ 5>0) which are to be processed by the syntactic analyzer, and the address part of the load commandcontains 77i±6lg-N. Each sentence number, within the table, refers to one of
the sentences to be analyzed, and the program assumes that one sentence isincluded in the text for each number in the list.

In order to be properly

processed, the numeric codes must appear on the list in increasing numericorder.
The last input file required by BT0KUN is a file of suffix codes,
furnished as part of the SMART library tape (tape B£).

This file (the secondon the tape) consists of two records:(1) Directory:(a) 2^6 words, one for each suffix numbern(0 i:n ± 225), to indicate (in the decrement)

how many codes pertain to that suffix,
and to refer (in the address) to locations
above octal 67372.
(b) One word, whose decrement is the sum of
the decrements of the preceding 2^6 words,
and whose address is 67372.

This word serves

as an 1-0 command far the next record.
(2) The list of suffix codes.
This record contains as many words as are referred to by the directory.
of these suffix codes consists of one binary word.

Each binary word

Each

is

interpreted as five BCD characters, followed by five bits, followed by one

VI-6

blank bit*

A given suffix code is derived from a complete syntactic codeby judiciously replacing some of the characters of the original syntax
code by zeros, and by indicating the pattern of replacement in the fivebit byte which is appended.

Each bit within the five bit part is zero

if and only if the corresponding BCD character which precedes is zero. The
final (sixth) bit is always set equal to one. The construction of thesuffix code is illustrated by the examples of Fig. 1.

Suffix
No suffix

Codes
000S0

00010 1.

^ ^ ^ Sixth

VOOPO 10010 1,100 010010 1,10010 1,POO 010010 1

- S

vooco
vooso

10010 1,000P000010 1- ING

GOO SO 10010 1,

R00 010010 1 ^

V

ps.

- ED

- AL

•

ADJ

y

11111 1Five charactersderived from fullcode(a) Suffix codes

Example and Interpretation of Partial(Suffix and Stem Codes)
Figure 1

Five bits b l t
showing patternof zero-substitution

VI-7

Stem

Codes

ADD
BE

0T10

01101 0BEO

11011 0CAPIT-

N0UO 11101 0, 0T10 01101 0

ACT

N0UO 11101 0, 0110 01101 0

M0USE

NOUS 11111 1

MICE

N0UP 11111 1(b) Stem codes

Original code:

VT1S_

11111 1

Zeros inserted:

0..0.

0..0.

Partial code
resulting:

0T10

01101 1zeros correspond(c) Meaning of parts of apartial code
Figure 1 (continued)

3.

Internal Processing - The BT0KUN Routine
The input files are first read in, including the text, the list ofsentences to be processed, and the suffix code list. An initial sentinel isthen written on the output tape.
The routine now takes the first entry from the list of sentence
numbers, and retrieves the corresponding sentence (using the fifth word in

VI-8

the nine-word items as key).

When that sentence is found the number ofwords contained in it is counted and the count is written on the output
tape.

The words in the sentence are then processed one by one, to con-struct the corresponding complete syntactic code.
Each of the first eight 8-bit bytes (in the last two words of anine-word item) represents one of about 180 stem syntax codes. Their
format is similar to that used for the suffix codes: five BCD characters,
followed by six bits.

Again the five characters are derived by substi-

tuting zeros for certain of the characters in a complete code. The next
five bits have the same meaning as before. The final bit, however, is"one" only if no substitutions have been made in the construction of thecode.
The program can now capitalize upon the fact that information
can be extracted to some extent independently from stem and suffix codes.
Consider, for example, the procedure pertaining to verbs. Reference toTable 1 shows that the first and fourth characters of a given syntax code
indicate the mode and numberof a verb, and can thus be derived exclusively

from the suffix (see Fig. 1(a)). On the other hand, the second, third, andfifth characters indicate the type of stem and can thus be formed independentlyof the suffix.
For a word such as ADDED, appearing in the input, the dictionary
lookup program (Sec. IV) produces a nine-word item of the following form:
Sentence number/
Word number
ADDED

1

[S

2

3

h

W|

5

~

...

~T

|Ql|3

... QQ1|

~

~

VI-9
where 0)4.3 is the numeric code for Tl verbs, and 001 is the code of the suffix-ED.
Under 0U3 in the table of stem codes (which is a part of the BT0KUN program),
BT0KUN finds "0T10 01101 0". Under suffix number 001 the program finds"V00C0 10010 lM and MP00 0 10010 1" . The stem code is checked against eachof the suffix codes to see if they are exactly complementary, as in theexample shown:

Stem code denoting L_» 0T10 o n o i 0
Tl verbJ

0T10 01101

0Suffix codefor past)
parti7
Suffix code showing)
Trnnpn l n m n 1 partiH^VOOCO 10010 1 ciple^P00_0 10010 1
f i n i t e form
VT1C JL1111 1

PT1

11111 1

When such complementary pairs are found, they are combined, and the result
is taken as a complete syntax code. For the example given, BT0KUN would
supply the (correct) codes VTIC, PT1 (finite Tl verb, past participle of Tlverb) for "ADDED".
The processing of nouns is similar.

£'or nouns, the first characteris always N; the class occupies the first three character positions. The
number (singular, plural, or " common" -irrelevant or indeterminate, e.g.
"DEER") occupies nosition four, and character number five is always blank.
Thus stem codes will be N0UO 111010, N0VO 11101 0, etc.; suffix codes are of
the form 000S0 00010 1, 000P0 00010 1, 000C0 00010 1.

Note here that thesuffix/stem partition of complete codes is different for nouns (U/1235) andfor verbs (lU/235)•

Thus noun stem codes cannot by mistake be combined xtfith

verb suffix codes or vice versa.

VI-10A large number of words exist which do not require partial codes.
Among these are all those which exhibit no suffixes - prepositions,
irregular forms, pronouns, forms of "be", "have", "do", and so on. Also,
the codes for adjectives and adverbs are not divided. Many suffixes areincluded in the suffix table which, give rise to complete syntax codes bythemselves, no matter what stem code is supplied.

For instance, -MESS

always gives rise to the code "N0US" . Under these circumstances the code
juxtaposition operation can be skipped.
If no codes are determined by the procedure previously described,
because stem and suffix codes do not match, or because no partial codes
were provided by dictionary lookup, an arbitrary code list is assigned asshown:

VTIC, VI1C, N0UC, ADJ, AVI. This set of codes covers most wordclasses except pronouns, prepositions and other common words which areentered in the dictionary.

BT$KUN writes out the list of syntactic codes

generated for each word on the output tape in the following order:

the code,

the word and "homograph" numbers, the text word (2l| characters), and text,
sentence, and word number.

(The word number thus appears twice).

The sixth and seventh words of a nine-word item contain semantic
information.

This information is required by the criterion routine describedlater in this section, and is therefore transferred into COMMON storage
where it is not disturbed.

(COMMON k$l9i.e« octal 76556 and preceding

locations).
When every word in the sentence has been processed as describedan end-of-sentence sentinel is written on the output tape and the nextVI-11
sentence i s processed.

If the sentence-number l i s t i s exhausted, theroutine writes an end-of-text sentinel and an end-of-file on the output
tape, the tape i s rewound, and the f i r s t section (SETUP) of the syntactic
analyzer i s calledo

The complete process i s d e t a i l e d in Flowchart 1.

The

square brackets near the flowchart box indicate the symbolic name of the
program areas that perform the corresponding operations.

h*Organization and Operation of the Criterion Routine (CRITER)
Following the syntactic analysis of the t e x t s , the c r i t e r i o n routine

performs three functions * F i r s t , i t accepts the output of the syntactic
analyzer, and compute from i t a set of binary connection matrices.

Secondly,i t l i s t s a l l semantic and syntactic values appearing i n a sentence, and thewords to which they p e r t a i n .

Finally, i t supervises the matching of t h i sdata against each member of the l i b r a r y of c r i t e r i o n t r e e s .

The overall

organization of t h i s routine is shown in Flowchart 2.
In the output of the syntactic analysis program, one record i s formed
for each t e x t word, containing among other information a s t r i n g of up to 2)|
BCD characters (see Fig. 2 ) .

Each character of such a s t r i n g represents one

s t r u c t u r e or substructure in the sentence.

The type of structure ( e . g . subject,phrase, object, e t c . ) i s indicated by the character:for phrase, e t c .

f! ,f

S

for subject,

,r n

P

The s t r u c t u r e indicated by each character i s contained i n ,depends on, or modifies t h a t indicated by i t s predecessor in the s t r i n g ( i fany).

Thus in Fig. 2, rtone,f in each string denotes a declarative clausestanding alone, the "S" in s t r i n g s one and two indicates a subject of thatclause, and so on.

Compute number ofbinary words ontext tape
Read suffix table
Errorfrom library tape
O.K,
Read text and listof "frequent cluster11
sentences
XI <
X2 <

number of sentences
to be processed
number of binary words
in texti

Write i n i t i a ls e n t i n e l ("ENGTEX")
on output tape
[FIND
A-<
number of f i r s tsentence t o beprocessed[GEfj
Search text for firstword of sentence number A

Mot
VerifyO.K.

<3

Search text s w for f i r s t
word of next sentence
Compute number ofwords in sentence and Bad
verifyO.K.

©
Operations of BT0KUN Editing Routine
Flowchart 1

Convert number of*| words and sentence
number to BCD

R

Write word counton output tape(in BCD)[RESET]
Move f i r s t word t obufferjSUFLOC]^ Get list of suffix
1 codes; H0M0S*
0

a fe-

[RETSTM
Get one stem syntaxL
code

No more[GETSTM]Is it

complete
No [GE SFJ

w moreScan suffix code
list
Find a fit
Form combinedsyntax code;
put i n r,J$M0Sn

Flowchart 1 ( c o n t i n u e d )Yes

Put it-*list »H0I

[STEMOK

Scan s u f f i x codel i s t for complete
codes
Find
Put i tinto

[FULHOMl#• 0

H0M0S:

00
HOMOS < — V T I C , V I l C
N0UC,ADJ,AV1[GOOD]J Compute BCD w o r dnumber[LIMIT]
RepeatO.K.

Take a code from
H0MJ0S and write it on
output tape
No more'[ENDWDJStore semantic values(concept numbers)in SMS, with sentence
and word numbers©
Flowchart 1 ( c o n t i n u e d )No morevi-15

Have we processed thel a s t word i n thesentence?

No

Next word
to buffer

KD

Yes[ENDSENJ

Write ,fend of sentence' 1
sentinelHave we processed
the l a s tsentence?
Yes

No[D0NE1r,[Write end of text"
sentinel; rewind
tapeStore count of items
in SEMSEXIT to
chain

(U,3)
rERR0Rl*J WriteA

on A3: "error in BT0KUN or
sentence tape' 1
TERR0R21"BT0KUN s u f f i x

J Write on A3:
1
table i s in error

4

•l
A

c^~

"KUN0ER": c a l l /s»
LESKFlowchart 1 (continued)

numberof next
sentenceA<E)

vi-16

Form chained"table" of nodes,
strings and connections
Form connection
matrices from "table"

Form "Semval" tablefrom value tape and "table"
Form relations
from tree tapeand "Semval" table

Form summary table->| listing subject headsof matching trees
Index Informationlc
Attach index information
to summary, leave in
C0MM0N
EXIT

Organization of Criterion Routine
Flowchart 2

VI-17

Input

Magnetic

ISA -

tape

IS —

is

IV-

the

1CA -

fastest

1CA _

input

1C - •

which

1C7S

is

1C7V

available

1C7C

today

1C7D

(1)1

1. _

Format of Syntactic Analysis Used as Input
Figure 2

It may be seen from Fig, 2 that the strings may easily beconstructed from the corresponding syntactic tree simply by working up thetree from any given node. For example, the string for "magnetic," whichcorresponds to node three in Fig. 2, may be found by taking the predecessorsof node three, that is, node two, and then again of node two, i.e. node one.
The characters for these nodes are ,?A," rfS," "1" respectively, and correspondto the string "ISA."VI-18The criterion routine must perform the inverse transformation; thatis, it must determine a dependency tree from a set of strings. This task
is complicated by several factors. First, distinct nodes may have the same
strings; e.g., nodes six and seven in Fig. 2 both have the BCD character orsyntactic value ,fAM (adjective) and the string ,?1CA.M

Secondly, the strings

contain no explicit information to distinguish between phrases modifying
the same word.

Thus, in Fig. 3, there are two distinct trees exhibiting thesame set of strings. Only one of them (Fig. 3(a)) is correct.
The criterion routine processes the strings one at a time, startingwith the first word.

Each string is scanned from left to rigjit. The program

maintains a list, called TABLE, of sentence nodes and their dependencies.
TABLE is initially empty. As each string is scanned, the routine traces throughthis TABLE (see Fig. h) * When the string specifies a node not recorded in
TABLE, a new entry is generated.

Thus, when all strings have been scanned,

TABLE contains a tree corresponding to the strings.

Various refinements areadded to the miles for generating new nodes; these refinements handle thevarious ambiguities discussed in the last paragraph.
The criterion routine uses several tables as part of the process.
Two of these, "SEMS" and "SIMM" are used throughout a run; the others arereset for each sentence.
"SEMS" contains the semantic information for all the sentences to beprocessed.

It is stored by the BT0KUN program in C0MM0N U5l (octal 76556).

CRITER makes no alterations in it, but moves it into the program proper forsafekeeping.

This is necessary because GRAPH uses that area of C0MM0N forother purposes (see Sec. VII by Sussenguth).

The semantic information is

VI-Interpretation

Input
It

IS

^(2)S

is

IV-

on

1VPR

the

1VP0A

shelf

1VP0

"^6)0

in

IVPR

aS9)R

a

1VP0A

bottle

1VP0

Oft.
Q(5)R
0^)A

V(7)I

-oM-l)kyi(Q)P^°Cio)01(a)0Correct i n t e r p r e t a t i o nx\(2)S

It

1S

is

iv

on

IVPR

the

1VP0A

shelf

1VP0

in

IVPR

a

1VP0A

bottle1VP0(3)1<x(5)R
Q(7)A-SQ(6)0°(f)R •-°4™> A
-V(9)01.
(b)Incorrect i n t e r p r e t a t i o n

Interpretations of an Analysis
Figure 3

VJ ( iVI-20Word

String &Character

this

ISA

Structure Implied byCharacters to Date0(1)1(2)s l > ^

this
this

paper

u

this

1~

this •

is

A

paper

i3)A^

JO

(1)1

(1)1

this _
paper

(2)S

(in

\
discusses

IV

(1)1

this paper this

discusses

1*

paper
discusses

document

10A

this •

paper
discusses
information
anddocument
Note;^(U) V

oJ6)A
(7) +
(8)A

The vertical arrows indicate the character and node being
scanned at each step.
Scanning of Syntax Strings
Figure k(5)0VI-21stored in consecutive three-word items. The first word contains thesentence and word numbers originally assigned by the itemizer.

The next

two words (72 bits) consist of six semantic values (or concept numbers),
packed as three 12-bit bytes per word.

These are obtained by the thesaurus

lookup.
"SUMM" holds at any time the list of matches found between all
sentences so far processed, and the criterion trees in the library.

SUMM isinitially cleared; every time a tree is found to match a sentence, the table
is updated.

Each entry in SUMM consists of two machine words. The secondof these contains a subject heading or "index" specified by six BCD characters.
The other word contains a count specifying the number of times that thecorresponding heading has been found to match a sentence.
When a match is found between a sentence and a criterion tree, SUMM
is scanned for an entry that matches the heading of the tree. If such an
entry is found, the count in that entry is incremented.

If no entry is found,a new entry is made, with a count of one.
"(0UT)" is a table constructed from SUMM.

It is located in octal

61717 (C0MM0N 7010) and lower locations.

Octal 61717 contains, in the decre-

ment, the number of items in the table0

These items are listed in successively

lower locations in reverse alphabetical order. Each item comprises fivemachine words. The first word consists of a subject heading from SUMM; thefifth contains in the decrement, the appropriate count (also from SUMM).
The sign of this count is positive.

The remaining three words are extracted

from an "index" file on the SMART library tape.

This file contains a three-VI-22

machine-word correspondent for each subject heading; these three words are
simply copied into the appropriate locations without any processing.
"TABLE" is the most important table in the criterion routine.
is stored in C0MM0N 10010 (5U027g).

It

It is the primary active storage

during input of a sentence. When an entire sentence has been read-in,
TABLE contains all of the structural information provided by the analyzer.
During the processing of a sentence, TABLE holds all the nodes (i.e.
substructures) found as of that moment.
Each item in TABLE corresponds to one node of a tree. In memory an
item consists of 16 machine words. Of these, the first contains a chain
link, and a flag to indicate whether an actual word corresponds to thatnode.

The next five contain up to 30 BCD characters from the analysis of

the sentence, indicating the role of the node. The next two words are notused.

The remaining eight words in each item form two lUU-bit binary vectors.

One of these (the first) is called the "indirect" vector, the other the"direct" vector.

The "direct" vector is either 0, indicating that thenode has no antecedents (i.e. corresponds to the main structure (clause) of
the sentence),, or contains a single "1" bit whose position corresponds tothat of the immediate antecedent. The "indirect" vector contains a "1" bitfor each antecedent in the tree all the way up to the main clause.
The chain links referred to above, link together those entries corresponding to strings of equal length.

Thirty words, labeled

TABLE+1 through

TABLE+30, are provided to hold the initial links of these chains. Each linkpoints to the seventh word in a 16-word item.
chain is 00000.

The link at the end of theVI-2 3The last table, called f,SEMVALM, is reset for each sentence. It
lists all the semantic values and syntactic structure types found topertain to any node of the sentence. In memory, it consists of a sequenceof five-word items. The first of these contains one 12-bit value, and achain link by which the entire table is chained so that the values are inincreasing numerical order.

The remaining four words comprise a lljii-bit

binary vector; the "one" bits indicate the nodes to which the given value
pertains.

Only one entry is made for each distinct value:

if two nodes

have the same value this is represented by two "one" bits in a single entry.

5.

Internal Processing of the Criterion Routine
After a few initializations, CRITER processes the input, one

sentence at a time.

The input tape is first scanned for a sentinel

indicating the beginning of an analysis: the sentinel record then provides
the number of the sentence. The sentence is then scanned, and the information
extracted from each word is stored in TABLE and SEMVAL. When the sentence
is completely read-in, CRITER matches it against each of the criterion trees.
The criterion tree tape is then backspaced and another sentence processed.
Finally the results are summarized and left in memory for the next program.
When a sentence word is read from tape, its record contains among
other things a string of BCD characters denoting the syntactic function ofthat word in the sentencee

The criterion routine keeps a count, "K", inindex register two. For each word, this count starts at one, and then isincremented.

The routine takes the first K characters of the character stringVI-2U

representing the BCD syntactic function code and scans through TABLE bymeans of the chain (starting at TABLE+31-K).

The scan stops when a TABLE

entry is found whose string is equal to the first K characters of the
BCD code string of the word.

If the chain is exhausted before such amatch is found, or if the match is not permitted (e.g. where a matchindicates that the code entry corresponds both to the present and to someprevious text word), ENTERK generates a new entry in TABLE. This entry
will be chained into the beginning of the Kth chain, and its string willconsist of the first K characters of the code string for that word.
When an entry in TABLE is either found by the matchinprocessor generated, the number of the entry (represented as a single "one" bit)is placed in a special vector, called DIRCT; the updated DIRCT vector isthen used to alter another nINDRCT,T vector by "0Ring" the contents of
DIRCT into INDRCT.
Figure £ shows a simple example of this process. The sample
sentence is "Computers think."

The BCD code string for "Computers" is"IS", and the code string for "think" is "IV".

Here "S" means "subject"and "V" means "verb". The "1" in both strings is the clause indicator forthe singLe clause to which both words belong.
Both DIRCT and INDRCT are set to zero at the start of the process.
Then with K » 1, TABLE is scanned for entry whose string field is equal to"1".

Since TABLE is anpty, none is found, so a new entry is generated asshown at the top of Fig. £.

(The arrows represent the successive links ofthe chains connecting the entries).

The first entry has a string fieldVI-25
Indirect
DirectTABLE

Word and
StringComputers

S

I

\L
•

J/
m

L

s

F

S

I

D

X

1
IS

1

1

?

)

?

is

PLl
.1
Think
Y

•

•

F

S

I

D

X

1
IS

1

1

L

F

S

I

D

T

X
X

1
IS
IV

1
1

1
1

L

1 \
/

A

/

•

>\
•

1

^
I

N
•

-

T"

1
ds:

IV

1.1
. .1

L = Link which chains together entries of equal depth (=K)
F = Flag. This is set for an entry which matches theentire string for a word
S = String
I = Indirect
D = Direct
Construction of TABLE
Figure 5

VI-26of "1", blank I and D fields, because INDRCT and DIRCT are blank, and ablank link (L) because this entry is the first for K • 1.
INDRCT are now updated.

DIRCT andSince the entry just generated is the firstentry in TABLE, a "one" bit is placed in the first position of DIRCT,
and zeros elsewhere.

Then the new DIRCT vector is 0Red into INDRCT.

The process is repeated for K = 2.
again no entry is found.

The string is now "IS" andA new entry is generated; this time the I and

D fields each contain a "one" bit in position one, derived from INDRCT and
DIRCT respectively.

The flag bit is set because "IS" is the full string

for the word "computers."
The situation is similar when "think" is processed. When K = 1,
however, the code string is "1"; and the first entry in TABLE alreadycontains the string "1".

Thus no new entry is generated, and DIRCT will

have a "one" in the first position. INDRCT will also have a single "one"bit in position one, since it was previously reset to zero before the newword "think" was read-in.

The process described above is repeated again

for K = 2, string = "IV", A new entry (the third) is generated and placedat the beginning of the second chain. DIRCT has a "one" in position three;
INDRCT has "ones" in positions one and three.
Thus after the processing of the entire sentence, TABLE contains
a representation of the corresponding syntactic structure in tree form.
Each entry in TABLE represents a node, and the D(direct) field in a given
entry indicates the node upon which the given node depends. At any time
during the process, DIRCT indicates the most recent node found (or generated),VI-2 7i.e. the node upon which the next node will depend directly.

INDRCT exhibits

all the nodes upon which the next node will depend, either directly or
indirectly, up to and including the topmost node of the tree.
When the entire code string for a word has been processed, TABLE
contains a complete record of the syntactic relations of the given word to
the earlier words in the sentence, and SEMVAL records the syntactic functionsof the word.

The semantic values (from SMS) are now added to SEMVAL. As

before, DIRCT serves to indicate which nodes in the syntax tree are being
processed. When a given word is completely processed, DIRCT and INDRCT are
cleared to zeros for the next word.
Figure 6 shows how the concept numbers associated with the sentence"Computers think" are entered into SEMVAL.

The DIRCT vector is shown as it

is generated during the construction of TABLE.

The steps which update

SEMVAL alternate with those that update TABLE; thus DIRCT always shows thenode presently being processed.
After the first node is entered in TABLE, DIRCT contains a single"one" bit as shown. At this point an entry is made in SEMVAL which indicatesthat the first node has the (syntactic) value "1".

Similarly, after node twois entered, an entry is made into SEMVAL, to indicate that node number two
has the value "S". Then a third entry is made into SEMVAL, showing that thevalue ,f(G0MP)fl pertains to node number two. This is a semantic value obtained
from S M S ; the entry is made only after the complete code string for the text
word has been processed.

VI-28WORD
SEMVALDIRCT a n d VALUELINKCOMPUTERS

ll

T

#

1.1

(WORD)

1.1

DIRCT

VAL
1

1..

l

1..

s

.1.

V

"^s

1

(COMP)J

PL.
(COMP) .1.

THINK

. .1

i

f^

s

.1.
1 (COMP) . 1 .

n\ 1
r
1

X

v

1

(WORD)

1..

ft•(THINK)

..1
i

i

1..

s

.1.

.1.
h -L (COMP)
V
..1

u

\—

(Note:|( THINK) . . 1

The s t a g e s of p r o c e s s i n g shown h e r e a r e not c o n t i g u o u s , but
a l t e r n a t e w i t h those shown i n F i g . $).
C o n s t r u c t i o n of SEMVAL, Using DIRCT as Developed i n
C o n s t r u c t i o n of TABLE (see F i g . 5)
Figure 6\

VI-29The same procedure is followed for "think".

Note that when thefirst value, "1" is to be entered, a r,ln already appears in SEMVAL; in thiscase DIRCT is 0Red into the entry.

This has no effect in the present example,

because there is already a "one" in the first position of the SEMVAL entry.
When a word is read which is coded "period" or "question mark", theabove processing is not performed.

Instead, the INDRCT and DIRCT fields are

extracted from each entry in TABLE and reassembled to form two binary matrices,
one made up of all the INDRCT fields collected together, the other of the
DIRCT fields. Together these matrices are called C0NMAT (C0Nnection MATrices):
each is an incidence matrix indicating internode dependencies.
The complete preceding process takes place exactly once for eachsentence.

The "criterion trees", I.e.

the model phrases, are now read-infrom tape. Each is compared against the sentence as shown in Fig. 8,
Each tree consists of one record on tape, which is divided logicallyinto several fields (see Fig. 7)- The first field is the prefix, whichcontains the number of nodes, the number of "relations" (see below), thenumber of "relation generators", and a BCD heading and an I.D. (identification)
number.

The next two fields are indirect and direct connection matrices

showing the structure of the tree.
The fourth field consists of a series of "relation generators"*Eachof these is composed of a 12-bit value (syntactic or semantic), a node
number, and a relation number.

The latter refers to one of a set of "relations",(denoting restrictions which affect the matching process between the given
tree and the sentence).

Each relation is represented by a pair of binary

(C0MP)
Y)(C,V) (THINK)

(a)

— J

Symbolic representation

-I

_3

1

196

1
1

D i

S

"1

[

If

5
R i I iP (Prefix)

i
i

1

C

P

1 • • •• •1

I (Indirect)t • * «

1 14* i t|_.i..
D (Direct)

1 • • • •1••• •
1(COMPj1(THINK)

1

l

i

3

: kJ

C

i

i

! 3

S

•

! 2

V

i

! 3

i

2

!

3

!

1

;

3

(b) Structure of binary record

A Sample Criterion Tree
Figure 7\ V (Values)VI-31

Current
SEMVAL E n t r y

Current Relation
Generator

Relations Generated
Sentence(C0NMAT)

Value

V• (COMP)

Node Relation
No.

.1(C0MP1• (THINK; . . 1(THINK)

3

1.

1..

3

..1

..1

1

•

TREEBF

1...

S .1.

c

3 3

s

2

1.1.

l

1

V

..1

V

3

k-

1.1.

|..l

.1

.1.
.1.

.1.
1..

..1

.1

I..1

1

Scanning of SEMVAL in Generating Relations
Figure 8..1

VI-32
vectors, one for the tree and one for the sentence, and its function isto ensure that each of the tree nodes indicated by the "tree" vectors
correspond to one of the sentence nodes indicated by the "sentence" vector.
These relations are set up by a simultaneous scan of the set of
relation generators (sorted in numeric order) and of SEMVAL (chained inorder of value).

When an entry in SEMVAL is found to have the same value

as a relation generator, a relation is set up.
A space is reserved in storage near each connection matrix (C0NMAT
for the sentence, and "TREEBF" for the tree), to store the respective
relation vectors. The relation number in the current relation generator
specifies a location in each of these reserved storage spaces. In TREEBF,
the relation vector is cleared to zero, and a single "one" bit inserted
corresponding to the node number found in the relation generator; in
C0NMAT, the SEMVAL entry is 0Red into the relation vector.

This process

is shown in Fig. 8.
The first SEMVAL entry scanned in Fig. 8 has the value (C0MP), as
does the first relation generator.

Therefore a relation is set up. This

will be relation number two, corresponding to the number given by the
relation generator.
dated:

Thus the second vector in each reserved space is up-

the one in TREEBF is replaced by a vector having a "one" bit inposition one (as indicated by the relation generator) and the data from the
SEMVAL entry (which has a "one" in position two) is 0Red into the C0NMAT
half of the relation.

VI-33

When this has been done, the routine examines the next relation
generator.

If the value is the same, the process is repeated; if greater,a new SEMVAL entry is scanned.

Then the comparison is repeated.

If theSEMVAL entry is less than the relation generator value, SEMVAL is scanned;
if greater, a new relation generator is examined.

Thus the routine continues

its scan until it runs out of entries of either kind.
At this point the situation illustrated in Fig. 9 obtains. Two
separate areas are set up in memory, C0NMAT and TREEBF, each containing
the data for one syntactic structure.

The first word in each area contains

the number of nodes in that structure*(In the example of Fig. 9 this isthree in both cases; in general, the criterion tree will have fewer nodes —usually considerably so.) The next word is blank.

The third word contains

a number of "one" bits, right justified, i.e. a string of "zero" bits followed
by a string of "ones".

There are as many "ones" as there are relations.

This number is, of course, the same in C0NMAT and TREEBF — four in the example.
The relations are stored next in memory; these are paired:relation vector in C0NMAT goes with the first one in TREEBF, etc.

the first
They

instruct the graph matching routine GRAPH (see Sec. VII) to permit only certain
correspondences.
Finally come the two connection matrices. Those in C0NMAT originate
in TABLE; those in TREEBF come from the original tape record.

In the example

of Fig. 9, they indicate that nodes two and three of the sentence each depend,
directly (and hence indirectly) upon node one, while node one depends on
nothing; whereas the tree matrices show that the correspondent of node one must
depend directly on that of node two, while the correspondent of node three needVI-3UC0NMATTREEBF

3

U

n

1111

1111
.1.

.1.

.1.

1.

..1

vRelations/

..1

! i..

> INDRCT <

i..

I.,

I

DIRCT

l..

Cj^NMAT and TREEBF J u s t Before GRAPH
i s Called
Figure 9

VI|START|

Initialize:
SUM
SENTN0
TAP0S
QjEADSN)

Initialize
SEM;
N<
1
JNEtfREC]No A n a l y s i sFind f i r s t a n a l y s i sof a sentence(EpF)

I fFlND
Find f i r s t
word
O.K. [iDECil

E0F

Convert BCD
s e n t e n c e number
to binary
TTfoGAINI^ End of sentence?

Yes

J/ No [PRCCESI
1
String 4O's
DIRCT 400
INDRCT «£r(SEM)
Search for this word
in SEMS
LlOOPSM)]
Initialize reference to
SEMVAL

Criterion Routine
Flowchart 3

*©

< $

36
[ENDWD -k\
Is character (K+l)-0- 60j?
JRETRNJ
String <-a, /characters

I

other

^ / s t r i n g : + or ,JL

M TABLE +31-kh©

K+l : 30
[BEGINK

Chain(TABLE +31-16)|<.
i CTABLOCJ

W/TABLE= 0(6,M): R

TABLE (1,M)
lnset|i_M£LAG)

Flowchart 3 (continued)

SetVI-37

rr[SETUP]
DIRCT <r- - A^
INDRCTvA/ INDRCT «VS •<:—60n (fe c h a r a c t e r / , , - .

V

JENDWD]Set f l a g of TABLE(1,chain)[BACK]*|

S.t— a /SEM: 0
SEM <-— a 2 /SEM

S =0

S/0

Read next word
i n sentence
Find

Flowchart 3 ( c o n t i n u e d )

E0F

*©

VI-38[TREES]Set up C0NMAT
from TABLE

1

fREADTR]

Read a criterion tree(sample phrase) from
tape
O.K.
IchainJ

I + 1:T

ITRREL:

TREL(R(I))K-«%(I)L-V!

E0F

Backspace»)tree tape
one file

H®

V,GEN,TREMAT

1
SEMTAB
1[GETVALlSEMVAL ( c h a i n , 2 )generator

(I)

JLO.

[NEWENT]
3EMVAL
Chain <(chain,1) : 0
0["EQUAL!
REL(R(I)) 4 — REL(R(I))
v SEMVAL (CHAIN,3);[T0GRAFJ Set up c a l l i n gsequence

No
Match
Match [MATCH]
Scan SUMM t a b l e f o r e n t r y
Make new e n t r y
F a i l . from head of t r e e= t o head of c u r r e n t
trees e t count = 1
Find [MATH
Add 1 to count of( S i z e of SUMM)*—entry( S i z e of SUMM) + 1

I

Flowchart 3 ( c o n t i n u e d )VI-39[GOODBY]*| Space over tree file
to index heading file

Tree f i l e unused[PICK]O.K.
J Get alphabetically earliest heading
Repeatfrom SUMM; then erase

No
More

O.K.
Make up e n t r y f o r (OUT), u s i n g
h e a d i n g and count from SUMM
[FINISH]
Compute number of entries in(OUT) and verify
K-

Bad

O.K.

L_l^_

[READHD]Has enough more index d a t abeen r e a d ?

YesNo[LIMTWgl
Is read in still going on?

E0F

No
Initiate read[_BAKX[
Not
Find

Compare input data against^
Overshoot

(0UT)
Find

[(MOV])

Move index data to (0UT)[SORRY]Set item count of (0UT)= to zero

JSKIPL
Skip r e s t of index f i l e L(0.K)
Rewind sentence tape; EXIT [£Flowchart 3 (continued)

VI-1*0

1ENTERKI

Get empty l o c a t i o n
f o r new node
Move c h a i n l i n k fromt a b l e + 3 l ( K ) to new
location
Table+31(K) ^ — l o c a t i o nof new e n t r y
S t o r e l o c a t i o n of newentry
New e n t r y <— K c h a r a c t e r s
from s t r i n g<

New e n t r y
INDRC.T.DIRCT

I s t h e r e more room i n
TABLE?
Yes
RETURN

Subroutine ENTERKFlowchart h

No;
Full

-©

VI-M

I ENTERS ISCHAIN <?

0

CSEMST0J
Move down one

chain l i n k :SCHAIN <SEMTAB(SCHAIN)SEMTAB(SCHAIN)

VALBack up one-* chain l i n k

O.K.

LINK
friLEM)

No KoreSEMTAB(SCHAIN)<DATASEMTAB(SCHAIN)
DATAv DIRCT

flNSERfl-±
I s t h e r e any
No < R )more roomi n SEMTAB?
Kes
RETURN[SEHTET4T

Get new s l o t :SEMTAB (NEW) LINK<—SCHAIN

3EMTAB(SCHAIN)LI^New Address
SEMTAB (NEW ) M T A |«DIRCTSubroutine ENTERS
Flowchart 5>

VI-1|2

only have an indirect dependence on that of node two. The correspondence
1>2,2 — > 1 , 3 — > 3 satisfies these dependency requirements but not therelations, because tree node two must correspond (by relation number one)
to a sentence node marked S, i.e. to sentence node two.

But also by relation

two, tree node two must correspond with sentence node one (the only one
with value (COMP)); thus no correspondence is possible here.
These two sets of data serve as input to GRAPH (Sec, VII). They
are set up as described, and GRAPH is given the addresses of the corresponding; areas in memory.

Then GRAPH evaluates all the relations, con-nections, etc. and either decides that no one-to-one correspondence ispossible (as in the example given), or finds such a correspondence.
answer is returned in the accumulator:
possible.

Thezero if no match, one if a match isIf a match is possible, GRAPH leaves in memory a list of binary

words, one for each node in the tree. Each of these words contains thenumber of the sentence node corresponding to the respective tree node.
Flew charts 3* k and 5 describe the various steps used by CRITER in
greater detail.

REFERENCES

Mathematical Linguistics and Automatic Translation, Report No. NSF-8
The Computation Laboratory of Harvard University (January 1963).
Mathematical Linguistics and Automatic Translation, Report No. NSF-9
Vol. I and II, The Computation Laboratory of Harvard University(June 1963)-