commands/yap/machine.c

   1 /* Copyright (c) 1985 Ceriel J.H. Jacobs */
   2
   3 # ifndef lint
   4 static char rcsid[] = "$Header$";
   5 # endif
   6
   7 # define _MACHINE_
   8
   9 # include <ctype.h>
  10 # include "in_all.h"
  11 # include "machine.h"
  12 # include "getline.h"
  13 # include "assert.h"
  14
  15 /*
  16  * Add part of finite state machine to recognize the string s.
  17  */
  18
  19 STATIC int
  20 addtomach(s, cnt, list) char *s; struct state **list; {
  21
  22         register struct state *l;
  23         register int i = FSM_OKE;       /* Return value */
  24         register int j;
  25
  26         for (;;) {
  27                 l = *list;
  28                 if (!l) {
  29                         /*
  30                          * Create new list element
  31                          */
  32                         *list = l = (struct state *) alloc(sizeof(*l), 0);
  33                         l->s_char = *s;
  34                         l->s_endstate = 0;
  35                         l->s_match = 0;
  36                         l->s_next = 0;
  37                 }
  38                 if (l->s_char == *s) {
  39                         /*
  40                          * Continue with next character
  41                          */
  42                         if (!*++s) {
  43                                 /*
  44                                  * No next character
  45                                  */
  46                                 j = l->s_endstate;
  47                                 l->s_endstate = 1;
  48                                 if (l->s_match || j) {
  49                                         /*
  50                                          * If the state already was an endstate,
  51                                          * or has a successor, the currently
  52                                          * added string is a prefix of an
  53                                          * already recognized string
  54                                          */
  55                                         return FSM_ISPREFIX;
  56                                 }
  57                                 l->s_cnt = cnt;
  58                                 return i;
  59                         }
  60                         if (l->s_endstate) {
  61                                 /*
  62                                  * In this case, the currently added string has
  63                                  * a prefix that is an already recognized
  64                                  * string.
  65                                  */
  66                                 i = FSM_HASPREFIX;
  67                         }
  68                         list = &(l->s_match);
  69                         continue;
  70                 }
  71                 list = &(l->s_next);
  72         }
  73         /* NOTREACHED */
  74 }
  75
  76 /*
  77  * Add a string to the FSM.
  78  */
  79
  80 int
  81 addstring(s,cnt,machine) register char *s; struct state **machine; {
  82
  83         if (!s || !*s) {
  84                 return FSM_ISPREFIX;
  85         }
  86         return addtomach(s,cnt,machine);
  87 }
  88
  89 /*
  90  * Match string s with the finite state machine.
  91  * If it matches, the number of characters actually matched is returned,
  92  * and the count is put in the word pointed to by i.
  93  * If the string is a prefix of a string that could be matched,
  94  * FSM_ISPREFIX is returned. Otherwise, 0 is returned.
  95  */
  96
  97 int
  98 match(s,i,mach) char *s; int *i; register struct state *mach; {
  99
 100         register char *s1 = s;  /* Walk through string */
 101         register struct state *mach1 = 0;
 102                                 /* Keep track of previous state */
 103
 104         while (mach && *s1) {
 105                 if (mach->s_char == *s1) {
 106                         /*
 107                          * Current character matches. Carry on with next
 108                          * character and next state
 109                          */
 110                         mach1 = mach;
 111                         mach = mach->s_match;
 112                         s1++;
 113                         continue;
 114                 }
 115                 mach = mach->s_next;
 116         }
 117         if (!mach1) {
 118                 /*
 119                  * No characters matched
 120                  */
 121                 return 0;
 122         }
 123         if (mach1->s_endstate) {
 124                 /*
 125                  * The string matched
 126                  */
 127                 *i = mach1->s_cnt;
 128                 return s1 - s;
 129         }
 130         if (!*s1) {
 131                 /*
 132                  * The string matched a prefix
 133                  */
 134                 return FSM_ISPREFIX;
 135         }
 136         return 0;
 137 }