home *** CD-ROM | disk | FTP | other *** search
/ Boston 2 / boston-2.iso / DOS / PROGRAM / C / LEX / BASE.C < prev    next >
Text File  |  1993-12-01  |  7KB  |  235 lines
  1. /*
  2.  * Copyright (c) 1978 Charles H. Forsyth
  3.  *
  4.  * Modified 02-Dec-80 Bob Denny -- Conditionalize debug code to reduce size
  5.  * More     29-May-81 Bob Denny -- RSX overlaying
  6.  * More     19-Mar-82 Bob Denny -- New C library & compiler
  7.  * More     28-Aug-82 Bob Denny -- Reference "a" to shut up compiler
  8.  * More        20-Nov-83 Scott Guthery -- Adapted for IBM PC & DeSmet C
  9.  */
  10.  
  11. /*
  12.  * lex -- find and set base values for `move' vector
  13.  */
  14. #include <stdio.h>
  15. #include "lexlex.h"
  16.  
  17. extern struct set *chase();
  18.  
  19. /*
  20.  * Choose the best default state for `st'.
  21.  * Only states previous to the current state are considered,
  22.  * as these are guaranteed to exist.
  23.  */
  24. struct dfa *
  25. defalt(st, xsep)
  26. struct dfa *st;
  27. struct xset **xsep;
  28. {
  29.         register struct dfa *dp;
  30.         register unsigned minv, u;
  31.         struct dfa *def;
  32.         struct xset *xse;
  33.         int i;
  34.  
  35.         xse = *xsep;
  36.         if ((i = xse-sets)==0)
  37.                 return(NULL);
  38. #ifdef DEBUG
  39.         if (lldebug>1)
  40.                 fprintf(stderr, "State %d, default:\n", st-dfa);
  41. #endif
  42.         minv = -1;
  43.         def = NULL;
  44.         for (dp = dfa; dp < st; dp++) {
  45.                 u = compat(st, dp, xse);
  46. #ifdef DEBUG
  47.                 if (lldebug > 1)
  48.                         fprintf(stderr, "\t%d rates %d\n", dp-dfa, u);
  49. #endif
  50.                 if (u < minv) {
  51.                         def = dp;
  52.                         minv = u;
  53.                 }
  54.         }
  55.         if (minv == -1 || 10*(i-(int)minv) < i)
  56.                 def = NULL;
  57. #ifdef DEBUG
  58.         if (lldebug>1 && def)
  59.                 fprintf(stderr, "\t%d chosen\n", def-dfa);
  60. #endif
  61.         if (def)
  62.                 resolve(st, def, xsep);
  63.         return(def);
  64. }
  65.  
  66. /*
  67.  * State `b' is compatible with, and hence a suitable default state
  68.  * for state `a', if its transitions agree with
  69.  * those of `a', except those for which `a' has transitions to the
  70.  * (alleged) default. Circularity of the default
  71.  * relation is also not allowed. If the state `b' has at least
  72.  * twice as many transitions as `a', it is not even worth considering.
  73.  */
  74. compat(a, b, xse)
  75. struct dfa *a, *b;
  76. struct xset *xse;
  77. {
  78.         register struct dfa *dp;
  79.         struct xset *xs;
  80.         register nt;
  81.  
  82.         if (a==b || b->df_ntrans >= a->df_ntrans*2)
  83.                 return(-1);
  84.         for (dp = b; dp; dp = dp->df_default)
  85.                 if (dp == a)
  86.                         return(-1);
  87.         nt = b->df_ntrans + a->df_ntrans;
  88.         for (xs = sets; xs < xse; xs++)
  89.                 if (chase(b, xs->x_char) == xs->x_set)
  90.                         nt -= 2;
  91.         return(nt);
  92. }
  93.  
  94. struct set *
  95. chase(st, c)
  96. register struct dfa *st;
  97. register int c;
  98. {
  99.         register struct move *dp;
  100.  
  101.         c &= 0377;
  102.         while ((dp = st->df_base) != NULL &&
  103.                ((dp += c) >= st->df_max || dp->m_check != st))
  104.                 if ((st = st->df_default) == NULL)
  105.                         return(NULL);
  106.         if (dp)
  107.                 dp = dp->m_next;
  108.         return(dp);
  109. }
  110.  
  111. /*
  112.  * set `sets' to indicate those characters on which the state `a'
  113.  * and its default agree and those characters on which `a'
  114.  * should go to `error' (as the default accepts it, but `a' does not).
  115.  */
  116. resolve(a, def, xsep)
  117. struct dfa *a, *def;
  118. struct xset **xsep;
  119. {
  120.         register struct move *dp;
  121.         register int c, i;
  122.         struct xset *xs, *xse;
  123.  
  124.         a = a;                          /* Quiet compiler the easy way */
  125.  
  126.         xse = *xsep;
  127.         i = xse-sets;
  128.         for (xs = sets; xs < xse; xs++)
  129.                 xs->x_defsame = 0;
  130.         for (; def; def = def->df_default)
  131.         for (dp = def->df_base; dp < def->df_max; dp++)
  132.                 if (dp->m_check == def) {
  133.                         c = dp - def->df_base;
  134.                         for (xs = sets; xs < xse; xs++)
  135.                                 if (c==(xs->x_char&0377)) {
  136.                                         if (xs->x_set==dp->m_next) {
  137.                                                 xs->x_defsame++;
  138.                                                 i--;
  139.                                         }
  140.                                         break;
  141.                                 }
  142.                         if (xs >= xse) {
  143.                                 xs->x_defsame = 0;
  144.                                 xs->x_char = c;
  145.                                 xs->x_set = NULL;
  146.                                 i++;
  147.                                 xse++;
  148.                         }
  149.                 }
  150.         *xsep = xse;
  151.         return(i);
  152. }
  153.  
  154. /*
  155.  * Choose a base in `move' for the current state.
  156.  * The transitions of that state are in the vector `sets'.
  157.  */
  158. struct move *
  159. stbase(xse)
  160. struct xset *xse;
  161. {
  162.         register int a;
  163.         register struct move *base;
  164.         register int conflicts;
  165.         struct xset *xs;
  166.  
  167.         if (xse==sets)
  168.                 return(NULL);
  169.         base = move;
  170.         do {
  171.                 if (base-move >= NNEXT) {
  172.                         error("No space in `move' (stbase)");
  173. #ifdef DEBUG
  174.                         if (lldebug>1)
  175.                                 dfaprint();
  176. #endif
  177.                         exit(1);
  178.                 }
  179.                 conflicts = 0;
  180.                 for (xs = sets; xs < xse; xs++) {
  181.                         a = xs->x_char&0377;
  182.                         if (xs->x_defsame==0 &&
  183.                             (base+a>=move+NNEXT || base[a].m_check!=NULL)) {
  184.                                 conflicts++;
  185.                                 base++;
  186.                                 break;
  187.                         }
  188.                 }
  189.         } while (conflicts);
  190.         return(base);
  191. }
  192.  
  193. /*
  194.  * Given a state, its `base' value in `move',
  195.  * and the set of transitions in `sets' (ending near `xse'),
  196.  * set the `move' values.
  197.  */
  198. setbase(st, base, xse)
  199. struct dfa *st;
  200. register struct move *base;
  201. struct xset *xse;
  202. {
  203.         register struct move *dp;
  204.         register struct xset *xs;
  205.         struct move *maxdp;
  206.  
  207.         st->df_base = base;
  208.         st->df_max = base;
  209. #ifdef DEBUG
  210.         if (lldebug>1)
  211.                 fprintf(stderr, "Setbase: state %d\n", st-dfa);
  212.         if (lldebug>1 && base==0)
  213.                 fprintf(stderr, "\tno base\n");
  214. #endif
  215.         if (base==NULL)
  216.                 return;
  217.         maxdp = base;
  218.         for (xs = sets; xs < xse; xs++)
  219.                 if (xs->x_defsame==0) {
  220.                         dp = base + ((unsigned int)xs->x_char & 0377);
  221.                         if (dp > maxdp)
  222.                                 maxdp = dp;
  223.                         dp->m_next = xs->x_set;
  224.                         dp->m_check = st;
  225.                         if (dp-move > llnxtmax)
  226.                                 llnxtmax = dp-move;
  227. #ifdef DEBUG
  228.                         if (lldebug>1)
  229.                         fprintf(stderr, "\t%c nets %d\n",
  230.                                 xs->x_char&0377, dp-move);
  231. #endif
  232.                 }
  233.         st->df_max = maxdp+1;
  234. }
  235.