a56/keybld.c

   1 /*
   2  * Copyright (C) 1990-1994 Quinn C. Jensen
   3  *
   4  * Permission to use, copy, modify, distribute, and sell this software
   5  * and its documentation for any purpose is hereby granted without fee,
   6  * provided that the above copyright notice appear in all copies and
   7  * that both that copyright notice and this permission notice appear
   8  * in supporting documentation.  The author makes no representations
   9  * about the suitability of this software for any purpose.  It is
  10  * provided "as is" without express or implied warranty.
  11  *
  12  */
  13 static char *Copyright = "Copyright (C) 1990-1994 Quinn C. Jensen";
  14
  15 /*
  16  * keybld - builds a finite-state parser for the given keyword list
  17  *
  18  */
  19
  20 #include <stdio.h>
  21 #include "a56.h"
  22
  23 char buf[1024];
  24
  25 main()
  26 {
  27         int line = 0;
  28
  29         while(gets(buf)) {
  30                 char *bp = buf;
  31                 line++;
  32                 while(*bp != '\t' && *bp != ' ') bp++;
  33                 *bp++ = '\0';
  34                 while(*bp == '\t' || *bp == ' ') bp++;
  35                 if(strcmp(buf, ".code") == 0) {
  36                         printf("%s\n", bp);
  37                 } else if(add_tok(buf, bp) == -1) {
  38                         fprintf(stderr, "input line %d: ambiguous\n", line);
  39                 }
  40         }
  41
  42         dump_machine();
  43         return 0;
  44 }
  45
  46 #define MAX_CHAR 'z'
  47
  48 #define TRANSITIONS (MAX_CHAR + 1)
  49
  50 struct state {
  51         int number;
  52         char *seen;
  53         struct trans {
  54                 char action;
  55                 void *arg;
  56         } trans[TRANSITIONS];
  57         struct state *next;
  58 } empty_state, *stop = NULL, *scur = NULL, *new_state();
  59 int n_states = 0;
  60
  61 /* actions */
  62 #define NOMATCH 0       /* argument is nothing */
  63 #define GOTO 1          /* argument is target state */
  64 #define TERMINAL 2      /* argument is which user action to perform */
  65
  66 struct user_action {
  67         char *action;
  68         struct user_action *next;
  69 } *utop = NULL, *ucur = NULL;
  70 int n_user_actions = 0;
  71
  72 add_tok(tok, actions)
  73 char *tok, *actions;
  74 {
  75         struct state *scur;
  76         struct user_action *unew = (struct user_action *)alloc(sizeof *unew);
  77         unew->action = strsave(actions);
  78         unew->next = NULL;
  79         if(ucur)
  80                 ucur->next = unew;
  81         ucur = unew;
  82         if(utop == NULL)
  83                 utop = unew;
  84
  85         if(stop == NULL)
  86                 new_state(NULL);
  87
  88         if(follow(*tok, tok + 1, stop) == -1)
  89                 return -1;
  90
  91         n_user_actions++;
  92         return 0;
  93 }
  94
  95 follow(c, tp, sp)
  96 char c;
  97 char *tp;
  98 struct state *sp;
  99 {
 100         struct trans *arcp, *arcup;
 101
 102         if(c >= 'a' && c <= 'z') {
 103                 c -= 'a' - 'A';
 104         }
 105         arcp = sp->trans + c;
 106
 107         if(c >= 'A' && c <= 'Z') {
 108                 arcup = sp->trans + c + 'a' - 'A';
 109         } else {
 110                 arcup = arcp;
 111         }
 112
 113         if(c == '\0') {
 114                 if(arcp->action == TERMINAL) {
 115                         return -1;
 116                 } else {
 117                         arcp->action = arcup->action = TERMINAL;
 118                         arcp->arg = arcup->arg = (void *)n_user_actions;
 119                         return 0;
 120                 }
 121         } else {
 122                 if(arcp->action == GOTO) {
 123                         return follow(*tp, tp + 1, arcp->arg);
 124                 } else {
 125                         struct state *new = new_state(tp);
 126                         arcp->action = arcup->action = GOTO;
 127                         arcp->arg = arcup->arg = (void *)new;
 128                         return follow(*tp, tp + 1, new);
 129                 }
 130         }
 131 }
 132
 133 struct state *new_state(tp)
 134 char *tp;
 135 {
 136         struct state *snew = (struct state *)alloc(sizeof *snew);
 137         char tmp[1024];
 138
 139         *snew = empty_state;
 140
 141         snew->number = n_states++;
 142
 143         snew->next = NULL;
 144
 145         if(scur)
 146                 scur->next = snew;
 147         scur = snew;
 148
 149         if(stop == NULL)
 150                 stop = snew;
 151
 152         if(tp) {
 153                 strncpy(tmp, buf, tp - buf);
 154                 tmp[tp - buf] = '\0';
 155         } else
 156                 strcpy(tmp, "<nothing>");
 157
 158         snew->seen = strsave(tmp);
 159
 160         return snew;
 161 }
 162
 163 dump_machine()
 164 {
 165         struct state *sp;
 166         struct user_action *up;
 167         int n, a;
 168
 169         printf("/* state machine generated by keybld */\n");
 170         printf("/* states=%d actions=%d */\n", n_states, n_user_actions);
 171         printf("/* %d bytes required for transition table storage */\n",
 172                 sizeof(short) * TRANSITIONS * n_states);
 173
 174         printf("short transitions[%d][%d] = {\n", n_states, TRANSITIONS);
 175         for(n = 0, sp = stop; sp; sp = sp->next, n++) {
 176                 printf("        /* state %d: \"%s\" */\n", n, sp->seen);
 177                 printf("        {");
 178                 for(a = 0; a < TRANSITIONS; a++) {
 179                         struct trans *tp = sp->trans + a;
 180                         switch(tp->action) {
 181                         case GOTO:
 182                                 printf("%d", ((struct state *)tp->arg)->number);
 183                                 break;
 184                         case TERMINAL:
 185                                 printf("%d", -(int)tp->arg - 1);
 186                                 break;
 187                         case NOMATCH:
 188                                 printf("0");
 189                                 break;
 190                         }
 191                         printf(",%s", a % 20 == 19 ? "\n\t\t" : "");
 192                 };
 193                 printf("},\n");
 194         }
 195
 196         printf("};\n");
 197
 198         printf("\
 199 \n\
 200 kparse(kp)\n\
 201 char *kp;\n\
 202 {\n\
 203         int state = 0;\n\
 204 \n\
 205         for(;;) {\n\
 206                 short transition = transitions[state][*kp];\n");
 207
 208 printf("\
 209                 if(transition == 0) {\n\
 210                         return 0;\n\
 211                 } else if(transition > 0) {\n\
 212                         kp++;\n\
 213                         state = transition;\n\
 214                 } else {\n\
 215                         switch(-transition) {\n");
 216
 217         for(n = 1, up = utop; up; up = up->next, n++) {
 218                 printf("\
 219                         case %d:\n\
 220                                 %s;\n\
 221                                 break;\n", n, up->action);
 222         }
 223
 224         printf("\
 225                         }\n\
 226                         return transition;\n\
 227                 }\n\
 228         }\n\
 229 }\n");
 230
 231 }