Google
 

Trailing-Edge - PDP-10 Archives - decuslib20-05 - decus/20-0146/keywrd.doc
There are 2 other files named keywrd.doc in the archive. Click here to see a list.


	  KK   KK   EEEEEEEE  YY    YY  WW      WW  RRRRRR    DDDDD
	  KK  KK    EE         YY  YY   WW      WW  RR    RR  DD   DD
	  KK KK     EE          YYYY    WW  WW  WW  RR    RR  DD    DD
	  KKKKK     EEEEE        YY     WW WWWW WW  RRRRRR    DD    DD
	  KKK KK    EE           YY     WWWW  WWWW  RR  RR    DD    DD
	  KK   KK   EE           YY     WWW    WWW  RR   RR   DD   DD
	  KK    KK  EEEEEEEE     YY     WW      WW  RR    RR  DDDDD

	  15 May 1980

	      KEYWRD, Word and Phrase Recognition Logic Generator
	      ------  ---- --- ------ ----------- ----- ---------

	  The KEYWRD program produces a sequence of  tests  which  can
	  identify  the leading word or the leading phrase formed of a
	  fixed sequence of words in  a  line  of  text  without  ever
	  having   to   test   a  character  which  has  already  been
	  identified.  Such a leading word or phrase,  which  will  be
	  referred  to as a command in this document, does not need to
	  include any characters to the right  of  the  first  of  the
	  characters which uniquely identify the command.  The word or
	  each of  the  words  in  a  phrase  can  be  abbreviated  by
	  truncation, leaving at least the left character in each word
	  of a phrase  if  additional  words  or  their  abbreviations
	  appear  to  the right.  Spaces are allowed between the words
	  in a phrase, but are not required.   A  single  sequence  of
	  tests  is used to recognize the initial portions of commands
	  which start with a common series  of  characters,  then  the
	  unique  portion  of each command is identified by a separate
	  sequence of tests.  After the unique portion of each command
	  has  been identified by the separate sequence of tests, then
	  a single sequence of tests is similarly  used  to  recognize
	  the  final  portions  of  commands  which  end with a common
	  series of characters.

	  The KEYWRD program reads a single input file and produces an
	  output  listing  file  and  an  output FORTRAN language file
	  containing DATA statements which represent the  sequence  of
	  tests.   The  sequence  of tests could, of course, easily be
	  ouput in a form other than FORTRAN source code.  These  DATA
	  statements  must be merged into the FORTRAN program by which
	  these tests are to be used.  The KEYWRD program  is  written
	  in  FORTRAN, and is machine independent except for the short
	  subroutine which asks the user for the file names  and  then
	  opens  these files.  In the application for which the KEYWRD
	  program was written, a glossary of 55 commands  totaling  96
	  words  and  429 letters was converted into a sequence of 185
	  tests in  27  seconds  on  a  DECsystem1091  computer.   The
	  description  of  each test in the resulting decision tree is
	  packed into 2 array locations and consists of 5 items:   the
	  serial location in the alphabet of the letter to be matched,
	  an indication  of  whether  spaces  can  appear  before  the
	  letter, the location in the arrays of the description of the
	  next test to be applied if  the  current  match  fails,  the
	  value to be associated with the command if the current match
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 2


	  succeeds, and the location in the arrays of the  description
	  of  the  next  test  to  be  applied  if  the  current match
	  succeeds.  Six arrays of 1630 locations each were needed for
	  the  intermediate  storage of the decision tree representing
	  the 55 commands before the identical branches were merged.

	  Each line in the input file which does not start with one of
	  the  reserved  characters  *, /, ( or ), which are described
	  later, specifies a single word or  phrase  preceded  by  the
	  nonzero  value  by  which  the  word  or  phrase  is  to  be
	  identified.  The number should not duplicate the  number  to
	  be  associated  with any other command unless these commands
	  are  synonyms  or  unless  some  of   these   commands   are
	  abbreviations  which  would  otherwise  be  ambiguous.   The
	  number can be preceded by one or more  spaces,  but  leading
	  spaces  are  not  required.   The  number cannot contain any
	  characters other than the digits 0 through 9 and  a  leading
	  minus  sign  if the value is negative or an optional leading
	  plus sign if the value is positive.  Spaces and/or a  single
	  comma   can  appear  between  the  leading  number  and  the
	  following word or phrase, but are not required.   The  words
	  within  a  phrase  must  be  separated  by at least 1 space.
	  Extra  spaces  are  ignored.   Words  and  phrases  can   be
	  constructed  from  any  characters, but upper and lower case
	  alphabetic letters are considered  to  be  equivalent.   The
	  sequence   of  tests  produced  by  the  KEYWRD  program  is
	  independent of the order in which the commands  are  defined
	  in the input file, but with the exception that the numerical
	  values assigned to nonalphabetic characters are 26 plus  the
	  order   in  which  these  unexpected  characters  are  first
	  encountered.   The  input  file  is  terminated  by  a  line
	  containing  a  number which is not followed on the same line
	  by any word or phrase.  The following is an input file which
	  defines 4 very similar phrases.

	  10 NEXT RUNE
	  20 NEAT RULE
	  30 NEXT RULE
	  40 NEAT RUNE
	  0

	  The listing file produced by the KEYWRD  program  summarizes
	  each of the words and phrases and phrase abbreviations which
	  can be recognized.  The  following  listing  file  would  be
	  produced if the above input file is processed.

	        0 NE RULE
	          NE RUNE
	          N RULE
	          N RUNE
	       10 NEXT RU(N)E
	          NEX RU(N)E
	       20 NEAT RU(L)E
	          NEA RU(L)E
	       30 NEXT RU(L)E
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 3


	          NEX RU(L)E
	       40 NEAT RU(N)E
	          NEA RU(N)E

	  The numbers at the left in the listing file are  the  values
	  which  are to be associated with the words and phrases which
	  are shown to the right.  The unique portion of each word  or
	  phrase  is  enclosed  in  parentheses.  An abbreviation of a
	  command is unambiguous if  it  includes  the  first  of  the
	  letters  which are enclosed in parentheses.  Since the final
	  letter E in each of the above phrases is not  necessary  for
	  the  recognition  of  the phrases, the test sequences can be
	  merged at the end as well as at the start, so that the  same
	  test  for  the  final letter E can be included in all of the
	  test  sequences.   The  tests  for  the  next  to  the  last
	  character,  the  letter N, cannot be merged in the 2 phrases
	  which contain the word RUNE, and the tests for the letter  L
	  cannot  be  merged  in  the 2 phrases which contain the word
	  RULE, since no tests for unique characters would then remain
	  in the sequences of tests which identify these phrases.  The
	  abbreviations of all but the rightmost words in each  phrase
	  are  included  in the listing file since the manner in which
	  the previous words in a phrase are  abbreviated  can  change
	  which of the following characters are unique.  Abbreviations
	  such as NE RULE, NE RUNE, N RULE and N RUNE,  in  the  above
	  example,  contain no unique characters and so are ambiguous.
	  Ambiguous abbreviations are shown in the listing  file  with
	  the associated value being zero.

	  The FORTRAN statement file produced by  the  KEYWRD  program
	  contains  a  description of the input file, a description of
	  the tests, the DATA statements defining 2 arrays, MCHPNT and
	  NOTPNT,  which  specify  the  tests,  and  a  DATA statement
	  specifying the sizes of these  arrays,  KNTPNT.   The  names
	  which  are assigned to all of the arrays and variables which
	  are represented  in  the  DATA  statements  in  the  FORTRAN
	  statement  file  can be specified by a line starting with an
	  initial slash as described  later.   The  following  FORTRAN
	  statement  file would be produced if the above input file is
	  processed.  In the comment lines, a minus sign to  the  left
	  of  a  letter indicates that the letter appears at the start
	  of a word.

	  C     10 NEXT RUNE
	  C     20 NEAT RULE
	  C     30 NEXT RULE
	  C     40 NEAT RUNE
	  C
	  C     FINAL STORAGE USED=  19, MOST USED=   62, LIMIT= 3000
	  C
	  C     CHECKSUMS  990,  32,2894,2575, 866
	  C
	  C     COUNT     1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
	  C     COMMAND   0  0  0  0  0  0 20 40  0  0  0  0 30 10  0
	  C     LETTER   -N  E  A  T -R  U  L  N  X  T -R  U  L  N -R
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 4


	  C     SUCCESS   2  3  4  5  6  7 19 19 10 11 12 13 19 19 16
	  C     FAILURE   0 15  9  5  0  0  8  0 15 11  0  0 14  0  0
	  C
	  C     COUNT    16 17 18 19
	  C     COMMAND   0  0  0  0
	  C     LETTER    U  L  N  E
	  C     SUCCESS  17 19 19  0
	  C     FAILURE   0 18  0  0
	  C
	  C     DIMENSION MCHPNT(19)
	        DIMENSION MCHPN1(19)
	        EQUIVALENCE (MCHPN1(1),MCHPNT(1))
	  C     DIMENSION NOTPNT(19)
	        DIMENSION NOTPN1(19)
	        EQUIVALENCE (NOTPN1(1),NOTPNT(1))
	        DATA KNTPNT,KNTXTR/   19,    0/
	        DATA MCHPN1/2,3,4,5,6,7,419,819,10,11,12,13,619,219,
	       116,17,19,19,0/
	        DATA NOTPN1/-280,115,29,405,-360,420,248,280,495,411,
	       1-360,420,254,280,-360,420,258,280,100/

	  If the words and phrases  are  constructed  from  characters
	  other  than  spaces  and the alphabetic letters A through Z,
	  then  an  additional  DATA  statement  is  generated   which
	  specifies  a  third array, LTRXTR, containing the unexpected
	  characters.  KNTXTR, which is specified by one of  the  DATA
	  statements  which  are  always generated, is the size of the
	  LTRXTR array.  If the words and phrases are constructed only
	  from  spaces  and  the  alphabetic letters A through Z, then
	  KNTXTR has the value zero and a DATA statement defining  the
	  LTRXTR array is not generated.

	  The first location in the NOTPNT array describes  the  first
	  test  which  is to be performed.  The absolute value of each
	  entry in the NOTPNT array is the sum of the location  within
	  the  alphabet  of the letter to be matched times (KNTPNT+1),
	  plus the subscript of the location in the NOTPNT array which
	  describes  the  next  match  which is to be attempted if the
	  current match is a  failure.   The  subscript  of  an  array
	  location  is  its serial position within the array, counting
	  the first value in the array as being at  subscript  1,  the
	  second  value  as  being  at subscript 2, and so on.  If the
	  entry in the NOTPNT array is negative,  then  the  character
	  starts  a  word  and  any  spaces  in  the input line can be
	  skipped.  If the location within  the  alphabet  is  greater
	  than  26,  then  this  minus  26  is the location within the
	  LTRXTR array of the character to be matched.  If  the  match
	  succeeds  and the value to be associated with the command is
	  positive or if the value is zero indicating that  the  match
	  does  not  uniquely  identify a particular command, then the
	  parallel location in the MCHPNT array contains  the  sum  of
	  the   value  of  the  command  times  (KNTPNT+1),  plus  the
	  subscript  of  the  location  in  the  NOTPNT  array   which
	  describes  the  next  test.   If  the match succeeds and the
	  value to be associated with the command  is  negative,  then
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 5


	  the  parallel  location in the MCHPNT array instead contains
	  the  value  of  the  command  times  (KNTPNT+1),  minus  the
	  subscript   of  the  location  in  the  NOTPNT  array  which
	  describes the next test.  If the subscript of  the  location
	  in  the  NOTPNT  array  which  describes  the  next  test is
	  indicated to be zero, either by  the  MCHPNT  array  if  the
	  current  match  is  a  success or by the NOTPNT array if the
	  current match is a failure, then no additional test  remains
	  to  be  performed, and the command is identified by the last
	  nonzero value encountered in the MCHPNT array  for  a  match
	  which succeeded.

	  The sequence of tests which the KEYWRD program  produces  to
	  identify  the commands in the above input file is diagrammed
	  below.  In this diagram,  the  horizontal  lines  formed  of
	  minus  signs  indicate the next tests to be performed if the
	  matches succeed, and the diagonal lines  formed  of  slashes
	  indicate the next tests to be performed if the matches fail.
	  The numbers above the  letters  are  the  locations  in  the
	  NOTPNT  and  MCHPNT  arrays  which  describe the tests.  The
	  numbers below the letters are the values of  the  associated
	  commands.  The word "space" indicates a location at which an
	  optional space character can appear.

	                                                        18  19
	                                                         N---E
	                                                        /0  /0
	                                             15  16  17/   /
	                      /---/-----------space---R---U---L---/
	                     /   /                    0   0   0  /
	                    /   /                               /
	                   /   /                         14    /
	                  /   /                           N---/
	                 /   /                           /10 /
	                /   /                 11  12  13/   /
	               /   /   /---/---space---R---U---L---/
	              /  9/ 10/   /            0   0   30 /
	             /   X---T---/                       /
	            /   /0   0                     8    /
	           /   /                           N---/
	          /   /                           /40 /
	         /   /                  5   6   7/   /
	        /   /   /---/---space---R---U---L---/
	  1   2/  3/  4/   /            0   0   20
	  N---E---A---T---/
	  0   0   0   0

	  The following input file defines 4 commands which start with
	  the same first 3 letters.

	  10 FOGHORN
	  20 FOG HORN
	  30 FOG
	  40 FOGGY
	  0
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 6


	  The sequence of tests which the KEYWRD program  produces  to
	  identify  the commands in the above input file is diagrammed
	  below.  This sequence of tests is independent of  the  order
	  in  which  the  commands  appear  in  the  input file.  If a
	  continuation of the current word starts with the same letter
	  as  the  next  word  of  a  phrase, then the continuation is
	  always sought first and the space  which  must  precede  the
	  next  word  is  sought only if the test for the continuation
	  fails.  Thus, FOGHORN without a space before  the  letter  H
	  will  always be identified as command 10 and FOG HORN with a
	  space before the letter  H  will  always  be  identified  as
	  command  20.   FHORN and FOHORN are not abbreviations of the
	  single word FOGHORN, and so are  identified  as  command  20
	  whether or not a space appears before the letter H.

	                                  7   8   9  10
	              /---/---/---space---H---O---R---N
	             /   /   /            20 /0   0   0
	            /   /   /               /
	           /   /  6/               /
	          /   /   H---------------/
	         /   /   /10
	        /   /   /
	  1   2/  3/  4/  5
	  F---O---G---G---Y
	  0   0  30  40  40

	  Undesired  abbreviations  can  be  made  unidentifiable   by
	  including  them  in  the  input  file  with  zeroes  as  the
	  associated values.  If the glossary  defined  by  the  input
	  file  shown above is to include the abbreviations F HORN and
	  FO  HORN  when  a  space  or  spaces  appear   between   the
	  abbreviations  of  the  words  of  the phrase, but FHORN and
	  FOHORN are not to be  allowed  as  abbreviations,  then  the
	  input file might be changed to the following.

	  10 FOGHORN
	  20 FOG HORN
	  30 FOG
	  40 FOGGY
	  0 FHORN
	  0 FOHORN
	  0

	  The following listing file would be produced  if  the  above
	  input file is processed.

	        0 FHORN
	          FOHORN
	       10 FOG(H)ORN
	       20 FOG (H)ORN
	          FO (H)ORN
	          F (H)ORN
	       30 FO(G)
	       40 FOG(GY)
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 7


	  The sequence of tests which the KEYWRD program  produces  to
	  identify  the commands in the above input file is diagrammed
	  below.  The only differences between this sequence of  tests
	  and  that  shown  for  the  previous  example  is  that this
	  sequence of tests does not assign a  nonzero  value  to  the
	  command  when  the  letter  H  is found immediately after an
	  initial letter F or after the initial letters FO.

	                                          9  10  11  12
	                      /---/---/---space---H---O---R---N
	                     /   /   /            20 /0   0   0
	                    /   /   /               /
	                   /  8/                   /
	                  /   H-------------------/
	                 /   /0                  /
	                /   /   /               /
	               /   /  7/               /
	              /   /   H---------------/
	             /   /   /10             /
	            /   /   /               /
	          3/  4/  5/  6            /
	          O---G---G---Y           /
	         /0   30  40  40         /
	        /                       /
	  1   2/                       /
	  F---H-----------------------/
	  0   0

	  If, instead, the glossary is to  include  the  abbreviations
	  FHORN  and  FOHORN,  but  F  HORN  and FO HORN are not be be
	  allowed as abbreviations  when  a  space  or  spaces  appear
	  between  the  words, then the input file might be changed to
	  the following.

	  10 FOGHORN
	  20 FOG HORN
	  30 FOG
	  40 FOGGY
	  20 FHORN
	  20 FOHORN
	  0 FO HORN
	  0

	  No harm would result from  explicitly  assigning  the  value
	  zero  to the phrase F HORN in the above input file, but this
	  is not necessary since this phrase is an abbreviation of the
	  phrase  FO  HORN.   The  following  listing  file  would  be
	  produced if the above input file is processed.

	        0 FO HORN
	          F HORN
	       10 FOG(H)ORN
	       20 F(H)ORN
	          FOG (H)ORN
	          FO(H)ORN
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 8


	       30 FO(G)
	       40 FOG(GY)

	  The sequence of tests which the KEYWRD program  produces  to
	  identify  the commands in the above input file is diagrammed
	  below.

	                                             10  11  12  13
	                          /---/-------space---H---O---R---N
	                         /   /                0  /0   0   0
	                        /   /                   /
	                       /  9/                   /
	                      /   H-------------------/
	                     /   /20                 /
	                    /   /                   /
	                   /   /              8    /
	                  /   /   /---space---H---/
	                 /   /   /            20 /
	                /   /   /               /
	               /   /  7/               /
	              /   /   H---------------/
	             /   /   /10             /
	            /   /   /               /
	          3/  4/  5/  6            /
	          O---G---G---Y           /
	         /0   30  40  40         /
	        /                       /
	  1   2/                       /
	  F---H-----------------------/
	  0   20

	  When 2 or more commands start  with  the  same  sequence  of
	  characters  and  the  input  file  defines a shorter command
	  which is itself an abbreviation of the  nonunique  sequence,
	  then  the shorter command can be followed by the rest of the
	  nonunique characters and still be identified as the  shorter
	  command.   For example, if the above input files defined FOG
	  HIDDEN as having the value 50, then then both FOG and FOG  H
	  would  be identified as command 30.  This could be prevented
	  by assigning FOG H and all other undesired abbreviations  of
	  this  sort  some  single nonzero value which is not used for
	  any  valid  command  and  which  will  indicate  that  these
	  undesired commands are illegal if they are ever encountered.


	    Handling of Input Lines Starting with Special Characters
	    -------- -- ----- ----- -------- ---- ------- ----------

	  Lines in the  input  file  which  start  with  a  slash,  an
	  asterisk,  a  left  parenthesis  or  a right parenthesis are
	  treated  specially.   These  initial  characters  cause  the
	  following actions to be performed.
	  KEYWRD, Word and Phrase Recognition Logic Generator   Page 9


	    /  An initial slash indicates that the line specifies  the
	       names  of  the  arrays  and  variables  which are to be
	       represented in the DATA  statements  which  are  to  be
	       written into the output FORTRAN statement file.

	    *  An initial asterisk indicates that the line specifies 5
	       numbers   which  characterize  the  sequence  of  tests
	       produced by the KEYWRD  program.   Such  a  line  would
	       appear  in  the  input  file  only  when  the result is
	       already known and the operation of the  KEYWRD  program
	       is being verified.

	    (  An initial left parenthesis indicates that the rest  of
	       the  current  line  is  to  be  copied  into the output
	       FORTRAN statement file unchanged.

	    )  An initial right parenthesis indicates  that  the  DATA
	       statements which represent the sequence of tests are to
	       be written into the output FORTRAN statement file.

	  If a line starts with an slash, then the next  5  groups  of
	  printing characters on the line are used as the names of the
	  3 arrays and 2 variables which are represented in  the  DATA
	  statements  when  the  next line is encountered which starts
	  with a left parenthesis or which  contains  only  a  number.
	  These  groups  of  printing  characters  can be separated by
	  spaces and/or by single commas.  The names of the  3  arrays
	  must   each   differ  from  the  others  in  their  first  3
	  characters.

	    1. The first group of up to 6 characters is  used  as  the
	       name of the array which specifies the next operation if
	       a match fails.  This name is NOTPNT if a line  starting
	       with an slash does not appear in the input file.

	    2. The second group of up to 6 characters is used  as  the
	       name of the array which specifies the next operation if
	       a match succeeds.   This  name  is  MCHPNT  if  a  line
	       starting  with  an  slash  does not appear in the input
	       file.

	    3. The third group of up to 6 characters is  used  as  the
	       name  of the nondimensioned variable which contains the
	       number of tests specified  by  the  NOTPNT  and  MCHPNT
	       arrays.  This name is KNTPNT if a line starting with an
	       slash does not appear in the input file.

	    4. The fourth group of up to 6 characters is used  as  the
	       name of the array which specifies all characters, other
	       than spaces and the letters A through Z,  appearing  in
	       the  commands.   This name is LTRXTR if a line starting
	       with an slash does not appear in the input file.

	    5. The fifth group of up to 6 characters is  used  as  the
	       name  of the nondimensioned variable which contains the
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 10


	       number of characters in the LTRXTR array.  This name is
	       KNTXTR if a line starting with an slash does not appear
	       in the input file.

	  If a line starts with an asterisk, then the rest of the line
	  predicts   the  values  of  5  checksums  which  are  to  be
	  calculated from the glossary which is being defined.   These
	  checksums  can  be  separated  by  spaces  and/or  by single
	  commas.  The user of the KEYWRD program will be informed  if
	  the predicted values and the calculated values do not agree.
	  The predicted checksums are used in standardized versions of
	  the  input  file  which  are  processed  to determine if the
	  KEYWRD program still produces the  same  results  after  the
	  KEYWRD program itself has been changed.  A sixth group of up
	  to 6 characters on the line beginning with an  asterisk  can
	  define a label which is to be displayed to the user.

	  The characters appearing to the right  of  an  initial  left
	  parenthesis  are  copied directly into the FORTRAN statement
	  file.  The  appearance  of  a  line  starting  with  a  left
	  parenthesis  does  not  interrupt  the  specification of the
	  glossary of keywords, and, in particular, does not cause the
	  DATA statements to be generated.  Lines with an initial left
	  parenthesis can be used to introduce FORTRAN statements  and
	  FORTRAN comment lines into the FORTRAN statement file.

	  Lines which begin with a right parenthesis  cause  the  DATA
	  statements  representing the sequence of tests to be written
	  into the FORTRAN statement file, but do  not  indicate  that
	  the  end of the input file has been reached.  All characters
	  which follow the initial right parenthesis on the same  line
	  are  ignored.   If  the  input  file is used for testing the
	  KEYWRD program, then additional glossaries might be  defined
	  on  the  lines which follow that which begins with the right
	  parenthesis, but, usually, only lines containing information
	  to  be  copied  directly to the FORTRAN statement file would
	  appear before the final line which contains only  a  number.
	  The  final line will cause the DATA statements to be written
	  out if a line with an  initial  right  parenthesis  has  not
	  already done so.

	  For example, the following input file

	  (      BLOCK DATA
	  (      COMMON/NUMKEY/NOTPNT(300),MCHPNT(300),KNTPNT,KNTXTR
	  (      COMMON/LTRKEY/LTRXTR(20)
	  10 FOGHORN
	  20 FOG HORN
	  (C     COMMENT LINE TO BE COPIED DIRECTLY TO OUTPUT
	  30 FOG
	  40 FOGGY
	  )GENERATE THE DATA STATEMENTS
	  (      END
	  0
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 11


	  would, when processed by the  KEYWRD  program,  produce  the
	  following FORTRAN statement file.

	        BLOCK DATA
	        COMMON/NUMKEY/NOTPNT(300),MCHPNT(300),KNTPNT,KNTXTR
	        COMMON/LTRKEY/LTRXTR(20)
	  C     10 FOGHORN
	  C     20 FOG HORN
	  C     COMMENT LINE TO BE COPIED DIRECTLY TO OUTPUT
	  C     30 FOG
	  C     40 FOGGY
	  C
	  C     FINAL STORAGE USED=  10, MOST USED=   24, LIMIT= 3000
	  C
	  C     CHECKSUMS  650,   8, 736, 306, 101
	  C
	  C     COUNT     1  2  3  4  5  6  7  8  9 10
	  C     COMMAND   0  0 30 40 40 10 20  0  0  0
	  C     LETTER   -F  O  G  G  Y  H -H  O  R  N
	  C     SUCCESS   2  3  4  5  0  8  8  9 10  0
	  C     FAILURE   0  7  7  6  0  7  0  0  0  0
	  C
	  C     DIMENSION MCHPNT(10)
	        DIMENSION MCHPN1(10)
	        EQUIVALENCE (MCHPN1(1),MCHPNT(1))
	  C     DIMENSION NOTPNT(10)
	        DIMENSION NOTPN1(10)
	        EQUIVALENCE (NOTPN1(1),NOTPNT(1))
	        DATA KNTPNT,KNTXTR/   10,    0/
	        DATA MCHPN1/2,3,334,445,440,118,228,9,10,0/
	        DATA NOTPN1/-66,172,84,83,275,95,-88,165,198,154/
	        END


	   A Sample Program Using the Output from the KEYWRD Program
	   - ------ ------- ----- --- ------ ---- --- ------ -------

	  The following FORTRAN program  demonstrates  the  manner  in
	  which  the  variables and the arrays generated by the KEYWRD
	  program are used.

	        COMMON/NUMKEY/NOTPNT(300),MCHPNT(300),KNTPNT,KNTXTR
	        COMMON/LTRKEY/LTRXTR(20)
	        DIMENSION LTRBFR(30),LTRABC(26),LWRABC(26)
	  C     NUMBER OF UNIT FROM WHICH TEXT IS READ
	        DATA ITTY/5/
	  C     DIMENSION OF LTRBFR ARRAY, NUMBER OF LETTERS TO READ
	        DATA LMTBFR/30/
	  C     UPPER CASE LETTERS A THROUGH Z
	        DATA LTRABC/1HA,1HB,1HC,1HD,1HE,1HF,1HG,1HH,1HI,1HJ,
	       11HK,1HL,1HM,1HN,1HO,1HP,1HQ,1HR,1HS,1HT,1HU,1HV,1HW,
	       21HX,1HY,1HZ/
	  C     LOWER CASE LETTERS A THROUGH Z
	        DATA LWRABC/1Ha,1Hb,1Hc,1Hd,1He,1Hf,1Hg,1Hh,1Hi,1Hj,
	       11Hk,1Hl,1Hm,1Hn,1Ho,1Hp,1Hq,1Hr,1Hs,1Ht,1Hu,1Hv,1Hw,
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 12


	       21Hx,1Hy,1Hz/
	  C     THE SPACE CHARACTER FOR FINDING SPACES IN TEXT
	  C     ASTERISK FOR MARKING UNKNOWN LETTERS IN MESSAGE
	        DATA LTRSPC,LTRSTR/1H ,1H*/
	  C
	  C     CALCULATE FACTOR FOR EXTRACTING BYTES FROM ARRAYS
	        IOFFST=KNTPNT+1
	  C
	  C     GET NEXT LINE OF TEXT TO BE INTERPRETED
	   1001 WRITE(ITTY,1002)
	   1002 FORMAT(2H *,$)
	        READ(ITTY,1003)LTRBFR
	   1003 FORMAT(30A1)
	        KMDNOW=0
	        LOCBFR=0
	        LOCPNT=1
	        MINPRT=1
	        MAXPRT=0
	  C
	  C     GET NEXT CHARACTER TO BE TESTED
	   1004 LOCBFR=LOCBFR+1
	        IF(LOCBFR.GT.LMTBFR)GO TO 1013
	  C
	  C     ATTEMPT TO IDENTIFY THE CHARACTER
	   1005 IF(LOCPNT.LE.0)GO TO 1013
	        IVALUE=NOTPNT(LOCPNT)
	        LOCABC=IVALUE
	        IF(IVALUE.LT.0)LOCABC=-LOCABC
	        LOCABC=LOCABC/IOFFST
	   1006 IF(LOCABC.LE.26)GO TO 1007
	        IF(LTRBFR(LOCBFR).EQ.LTRXTR(LOCABC-26))GO TO 1011
	        GO TO 1008
	   1007 IF(LTRBFR(LOCBFR).EQ.LTRABC(LOCABC))GO TO 1011
	        IF(LTRBFR(LOCBFR).EQ.LWRABC(LOCABC))GO TO 1011
	  C
	  C     LETTERS DID NOT MATCH
	   1008 IF(IVALUE.GE.0)GO TO 1010
	        IVALUE=-IVALUE
	  C
	  C     CHECK FOR SPACES BEFORE NEXT WORD
	   1009 IF(LTRBFR(LOCBFR).NE.LTRSPC)GO TO 1006
	        LOCBFR=LOCBFR+1
	        IF(LOCBFR.LE.LMTBFR)GO TO 1009
	        GO TO 1013
	  C
	  C     GET NEXT LETTER TO BE TESTED IF FAILURE
	   1010 LOCPNT=IVALUE-(IOFFST*LOCABC)
	        GO TO 1005
	  C
	  C     LETTERS MATCHED
	   1011 IF(MINPRT.GT.MAXPRT)MINPRT=LOCBFR
	        MAXPRT=LOCBFR
	        IVALUE=MCHPNT(LOCPNT)
	        IF(IVALUE.GE.0)GO TO 1012
	        IVALUE=-IVALUE
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 13


	        KMDNEW=IVALUE/IOFFST
	        LOCPNT=IVALUE-(IOFFST*KMDNEW)
	        IF(KMDNEW.NE.0)KMDNOW=-KMDNEW
	        GO TO 1004
	   1012 KMDNEW=IVALUE/IOFFST
	        LOCPNT=IVALUE-(IOFFST*KMDNEW)
	        IF(KMDNEW.NE.0)KMDNOW=KMDNEW
	        GO TO 1004
	  C
	  C     REPORT RESULTS WHEN ALL DONE
	   1013 IF(LOCPNT.EQ.1)GO TO 1019
	        MAXSHO=LMTBFR
	   1014 IF(LTRBFR(MAXSHO).NE.LTRSPC)GO TO 1015
	        MAXSHO=MAXSHO-1
	        GO TO 1014
	   1015 IF(MINPRT.GT.MAXPRT)GO TO 1017
	        IF(MAXPRT.GE.MAXSHO)WRITE(ITTY,1016)KMDNOW,
	       1(LTRBFR(I),I=MINPRT,MAXPRT)
	   1016 FORMAT(8H COMMAND,1I3,2H: ,31A1)
	        LOCBFR=MAXPRT+1
	        IF(MAXPRT.LT.MAXSHO)WRITE(ITTY,1016)KMDNOW,
	       1(LTRBFR(I),I=MINPRT,MAXPRT),LTRSTR,
	       2(LTRBFR(I),I=LOCBFR,MAXSHO)
	        GO TO 1001
	   1017 WRITE(ITTY,1018)(LTRBFR(I),I=LOCBFR,MAXSHO)
	   1018 FORMAT(18H UNKNOWN COMMAND: ,30A1)
	        GO TO 1001
	   1019 WRITE(ITTY,1020)
	   1020 FORMAT(11H EMPTY LINE)
	        GO TO 1001
	        END


	   A Description of the Algorithm Used by the KEYWRD Program
	   - ----------- -- --- --------- ---- -- --- ------ -------

	  The first printing character in each new line read from  the
	  input  file  is  checked  to  determine  if it is one of the
	  reserved characters.  If the  line  instead  begins  with  a
	  number,  then this number is evaluated and the spaces and/or
	  a single  comma  following  the  number  are  discarded.   A
	  decision  tree is then constructed which describes the paths
	  by which the characters in the word or in the  phrase  could
	  have  been  recognized.   Each  node  in  the  decision tree
	  specifies the node from which it can be reached and  whether
	  it  is  reached  upon the success or upon the failure, never
	  both, of  the  test  described  by  that  node.   The  first
	  character  of the second and of each of the subsequent words
	  in a phrase is included in separate tests which are  reached
	  on  failures  to  match each appearance of the second and of
	  each of the subsequent characters of the previous word,  and
	  is  also  included  in separate tests which are reached upon
	  successful matches of each appearance of the final character
	  of  the  previous word.  If the command consists of a single
	  word, then the decision tree is a  simple  chain  of  tests,
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 14


	  each  node  indicating  that  it is reached only if the test
	  described by  the  previous  node  is  successful.   If  the
	  command  consists  of  more  than  a  single word, then each
	  character in the second word appears in  as  many  tests  as
	  there are characters in the first word.  Each character in a
	  third word would appear in a number of tests  equal  to  the
	  number  of  characters in the first word times the number of
	  characters in the second, and  so  on.   The  decision  tree
	  which can be used to identify the new command is appended to
	  the arrays which  are  used  to  store  the  decision  trees
	  already obtained for the previously read commands.

	  For example, the input file

	  10 WHO ARE YOU
	  20 WHO AM I
	  0

	  would be converted into the 2 trees which  are  shown  below
	  after the second line of the input file is read.

	                               17 26 35
	                                Y--O--U
	                               /10 10 10
	                              /20 29 38
	                             /  Y--O--U
	                            /  /10 10 10
	                       5  8/11/14 23 32
	                       A--R--E--Y--O--U
	                      /10 10 10 10 10 10
	                     /         18 27 36
	                    /           Y--O--U
	                   /           /10 10 10
	                  /           /21 30 39
	                 /           /  Y--O--U
	                /           /  /10 10 10
	               /       6  9/12/15 24 33
	              /        A--R--E--Y--O--U
	             /        /10 10 10 10 10 10
	            /        /         16 25 34
	           /        /           Y--O--U
	          /        /           /10 10 10
	         /        /           /19 28 37
	        /        /           /  Y--O--U
	       /        /           /  /10 10 10
	  1  2/       3/       4  7/10/13 22 31
	  W--H--------O--------A--R--E--Y--O--U
	  10 10       10       10 10 10 10 10 10
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 15


	  and

	                       53
	                        I
	                       /20
	                 44 47/50
	                  A--M--I
	                 /20 20 20
	                /      54
	               /        I
	              /        /20
	             /   45 48/51
	            /     A--M--I
	           /     /20 20 20
	          /     /      52
	         /     /        I
	        /     /        /20
	  40 41/   42/   43 46/49
	   W--H-----O-----A--M--I
	   20 20    20    20 20 20

	  After a new command has been read and converted to the  back
	  pointing  decision  tree,  nodes  in  the new tree which are
	  identical to nodes in the old trees, and which  are  reached
	  under  identical  conditions, are removed and all references
	  to the removed nodes in the new tree are revised to point to
	  the  nodes  in  the old trees to which the removed nodes are
	  identical.  The portion of the  new  tree  which  is  stored
	  above  the node which is being removed is shifted downward 1
	  location and all references in this portion of the new  tree
	  to  the node being removed are changed to instead point back
	  to the node in the old trees to which the  removed  node  is
	  identical.   The  decision  tree shown below would represent
	  the input file shown above after the redundant subphrase WHO
	  A  is  removed  from  the  second command.  There are then 2
	  nodes which branch from node 4 on a success, 2 from 5 and  2
	  from 6.
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 16


	                                           17 26 35
	                                            Y--O--U
	                                           /10 10 10
	                                          /20 29 38
	                                         /  Y--O--U
	                                        /  /10 10 10
	                                      8/11/14 23 32
	                                   :--R--E--Y--O--U
	                                   :  10 10 10 10 10
	                                   :    47
	                                   :     I
	                                   :    /20
	                                   5 41/ 44
	                                   A--M--I
	                                  /0  20 20
	                                 /         18 27 36
	                                /           Y--O--U
	                               /           /10 10 10
	                              /           /21 30 39
	                             /           /  Y--O--U
	                            /           /  /10 10 10
	                           /          9/12/15 24 33
	                          /        :--R--E--Y--O--U
	                         /         :  10 10 10 10 10
	                        /          :    48
	                       /           :     I
	                      /            :    /20
	                     /             6 42/ 45
	                    /              A--M--I
	                   /              /0  20 20
	                  /              /         16 25 34
	                 /              /           Y--O--U
	                /              /           /10 10 10
	               /              /           /19 28 37
	              /              /           /  Y--O--U
	             /              /           /  /10 10 10
	            /              /          7/10/13 22 31
	           /              /        :--R--E--Y--O--U
	          /              /         :  10 10 10 10 10
	         /              /          :    46
	        /              /           :     I
	       /              /            :    /20
	  1  2/             3/             4 40/ 43
	  W--H--------------O--------------A--M--I
	  0  0              0              0  20 20

	  The roots of the remaining trees, which will each begin with
	  a  different  character, are chained together in a series of
	  failure transfers when the end of the input  file  is  read.
	  The  resulting  single back pointing decision tree must then
	  be converted into a forward pointing decision tree in  which
	  each  node  indicates  the node which is to follow it in the
	  event of a success or of a failure.   A  node  in  the  back
	  pointing  decision tree can be reached only upon the success
	  or the failure of a single node which is stored lower in the
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 17


	  arrays  since all linking and relinking has been to nodes in
	  older trees and since  the  nodes  are  still  in  the  same
	  relative  order  as when they were constructed.  Since nodes
	  can only be reached from nodes which are stored lower in the
	  arrays,  a  single  pass  through  the arrays can be used to
	  convert from the back pointing decision tree to the  forward
	  pointing  decision  tree.   If  a  node indicates that it is
	  reached by a failure of a node  which  represents  a  letter
	  which  is  higher  in  the  alphabet,  then the tree must be
	  relinked to place the new  node  earlier  in  the  chain  of
	  failures than that which is indicated to be its predecessor.
	  In this reordering, as in all situations in which characters
	  are  compared, characters which appear at the start of words
	  are considered to be in a second and higher  alphabet.   The
	  following forward pointing decision tree would represent the
	  sample input file shown above.

	                                        17 26 35
	                                         Y--O--U
	                                        /10 10 10
	                                     47/20 29 38
	                                      I  Y--O--U
	                                     /20/10 10 10
	                                   8/11/14 23 32
	                                   R--E--Y--O--U
	                                  /10 10 10 10 10
	                             5 41/ 44
	                             A--M--I
	                            /0  20 20
	                           /            18 27 36
	                          /              Y--O--U
	                         /              /10 10 10
	                        /            48/21 30 39
	                       /              I  Y--O--U
	                      /              /20/10 10 10
	                     /             9/12/15 24 33
	                    /              R--E--Y--O--U
	                   /              /10 10 10 10 10
	                  /          6 42/ 45
	                 /           A--M--I
	                /           /0  20 20
	               /           /            16 25 34
	              /           /              Y--O--U
	             /           /              /10 10 10
	            /           /            46/19 28 37
	           /           /              I  Y--O--U
	          /           /              /20/10 10 10
	         /           /             7/10/13 22 31
	        /           /              R--E--Y--O--U
	       /           /              /10 10 10 10 10
	  1  2/          3/          4 40/ 43
	  W--H-----------O-----------A--M--I
	  0  0           0           0  20 20

	  Each  chain  of  failures  is  next  purged   of   identical
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 18


	  characters,  since  the  second  appearance  of a particular
	  character in a chain of failures can never be reached.  When
	  a  duplicate  is  found,  then the chain of failures must be
	  linked around the node  being  removed,  and  the  chain  of
	  failures  extending  from the success transfer from the node
	  being removed must be merged  with  the  chain  of  failures
	  extending  from  the  success  transfer  from the node being
	  kept, weaving the 2 chains together to obtain a single chain
	  in which the characters are tested in alphabetical order.

	  Once the tree has been purged of identical characters in the
	  chains  of  failures,  the  nodes which represent the unique
	  characters in all possible  abbreviations  of  each  command
	  must be identified so that these nodes can be preserved when
	  identical branches of the decision  tree  are  merged.   The
	  nodes  which  must  be  preserved are those which are on the
	  chains of failures extending from the success transfers from
	  the  nodes  which  are known to be ambiguous by their having
	  been on roots which were merged.

	  Identical nodes which are at the ends  of  the  branches  or
	  which  transfer  to  the  same  nodes  are  merged  if these
	  identical  nodes  are  not  marked  as  representing  unique
	  characters in different commands.  Since it is not necessary
	  to preserve the relative order of the storage of  the  nodes
	  in  the  arrays, the node being removed is interchanged with
	  that at the upper end of the arrays and  all  references  to
	  both nodes are patched.  This interchange prevents having to
	  shift several nodes  each  time  a  node  must  be  removed.
	  Pruning of the identical branches would convert the decision
	  tree shown above to that which is shown below.

	                                    6 11 12
	                           /--/--/--Y--O--U
	                         5/  /  /   10 10 10
	                         I  /  /
	                        /20/  /
	                      7/10/  /
	                      R--E--/
	                     /10 10
	                4  9/ 8
	       /--/--/--A--M--I
	  1  2/ 3/  /   0  20 20
	  W--H--O--/
	  0  0  0

	  To make the decision tree easier to diagram, the  nodes  are
	  rearranged into the order in which the nodes are encountered
	  when the decision tree is climbed.  The decision tree  shown
	  above would finally be reduced to that which is shown below.
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 19


	                                   10 11 12
	                           /--/--/--Y--O--U
	                         9/  /  /   10 10 10
	                         I  /  /
	                        /20/  /
	                      7/ 8/  /
	                      R--E--/
	                     /10 10
	                4  5/ 6
	       /--/--/--A--M--I
	  1  2/ 3/  /   0  20 20
	  W--H--O--/
	  0  0  0

	  When the optional spaces before each of the words of each of
	  the  phrases  are  included, the decision tree would instead
	  appear as is shown below.

	                                                     10 11 12
	                                        /--/--/-space-Y--O--U
	                                      9/  /  /        10 10 10
	                              /-space-I  /  /
	                             /        20/  /
	                           7/         8/  /
	                           R----------E--/
	                          /10 10
	                     4  5/        6
	       /--/--/-space-A--M--space--I
	  1  2/ 3/  /        0  20        20
	  W--H--O--/
	  0  0  0

	  The following listing file would be produced when the  above
	  decision tree is constructed.

	       10 WHO A(RE YOU)
	          WHO A(R YOU)
	          WHO A (YOU)
	          WH A(RE YOU)
	          WH A(R YOU)
	          WH A (YOU)
	          W A(RE YOU)
	          W A(R YOU)
	          W A (YOU)
	       20 WHO A(M I)
	          WHO A (I)
	          WH A(M I)
	          WH A (I)
	          W A(M I)
	          W A (I)
	  KEYWRD, Word and Phrase Recognition Logic Generator  Page 20


	  The following FORTRAN statement file represents the decision
	  tree shown above.

	  C     10 WHO ARE YOU
	  C     20 WHO AM I
	  C
	  C     FINAL STORAGE USED=  12, MOST USED=   54, LIMIT= 3000
	  C
	  C     CHECKSUMS  880,  30,1121, 448, 288
	  C
	  C     COUNT     1  2  3  4  5  6  7  8  9 10 11 12
	  C     COMMAND   0  0  0  0 20 20 10 10 20 10 10 10
	  C     LETTER   -W  H  O -A  M -I  R  E -I -Y  O  U
	  C     SUCCESS   2  3  4  5  6  0  8 10  0 11 12  0
	  C     FAILURE   0  4  4  0  7  0  9 10 10  0  0  0
	  C
	  C     DIMENSION MCHPNT(12)
	        DIMENSION MCHPN1(12)
	        EQUIVALENCE (MCHPN1(1),MCHPNT(1))
	  C     DIMENSION NOTPNT(12)
	        DIMENSION NOTPN1(12)
	        EQUIVALENCE (NOTPN1(1),NOTPNT(1))
	        DATA KNTPNT,KNTXTR/   12,    0/
	        DATA MCHPN1/2,3,4,5,266,260,138,140,260,141,142,130/
	        DATA NOTPN1/-299,108,199,-13,176,-117,243,75,-127,
	       1-325,195,273/


	  The KEYWRD program and this documentation  were  written  at
	  the  Harvard  Business School by Donald E. Barth, who can be
	  reached at the following address.

	  Baker Library 21
	  Graduate School of Business Administration
	  Harvard University, Soldiers Field
	  Boston, Massachusetts  02163