--- /dev/null
+/*
+ * Copyright (C) 1990-1994 Quinn C. Jensen
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. The author makes no representations
+ * about the suitability of this software for any purpose. It is
+ * provided "as is" without express or implied warranty.
+ *
+ */
+static char *Copyright = "Copyright (C) 1990-1994 Quinn C. Jensen";
+
+/*
+ * keybld - builds a finite-state parser for the given keyword list
+ *
+ */
+
+#include <stdio.h>
+#include "a56.h"
+
+char buf[1024];
+
+main()
+{
+ int line = 0;
+
+ while(gets(buf)) {
+ char *bp = buf;
+ line++;
+ while(*bp != '\t' && *bp != ' ') bp++;
+ *bp++ = '\0';
+ while(*bp == '\t' || *bp == ' ') bp++;
+ if(strcmp(buf, ".code") == 0) {
+ printf("%s\n", bp);
+ } else if(add_tok(buf, bp) == -1) {
+ fprintf(stderr, "input line %d: ambiguous\n", line);
+ }
+ }
+
+ dump_machine();
+ return 0;
+}
+
+#define MAX_CHAR 'z'
+
+#define TRANSITIONS (MAX_CHAR + 1)
+
+struct state {
+ int number;
+ char *seen;
+ struct trans {
+ char action;
+ void *arg;
+ } trans[TRANSITIONS];
+ struct state *next;
+} empty_state, *stop = NULL, *scur = NULL, *new_state();
+int n_states = 0;
+
+/* actions */
+#define NOMATCH 0 /* argument is nothing */
+#define GOTO 1 /* argument is target state */
+#define TERMINAL 2 /* argument is which user action to perform */
+
+struct user_action {
+ char *action;
+ struct user_action *next;
+} *utop = NULL, *ucur = NULL;
+int n_user_actions = 0;
+
+add_tok(tok, actions)
+char *tok, *actions;
+{
+ struct state *scur;
+ struct user_action *unew = (struct user_action *)alloc(sizeof *unew);
+ unew->action = strsave(actions);
+ unew->next = NULL;
+ if(ucur)
+ ucur->next = unew;
+ ucur = unew;
+ if(utop == NULL)
+ utop = unew;
+
+ if(stop == NULL)
+ new_state(NULL);
+
+ if(follow(*tok, tok + 1, stop) == -1)
+ return -1;
+
+ n_user_actions++;
+ return 0;
+}
+
+follow(c, tp, sp)
+char c;
+char *tp;
+struct state *sp;
+{
+ struct trans *arcp, *arcup;
+
+ if(c >= 'a' && c <= 'z') {
+ c -= 'a' - 'A';
+ }
+ arcp = sp->trans + c;
+
+ if(c >= 'A' && c <= 'Z') {
+ arcup = sp->trans + c + 'a' - 'A';
+ } else {
+ arcup = arcp;
+ }
+
+ if(c == '\0') {
+ if(arcp->action == TERMINAL) {
+ return -1;
+ } else {
+ arcp->action = arcup->action = TERMINAL;
+ arcp->arg = arcup->arg = (void *)n_user_actions;
+ return 0;
+ }
+ } else {
+ if(arcp->action == GOTO) {
+ return follow(*tp, tp + 1, arcp->arg);
+ } else {
+ struct state *new = new_state(tp);
+ arcp->action = arcup->action = GOTO;
+ arcp->arg = arcup->arg = (void *)new;
+ return follow(*tp, tp + 1, new);
+ }
+ }
+}
+
+struct state *new_state(tp)
+char *tp;
+{
+ struct state *snew = (struct state *)alloc(sizeof *snew);
+ char tmp[1024];
+
+ *snew = empty_state;
+
+ snew->number = n_states++;
+
+ snew->next = NULL;
+
+ if(scur)
+ scur->next = snew;
+ scur = snew;
+
+ if(stop == NULL)
+ stop = snew;
+
+ if(tp) {
+ strncpy(tmp, buf, tp - buf);
+ tmp[tp - buf] = '\0';
+ } else
+ strcpy(tmp, "<nothing>");
+
+ snew->seen = strsave(tmp);
+
+ return snew;
+}
+
+dump_machine()
+{
+ struct state *sp;
+ struct user_action *up;
+ int n, a;
+
+ printf("/* state machine generated by keybld */\n");
+ printf("/* states=%d actions=%d */\n", n_states, n_user_actions);
+ printf("/* %d bytes required for transition table storage */\n",
+ sizeof(short) * TRANSITIONS * n_states);
+
+ printf("short transitions[%d][%d] = {\n", n_states, TRANSITIONS);
+ for(n = 0, sp = stop; sp; sp = sp->next, n++) {
+ printf(" /* state %d: \"%s\" */\n", n, sp->seen);
+ printf(" {");
+ for(a = 0; a < TRANSITIONS; a++) {
+ struct trans *tp = sp->trans + a;
+ switch(tp->action) {
+ case GOTO:
+ printf("%d", ((struct state *)tp->arg)->number);
+ break;
+ case TERMINAL:
+ printf("%d", -(int)tp->arg - 1);
+ break;
+ case NOMATCH:
+ printf("0");
+ break;
+ }
+ printf(",%s", a % 20 == 19 ? "\n\t\t" : "");
+ };
+ printf("},\n");
+ }
+
+ printf("};\n");
+
+ printf("\
+\n\
+kparse(kp)\n\
+char *kp;\n\
+{\n\
+ int state = 0;\n\
+\n\
+ for(;;) {\n\
+ short transition = transitions[state][*kp];\n");
+
+printf("\
+ if(transition == 0) {\n\
+ return 0;\n\
+ } else if(transition > 0) {\n\
+ kp++;\n\
+ state = transition;\n\
+ } else {\n\
+ switch(-transition) {\n");
+
+ for(n = 1, up = utop; up; up = up->next, n++) {
+ printf("\
+ case %d:\n\
+ %s;\n\
+ break;\n", n, up->action);
+ }
+
+ printf("\
+ }\n\
+ return transition;\n\
+ }\n\
+ }\n\
+}\n");
+
+}