home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / alde_c / misc / util / lex / base.c < prev    next >
Encoding:
C/C++ Source or Header  |  1980-01-01  |  6.9 KB  |  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.  
  62.         if (def)
  63.                 resolve(st, def, xsep);
  64.         return(def);
  65. }
  66.  
  67. /*
  68.  * State `b' is compatible with, and hence a suitable default state
  69.  * for state `a', if its transitions agree with
  70.  * those of `a', except those for which `a' has transitions to the
  71.  * (alleged) default. Circularity of the default
  72.  * relation is also not allowed. If the state `b' has at least
  73.  * twice as many transitions as `a', it is not even worth considering.
  74.  */
  75. compat(a, b, xse)
  76. struct dfa *a, *b;
  77. struct xset *xse;
  78. {
  79.         register struct dfa *dp;
  80.         struct xset *xs;
  81.         register nt;
  82.  
  83.         if (a==b || b->df_ntrans >= a->df_ntrans*2)
  84.                 return(-1);
  85.         for (dp = b; dp; dp = dp->df_default)
  86.                 if (dp == a)
  87.                         return(-1);
  88.         nt = b->df_ntrans + a->df_ntrans;
  89.         for (xs = sets; xs < xse; xs++)
  90.                 if (chase(b, xs->x_char) == xs->x_set)
  91.                         nt -= 2;
  92.         return(nt);
  93. }
  94.  
  95. struct set *
  96. chase(st, c)
  97. register struct dfa *st;
  98. register c;
  99. {
  100.         register struct move *dp;
  101.  
  102.         c &= 0377;
  103.         while ((dp = st->df_base) != NULL &&
  104.                ((dp += c) >= st->df_max || dp->m_check != st))
  105.                 if ((st = st->df_default) == NULL)
  106.                         return(NULL);
  107.         if (dp)
  108.                 dp = dp->m_next;
  109.         return(dp);
  110. }
  111.  
  112. /*
  113.  * set `sets' to indicate those characters on which the state `a'
  114.  * and its default agree and those characters on which `a'
  115.  * should go to `error' (as the default accepts it, but `a' does not).
  116.  */
  117. resolve(a, def, xsep)
  118. struct dfa *a, *def;
  119. struct xset **xsep;
  120. {
  121.         register struct move *dp;
  122.         register c, i;
  123.         struct xset *xs, *xse;
  124.  
  125.         a = a;                          /* Quiet compiler the easy way */
  126.  
  127.         xse = *xsep;
  128.         i = xse-sets;
  129.         for (xs = sets; xs < xse; xs++)
  130.                 xs->x_defsame = 0;
  131.         for (; def; def = def->df_default)
  132.         for (dp = def->df_base; dp < def->df_max; dp++)
  133.                 if (dp->m_check == def) {
  134.                         c = dp - def->df_base;
  135.                         for (xs = sets; xs < xse; xs++)
  136.                                 if (c==(xs->x_char&0377)) {
  137.                                         if (xs->x_set==dp->m_next) {
  138.                                                 xs->x_defsame++;
  139.                                                 i--;
  140.                                         }
  141.                                         break;
  142.                                 }
  143.                         if (xs >= xse) {
  144.                                 xs->x_defsame = 0;
  145.                                 xs->x_char = c;
  146.                                 xs->x_set = NULL;
  147.                                 i++;
  148.                                 xse++;
  149.                         }
  150.                 }
  151.         *xsep = xse;
  152.         return(i);
  153. }
  154.  
  155. /*
  156.  * Choose a base in `move' for the current state.
  157.  * The transitions of that state are in the vector `sets'.
  158.  */
  159. struct move *
  160. stbase(xse)
  161. struct xset *xse;
  162. {
  163.         register a;
  164.         register struct move *base;
  165.         register conflicts;
  166.         struct xset *xs;
  167.  
  168.         if (xse==sets)
  169.                 return(NULL);
  170.         base = move;
  171.         do {
  172.                 if (base-move >= NNEXT) {
  173.                         error("No space in `move' (stbase)");
  174.  
  175. #ifdef DEBUG
  176.                         if (lldebug>1)
  177.                                 dfaprint();
  178. #endif
  179.                         exit(1);
  180.                 }
  181.                 conflicts = 0;
  182.                 for (xs = sets; xs < xse; xs++) {
  183.                         a = xs->x_char&0377;
  184.                         if (xs->x_defsame==0 &&
  185.                             (base+a>=move+NNEXT || base[a].m_check!=NULL)) {
  186.                                 conflicts++;
  187.                                 base++;
  188.                                 break;
  189.                         }
  190.                 }
  191.         } while (conflicts);
  192.         return(base);
  193. }
  194.  
  195. /*
  196.  * Given a state, its `base' value in `move',
  197.  * and the set of transitions in `sets' (ending near `xse'),
  198.  * set the `move' values.
  199.  */
  200. setbase(st, base, xse)
  201. struct dfa *st;
  202. register struct move *base;
  203. struct xset *xse;
  204. {
  205.         register struct move *dp;
  206.         register struct xset *xs;
  207.         struct move *maxdp;
  208.  
  209.         st->df_base = base;
  210.         st->df_max = base;
  211. #ifdef DEBUG
  212.         if (lldebug>1)
  213.                 fprintf(stderr, "Setbase: state %d\n", st-dfa);
  214.         if (lldebug>1 && base==0)
  215.                 fprintf(stderr, "\tno base\n");
  216. #endif
  217.         if (base==NULL)
  218.                 return;
  219.         maxdp = base;
  220.         for (xs = sets; xs < xse; xs++)
  221.                 if (xs->x_defsame==0) {
  222.                         dp = base + (int)xs->x_char;
  223.                         if (dp > maxdp)
  224.                                 maxdp = dp;
  225.                         dp->m_next = xs->x_set;
  226.                         dp->m_check = st;
  227.                         if (dp-move > llnxtmax)
  228.                                 llnxtmax = dp-move;
  229. #ifdef DEBUG
  230.                         if (lldebug>1)
  231.                         fprintf(stderr, "\t%c nets %d\n",
  232.                                 xs->x_char&0377, dp-move);
  233. #endif
  234.                 }
  235.  
  236.         st->df_max = maxdp+1;
  237. }
  238.