home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / OS2_LEX.ZIP / BASE.C next >
C/C++ Source or Header  |  1989-10-07  |  7KB  |  224 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 <stdlib.h>
  15. #include <stdio.h>
  16. #include "lexlex.h"
  17. #include "lextern.h"
  18.  
  19. struct set *chase(struct dfa *, int);
  20. compat(struct dfa *, struct dfa *, struct xset *);
  21. int resolve(struct dfa *, struct dfa *, struct xset **);
  22.  
  23. /*
  24.  * Choose the best default state for `st'.
  25.  * Only states previous to the current state are considered,
  26.  * as these are guaranteed to exist.
  27.  */
  28. struct dfa *defalt(struct dfa *st, struct xset **xsep)
  29. {
  30.         register struct dfa *dp;
  31.         register unsigned minv, u;
  32.         struct dfa *def;
  33.         struct xset *xse;
  34.         int i;
  35.  
  36.         xse = *xsep;
  37.         if ((i = xse-sets)==0)
  38.                 return(NULL);
  39. #ifdef DEBUG
  40.         if (lldebug>1)
  41.                 fprintf(stderr, "State %d, default:\n", st-dfa);
  42. #endif
  43.         minv = -1;
  44.         def = NULL;
  45.         for (dp = dfa; dp < st; dp++) {
  46.                 u = compat(st, dp, xse);
  47. #ifdef DEBUG
  48.                 if (lldebug > 1)
  49.                         fprintf(stderr, "\t%d rates %d\n", dp-dfa, u);
  50. #endif
  51.                 if (u < minv) {
  52.                         def = dp;
  53.                         minv = u;
  54.                 }
  55.         }
  56.         if (minv == -1 || 10*(i-(int)minv) < i)
  57.                 def = NULL;
  58. #ifdef DEBUG
  59.         if (lldebug>1 && def)
  60.                 fprintf(stderr, "\t%d chosen\n", def-dfa);
  61. #endif
  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(struct dfa *a, struct dfa *b, struct xset *xse)
  76. {
  77.         register struct dfa *dp;
  78.         struct xset *xs;
  79.         register nt;
  80.  
  81.         if (a==b || b->df_ntrans >= a->df_ntrans*2)
  82.                 return(-1);
  83.         for (dp = b; dp; dp = dp->df_default)
  84.                 if (dp == a)
  85.                         return(-1);
  86.         nt = b->df_ntrans + a->df_ntrans;
  87.         for (xs = sets; xs < xse; xs++)
  88.                 if (chase(b, xs->x_char) == xs->x_set)
  89.                         nt -= 2;
  90.         return(nt);
  91. }
  92.  
  93. struct set *chase(struct dfa *st, int c)
  94. {
  95.         register struct move *dp;
  96.  
  97.         c &= 0377;
  98.         while ((dp = st->df_base) != NULL &&
  99.                ((dp += c) >= st->df_max || dp->m_check != st))
  100.                 if ((st = st->df_default) == NULL)
  101.                         return(NULL);
  102.         if (dp)
  103.                 dp = dp->m_next;
  104.         return((struct set *)dp);
  105. }
  106.  
  107. /*
  108.  * set `sets' to indicate those characters on which the state `a'
  109.  * and its default agree and those characters on which `a'
  110.  * should go to `error' (as the default accepts it, but `a' does not).
  111.  */
  112. int resolve(struct dfa *a, struct dfa *def, struct xset **xsep)
  113. {
  114.         register struct move *dp;
  115.         register c, i;
  116.         struct xset *xs, *xse;
  117.  
  118.         a = a;                          /* Quiet compiler the easy way */
  119.  
  120.         xse = *xsep;
  121.         i = xse-sets;
  122.         for (xs = sets; xs < xse; xs++)
  123.                 xs->x_defsame = 0;
  124.         for (; def; def = def->df_default)
  125.         for (dp = def->df_base; dp < def->df_max; dp++)
  126.                 if (dp->m_check == def) {
  127.                         c = dp - def->df_base;
  128.                         for (xs = sets; xs < xse; xs++)
  129.                                 if (c==(xs->x_char&0377)) {
  130.                                         if (xs->x_set==dp->m_next) {
  131.                                                 xs->x_defsame++;
  132.                                                 i--;
  133.                                         }
  134.                                         break;
  135.                                 }
  136.                         if (xs >= xse) {
  137.                                 xs->x_defsame = 0;
  138.                                 xs->x_char = c;
  139.                                 xs->x_set = NULL;
  140.                                 i++;
  141.                                 xse++;
  142.                         }
  143.                 }
  144.         *xsep = xse;
  145.         return(i);
  146. }
  147.  
  148. /*
  149.  * Choose a base in `move' for the current state.
  150.  * The transitions of that state are in the vector `sets'.
  151.  */
  152. struct move *stbase(struct xset *xse)
  153. {
  154.         register a;
  155.         register struct move *base;
  156.         register conflicts;
  157.         struct xset *xs;
  158.  
  159.         if (xse==sets)
  160.                 return(NULL);
  161.         base = move;
  162.         do {
  163.                 if (base-move >= NNEXT) {
  164.                         error("No space in `move' (stbase)");
  165. #ifdef DEBUG
  166.                         if (lldebug>1)
  167.                                 dfaprint();
  168. #endif
  169.                         exit(1);
  170.                 }
  171.                 conflicts = 0;
  172.                 for (xs = sets; xs < xse; xs++) {
  173.                         a = xs->x_char&0377;
  174.                         if (xs->x_defsame==0 &&
  175.                             (base+a>=move+NNEXT || base[a].m_check!=NULL)) {
  176.                                 conflicts++;
  177.                                 base++;
  178.                                 break;
  179.                         }
  180.                 }
  181.         } while (conflicts);
  182.         return(base);
  183. }
  184.  
  185. /*
  186.  * Given a state, its `base' value in `move',
  187.  * and the set of transitions in `sets' (ending near `xse'),
  188.  * set the `move' values.
  189.  */
  190. void setbase(struct dfa *st, struct move *base, struct xset *xse)
  191. {
  192.         register struct move *dp;
  193.         register struct xset *xs;
  194.         struct move *maxdp;
  195.  
  196.         st->df_base = base;
  197.         st->df_max = base;
  198. #ifdef DEBUG
  199.         if (lldebug>1)
  200.                 fprintf(stderr, "Setbase: state %d\n", st-dfa);
  201.         if (lldebug>1 && base==0)
  202.                 fprintf(stderr, "\tno base\n");
  203. #endif
  204.         if (base==NULL)
  205.                 return;
  206.         maxdp = base;
  207.         for (xs = sets; xs < xse; xs++)
  208.                 if (xs->x_defsame==0) {
  209.                         dp = base + (int)xs->x_char;
  210.                         if (dp > maxdp)
  211.                                 maxdp = dp;
  212.                         dp->m_next = xs->x_set;
  213.                         dp->m_check = st;
  214.                         if (dp-move > llnxtmax)
  215.                                 llnxtmax = dp-move;
  216. #ifdef DEBUG
  217.                         if (lldebug>1)
  218.                         fprintf(stderr, "\t%c nets %d\n",
  219.                                 xs->x_char&0377, dp-move);
  220. #endif
  221.                 }
  222.         st->df_max = maxdp+1;
  223. }
  224.