home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / convergent / ctwart.c < prev    next >
C/C++ Source or Header  |  2020-01-01  |  12KB  |  628 lines
  1. /* W A R T
  2.  *
  3.  * pre-process a lex-like file into a C program.
  4.  *
  5.  * Jeff Damens, Columbia University Center for Computing Activites, 11/84.
  6.  * (Reorganized by Frank da Cruz into a single source module for ease
  7.  * of distribution).
  8.  * Copyright (C) 1984, Trustees of Columbia University.
  9.  * May be copied and used except for explicitly commercial purposes.
  10.  *
  11.  * input format is:
  12.  *  lines to be copied | %state <state names...>
  13.  *  %%
  14.  * <state> | <state,state,...> CHAR  { actions }
  15.  * ...
  16.  *  %%
  17.  */
  18.  
  19.  
  20. /* modified for CTOS C2.0 by Joel Dunn, UNC-CH, October 1986 */
  21.  
  22. #include <stdio.h>
  23. #include <ctype.h>
  24.  
  25. /* token types */
  26.  
  27. #define SEP 1
  28. #define LBRACK 2
  29. #define RBRACK 3
  30. #define WORD 4
  31. #define COMMA 5
  32.  
  33. /* storage sizes */
  34.  
  35. #define MAXSTATES 50            /* max number of states */
  36. #define MAXWORD 50            /* max # of chars/word */
  37. #define SBYTES ((MAXSTATES+7)/8)    /* # of bytes for state bitmask */
  38.  
  39. /* name of wart function in generated program */
  40.  
  41. #ifndef FNAME
  42. #define FNAME "wart"
  43. #endif
  44.  
  45. /* data structure for state information */
  46.  
  47. #ifdef PROVX1
  48. typedef unsigned short CHAR;
  49. #else
  50. typedef unsigned char CHAR;
  51. #endif
  52.  
  53. struct trans { CHAR states[SBYTES];    /* included states */
  54.                int anyst;        /* true if this good from any state */
  55.                CHAR inchr;        /* input character */
  56.            int actno;        /* associated action */
  57.            struct trans *nxt; };    /* next transition */
  58.  
  59. typedef struct trans *Trans;
  60.  
  61. /* Variables and tables */
  62.  
  63. int lines,nstates,nacts;
  64.  
  65. char tokval[MAXWORD];
  66.  
  67. int tbl[MAXSTATES*128];
  68.  
  69.  
  70.  
  71. char *txt1 = "\n\
  72. #define BEGIN state =\n\
  73. \n\
  74. int state = 0;\n\
  75. \n";
  76.  
  77. char *fname = FNAME;        /* function name goes here */
  78.  
  79. /* rest of program... */
  80.  
  81. char *txt2 = "()\n\
  82. {\n\
  83.   int c,actno;\n\
  84.   extern int tbl[];\n\
  85.   while (1) {\n\
  86.     c = input();\n\
  87.     if ((actno = tbl[c + state*128]) != -1)\n\
  88.       switch(actno) {\n";
  89.  
  90. /* this program's output goes here, followed by final text... */
  91.  
  92. char *txt3 = "\n    }\n  }\n\}\n\n";
  93.  
  94. /*
  95.  * turn on the bit associated with the given state
  96.  *
  97.  */
  98. setstate(state,t)
  99. int state;
  100. Trans t;
  101. {
  102.   int idx,msk;
  103.   idx = state/8;            /* byte associated with state */
  104.   msk = 0x80 >> (state % 8);        /* bit mask for state */
  105.   t->states[idx] |= msk;
  106. }
  107.  
  108. /*
  109.  * see if the state is involved in the transition
  110.  *
  111.  */
  112.  
  113. teststate(state,t)
  114. int state;
  115. Trans t;
  116. {
  117.   int idx,msk;
  118.   idx = state/8;
  119.   msk = 0x80 >> (state % 8);
  120.   return(t->states[idx] & msk);
  121. }
  122.  
  123.  
  124. /*
  125.  * read input from here...
  126.  *
  127.  */
  128.  
  129. Trans
  130. rdinput(infp,outfp)
  131. FILE *infp,*outfp;
  132. {
  133.   Trans x,rdrules();
  134.   lines = 1;                /* line counter */
  135.   nstates = 0;                /* no states */
  136.   nacts = 0;                /* no actions yet */
  137.   fprintf(outfp,"\n\
  138. /* WARNING -- This C source program generated by Wart preprocessor. */\n");
  139.   fprintf(outfp,"\
  140. /* Do not edit this file; edit the Wart-format source file instead, */\n");
  141.   fprintf(outfp,"\
  142. /* and then run it through Wart to produce a new C source file.     */\n\n");
  143.   initial(infp,outfp);            /* read state names, initial defs */
  144.   prolog(outfp);            /* write out our initial code */
  145.   x = rdrules(infp,outfp);        /* read rules */
  146.   epilogue(outfp);            /* write out epilogue code */
  147.   return(x);
  148. }
  149.  
  150. /*
  151.  * initial - read initial definitions and state names.  Returns
  152.  * on EOF or %%.
  153.  *
  154.  */
  155.  
  156. initial(infp,outfp)
  157. FILE *infp,*outfp;
  158. {
  159.   int c;
  160.   char wordbuf[MAXWORD];
  161.   while ((c = getc(infp)) != EOF) {
  162.     if (c == '%') {
  163.             rdword(infp,wordbuf);
  164.             if (strcmp(wordbuf,"states") == 0)
  165.                 rdstates(infp,outfp);
  166.             else if (strcmp(wordbuf,"%") == 0) return;
  167.             else fprintf(outfp,"%%%s",wordbuf);
  168.               }
  169.     else putc(c,outfp);
  170.     if (c == '\n') lines++;
  171.      }
  172. }
  173.  
  174. /*
  175.  * boolean function to tell if the given character can be part of
  176.  * a word.
  177.  *
  178.  */
  179. isin(s,c) char *s; int c; {
  180.    for (; *s != '\0'; s++)
  181.       if (*s == c) return(1);
  182.    return(0);
  183. }
  184. isword(c)
  185. int c;
  186. {
  187.   static char special[] = ".%_-$@";    /* these are allowable */
  188.   return(isalnum(c) || isin(special,c));
  189. }
  190.  
  191. /*
  192.  * read the next word into the given buffer.
  193.  *
  194.  */
  195. rdword(fp,buf)
  196. FILE *fp;
  197. char *buf;
  198. {
  199.   int len = 0,c;
  200.   while (isword(c = getc(fp)) && ++len < MAXWORD) *buf++ = c;
  201.   *buf++ = '\0';            /* tie off word */
  202.   ungetc(c,fp);                /* put break char back */
  203. }
  204.  
  205. /*
  206.  * read state names, up to a newline.
  207.  *
  208.  */
  209.  
  210. rdstates(fp,ofp)
  211. FILE *fp,*ofp;
  212. {
  213.   int c;
  214.   char wordbuf[MAXWORD];
  215.   while ((c = getc(fp)) != EOF && c != '\n')
  216.   {
  217.     if (isspace(c)) continue;    /* skip whitespace */
  218.     ungetc(c,fp);            /* put char back */
  219.     rdword(fp,wordbuf);        /* read the whole word */
  220.     enter(wordbuf,++nstates);    /* put into symbol tbl */
  221.     fprintf(ofp,"#define %s %d\n",wordbuf,nstates);
  222.   }
  223.   lines++;
  224. }
  225.         
  226. /*
  227.  * allocate a new, empty transition node
  228.  *
  229.  */
  230.  
  231. Trans
  232. newtrans()
  233. {
  234.   Trans new;
  235.   int i;
  236.   new = (Trans) malloc(sizeof (struct trans));
  237.   for (i=0; i<SBYTES; i++) new->states[i] = 0;
  238.   new->anyst = 0;
  239.   new->nxt = NULL;
  240.   return(new);
  241. }
  242.  
  243. /*
  244.  * read all the rules.
  245.  *
  246.  */
  247.  
  248. Trans
  249. rdrules(fp,out)
  250. FILE *fp,*out;
  251. {
  252.   Trans head,cur,prev;
  253.   int curtok,i;
  254.   head = cur = NULL;
  255.   while ((curtok = gettoken(fp)) != SEP) 
  256.  
  257.     switch(curtok) {
  258.         case LBRACK: if (cur == NULL) cur = newtrans();
  259.                      else fatal("duplicate state list");
  260.                  statelist(fp,cur);/* set states */
  261.                  continue;    /* prepare to read char */
  262.  
  263.         case WORD:   if (strlen(tokval) != 1)
  264.                     fatal("multiple chars in state");
  265.                  if (cur == NULL) {
  266.                 cur = newtrans();
  267.                 cur->anyst = 1;
  268.                 }
  269.                  cur->actno = ++nacts;
  270.                  cur->inchr = tokval[0];
  271.                  if (head == NULL) head = cur;
  272.                  else prev->nxt = cur;
  273.                  prev = cur;
  274.                  cur = NULL;
  275.                  copyact(fp,out,nacts);
  276.                  break; 
  277.          default: fatal("bad input format");
  278.          }
  279.     
  280.    return(head);
  281. }
  282.  
  283. /*
  284.  * read a list of (comma-separated) states, set them in the
  285.  * given transition.
  286.  *
  287.  */
  288. statelist(fp,t)
  289. FILE *fp;
  290. Trans t;
  291. {
  292.   int curtok,sval;
  293.   curtok = COMMA;
  294.   while (curtok != RBRACK) {
  295.     if (curtok != COMMA) fatal("missing comma");
  296.     if ((curtok = gettoken(fp)) != WORD) fatal("missing state name");
  297.         if ((sval = lkup(tokval)) == -1) {
  298.         fprintf(stderr,"state %s undefined\n",tokval);
  299.         fatal("undefined state");
  300.        }
  301.         setstate(sval,t);
  302.     curtok = gettoken(fp);
  303.    }
  304. }
  305.  
  306. /*
  307.  * copy an action from the input to the output file
  308.  *
  309.  */
  310. copyact(inp,outp,actno)
  311. FILE *inp,*outp;
  312. int actno;
  313. {
  314.   int c,bcnt;
  315.   fprintf(outp,"case %d:\n",actno);
  316.   while ((c = getc(inp)) != '\n' && isspace(c));    /* skip whitespace */
  317.   if (c == '{') {
  318.      bcnt = 1;
  319.      putc(c,outp);
  320.      while (bcnt > 0 && (c = getc(inp)) != EOF) {
  321.     if (c == '{') bcnt++;
  322.     else if (c == '}') bcnt--;
  323.     else if (c == '\n') lines++;
  324.     putc(c,outp);
  325.       }
  326.      if (bcnt > 0) fatal("action doesn't end");
  327.     }
  328.    else {
  329.       while (c != '\n' && c != EOF) {
  330.         putc(c,outp);
  331.         c = getc(inp);
  332.         }
  333.       lines++;
  334.     }
  335.    fprintf(outp,"\nbreak;\n");
  336. }
  337.  
  338. /*
  339.  * find the action associated with a given character and state.
  340.  * returns -1 if one can't be found.
  341.  *
  342.  */
  343. faction(hd,state,chr)
  344. Trans hd;
  345. int state,chr;
  346. {
  347.   while (hd != NULL) {
  348.     if (hd->anyst || teststate(state,hd))
  349.       if (hd->inchr == '.' || hd->inchr == chr) return(hd->actno);
  350.     hd = hd->nxt;
  351.     }
  352.   return(-1);
  353. }
  354.  
  355.  
  356. /*
  357.  * empty the table...
  358.  *
  359.  */
  360. emptytbl()
  361. {
  362.   int i;
  363.   for (i=0; i<nstates*128; i++) tbl[i] = -1;
  364. }
  365.  
  366. /*
  367.  * add the specified action to the output for the given state and chr.
  368.  *
  369.  */
  370.  
  371. addaction(act,state,chr)
  372. int act,state,chr;
  373. {
  374.  tbl[state*128 + chr] = act;
  375. }
  376.  
  377. writetbl(fp)
  378. FILE *fp;
  379. {
  380.   warray(fp,"tbl",tbl,128*(nstates+1));
  381. }
  382.  
  383. /*
  384.  * write an array to the output file, given its name and size.
  385.  *
  386.  */
  387. warray(fp,nam,cont,siz)
  388. FILE *fp;
  389. char *nam;
  390. int cont[],siz;
  391. {
  392.   int i;
  393.   fprintf(fp,"int %s[] = {\n",nam);
  394.   for (i = 0; i < siz; i++) {
  395.     fprintf(fp,"%d, ",cont[i]);
  396.     if ((i % 20) == 0) putc('\n',fp);
  397.     }
  398.   fprintf(fp,"};\n");
  399. }
  400.  
  401. main(argc, argv)
  402.   int argc;
  403.   char **argv;
  404. {
  405.   Trans head;
  406.   int state,c;
  407.   FILE *infile,*outfile;
  408.  
  409.   if (argc > 1) {
  410.   argv++;
  411.     if ((infile = fopen(*argv,"r")) == NULL) {
  412.         fprintf(stderr,"Can't open %s\n",*argv);
  413.     fatal("unreadable input file"); } }
  414.   else infile = stdin;
  415.  
  416.   if (argc > 2) {
  417.   argv++;
  418.     if ((outfile = fopen(*argv,"w")) == NULL) {
  419.         fprintf(stderr,"Can't write to %s\n",*argv);
  420.     fatal("bad output file"); } }
  421.   else outfile = stdout;
  422.  
  423.   clrhash();                /* empty hash table */
  424.   head = rdinput(infile,outfile);    /* read input file */
  425.   emptytbl();                /* empty our tables */
  426.   for (state = 0; state <= nstates; state++)
  427.     for (c = 1; c < 128; c++)
  428.      addaction(faction(head,state,c),state,c);    /* find actions, add to tbl */
  429.   writetbl(outfile);
  430.   copyrest(infile,outfile);
  431.   printf("%d states, %d actions\n",nstates,nacts);
  432. #ifdef undef
  433.   for (state = 1; state <= nstates; state ++)
  434.     for (c = 1; c < 128; c++)
  435.        if (tbl[state*128 + c] != -1) printf("state %d, chr %d, act %d\n",
  436.            state,c,tbl[state*128 + c]);
  437. #endif                 
  438.   fclose(infile);
  439.   fclose(outfile);
  440.   exit(0);
  441. }
  442.  
  443. /*
  444.  * fatal error handler
  445.  *
  446.  */
  447.  
  448. fatal(msg)
  449. char *msg;
  450. {
  451.   fprintf(stderr,"error in line %d: %s\n",lines,msg);
  452.   exit(1);
  453. }
  454.  
  455. prolog(outfp)
  456. FILE *outfp;
  457. {
  458.   int c;
  459.   while ((c = *txt1++) != '\0')  putc(c,outfp);
  460.   while ((c = *fname++) != '\0') putc(c,outfp);
  461.   while ((c = *txt2++) != '\0')  putc(c,outfp);
  462. }
  463.  
  464. epilogue(outfp)
  465. FILE *outfp;
  466. {
  467.   int c;
  468.   while ((c = *txt3++) != '\0') putc(c,outfp);
  469. }
  470.  
  471. copyrest(in,out)
  472. FILE *in,*out;
  473. {
  474.   int c;
  475.   while ((c = getc(in)) != EOF) putc(c,out);
  476. }
  477.  
  478. /*
  479.  * gettoken - returns token type of next token, sets tokval
  480.  * to the string value of the token if appropriate.
  481.  *
  482.  */
  483.  
  484. gettoken(fp)
  485. FILE *fp;
  486. {
  487.   int c;
  488.   while (1) {                /* loop if reading comments... */
  489.     do {
  490.       c = getc(fp);
  491.       if (c == '\n') lines++;
  492.        } while (isspace(c));        /* skip whitespace */
  493.     switch(c) {
  494.       case EOF: return(SEP);
  495.       case '%': if ((c = getc(fp)) == '%') return(SEP);
  496.             tokval[0] = '%';
  497.             tokval[1] = c;
  498.             rdword(fp,tokval+2);
  499.             return(WORD);
  500.       case '<': return(LBRACK);
  501.       case '>': return(RBRACK);
  502.       case ',': return(COMMA);
  503.       case '/': if ((c = getc(fp)) == '*') {
  504.                   rdcmnt(fp);    /* skip over the comment */
  505.               continue; }    /* and keep looping */
  506.             else {
  507.             ungetc(c);    /* put this back into input */
  508.             c = '/'; }    /* put character back, fall thru */
  509.  
  510.       default: if (isword(c)) {
  511.               ungetc(c,fp);
  512.               rdword(fp,tokval);
  513.               return(WORD);
  514.                   }
  515.            else fatal("Invalid character in input");
  516.          }
  517.   }
  518. }
  519.  
  520. /*
  521.  * skip over a comment
  522.  *
  523.  */
  524.  
  525. rdcmnt(fp)
  526. FILE *fp;
  527. {
  528.   int c,star,prcnt;
  529.   prcnt = star = 0;            /* no star seen yet */
  530.   while (!((c = getc(fp)) == '/' && star)) {
  531.     if (c == EOF || (prcnt && c == '%')) fatal("Unterminated comment");
  532.     prcnt = (c == '%');
  533.     star = (c == '*');
  534.     if (c == '\n') lines++; }
  535. }
  536.  
  537.  
  538. /*
  539.  * symbol table management for wart
  540.  *
  541.  * entry points:
  542.  *   clrhash - empty hash table.
  543.  *   enter - enter a name into the symbol table
  544.  *   lkup - find a name's value in the symbol table.
  545.  *
  546.  */
  547.  
  548. #define HASHSIZE 101            /* # of entries in hash table */
  549.  
  550. struct sym { char *name;        /* symbol name */
  551.          int val;            /* value */
  552.          struct sym *hnxt; }    /* next on collision chain */
  553.     *htab[HASHSIZE];            /* the hash table */
  554.  
  555.  
  556. /*
  557.  * empty the hash table before using it...
  558.  *
  559.  */
  560. clrhash()
  561. {
  562.   int i;
  563.   for (i=0; i<HASHSIZE; i++) htab[i] = NULL;
  564. }
  565.  
  566. /*
  567.  * compute the value of the hash for a symbol
  568.  *
  569.  */
  570. hash(name)
  571. char *name;
  572. {
  573.   int sum;
  574.   for (sum = 0; *name != '\0'; name++) sum += (sum + *name);
  575.   sum %= HASHSIZE;            /* take sum mod hashsize */
  576.   if (sum < 0) sum += HASHSIZE;        /* disallow negative hash value */
  577.   return(sum);
  578. }
  579.  
  580. /*
  581.  * make a private copy of a string...
  582.  *
  583.  */
  584. char *
  585. copy(s)
  586. char *s;
  587. {
  588.   char *new;
  589.   new = (char *) malloc(strlen(s) + 1);
  590.   strcpy(new,s);
  591.   return(new);
  592. }
  593.  
  594. /*
  595.  * enter state name into the hash table
  596.  *
  597.  */
  598. enter(name,svalue)
  599. char *name;
  600. int svalue;
  601. {
  602.   int h;
  603.   struct sym *cur;
  604.   if (lkup(name) != -1) {
  605.     fprintf(stderr,"state %s appears twice...\n");
  606.     exit(1); }
  607.   h = hash(name);
  608.   cur = (struct sym *)malloc(sizeof (struct sym));
  609.   cur->name = copy(name);
  610.   cur->val = svalue;
  611.   cur->hnxt = htab[h];
  612.   htab[h] = cur;
  613. }
  614.  
  615. /*
  616.  * find name in the symbol table, return its value.  Returns -1
  617.  * if not found.
  618.  *
  619.  */
  620. lkup(name)
  621. char *name;
  622. {
  623.   struct sym *cur;
  624.   for (cur = htab[hash(name)]; cur != NULL; cur = cur->hnxt)
  625.     if (strcmp(cur->name,name) == 0) return(cur->val);
  626.   return(-1);
  627. }
  628.