home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / c / lex.arc / MIN.C < prev    next >
Text File  |  1986-03-10  |  5KB  |  179 lines
  1. /*
  2.  * Copyright (c) 1978 Charles H. Forsyth
  3.  *
  4.  * Modified 02-Dec-80 Bob Denny -- Conditionalize debug code for smaller size
  5.  *  Also note other mods. Now minimization is turned on at run time by '-m'.
  6.  * More     19-Mar-82 Bob Denny -- New C library & compiler
  7.  *  This routine is unimplemented. Define MIN to turn it on. Have fun.
  8.  */
  9.  
  10. /*
  11.  * lex -- dfa minimisation routines
  12.  */
  13.  
  14. #include <stdio.h>
  15. #include "lexlex.h"
  16.  
  17. #ifdef  MIN
  18. #else
  19. /*
  20.  * Dummy routine
  21.  */
  22. dfamin()
  23. {
  24. }
  25. #endif
  26.  
  27. #ifdef  MIN
  28.  
  29. member(e, v, i)
  30. register int e, *v, i;
  31. {
  32.  
  33.         while (i--)
  34.                 if (e==*v++)
  35.                         return(1);
  36.         return(0);
  37. }
  38.  
  39. extern struct set **oldpart;
  40. extern int **newpart;
  41. extern int nold, nnew;
  42.  
  43. struct  xlist {
  44.         struct  set     *x_set;
  45.         struct  trans   *x_trans;
  46.               };
  47.  
  48. xcomp(a, b)
  49. struct xlist *a, *b;
  50. {
  51.         if (a->x_trans > b->x_trans)
  52.                 return(1);
  53.         if (a->x_trans==b->x_trans)
  54.                 return(0);
  55.         return(-1);
  56. }
  57.  
  58. dfamin()
  59. {
  60.         struct xlist *temp, *tp, *xp, *zp;
  61.         struct trans *trp;
  62.         int *tp2, *ip;
  63.         struct set *gp, **xch;
  64.         int i, j, k, niter;
  65.  
  66.         if(mflag == 0) return;          /*** NOTE ***/
  67.  
  68. #ifdef DEBUG
  69.         fprintf(lexlog, "\nDFA minimisation (%d states)\n", ndfa);
  70. #endif
  71.  
  72.         temp = lalloc(ndfa, sizeof(*temp), "minimisation");
  73.         oldpart = lalloc(ndfa, sizeof(*oldpart), "minimisation");
  74.         newpart = lalloc(ndfa*2+1, sizeof(*newpart), "minimisation");
  75.         setlist = 0;
  76. /*
  77.  * partition first into final
  78.  * states which identify different
  79.  * translations, and non-final
  80.  * states.
  81.  */
  82.         tp = temp;
  83.         for (i = 0; i < ndfa; i++, tp++) {
  84.                 tp->x_set = dfa[i].df_name;
  85.                 if (tp->x_set->s_final)
  86.                         tp->x_trans = nfa[tp->x_set->s_final].n_trans; else
  87.                         tp->x_trans = 0;
  88.         }
  89.         qsort(temp, tp-temp, sizeof(*tp), xcomp);
  90.         for (xp = temp; xp < tp; xp = zp) {
  91.                 ip = newpart;
  92.                 for (zp = xp; zp < tp && zp->x_trans==xp->x_trans; zp++)
  93.                         *ip++ = zp->x_set->s_state-dfa;
  94.                 oldpart[nold++] = newset(newpart, ip-newpart, 0);
  95.         }
  96.         free(temp);
  97. /*
  98.  * create a new partition,
  99.  * by considering each group in
  100.  * the old partition.  For each
  101.  * such group, create new subgroups
  102.  * such that two states are in the
  103.  * same subgroup iff they have
  104.  * transitions on the same set of
  105.  * characters into the same
  106.  * set of groups in the old partition.
  107.  * repeat this process until
  108.  * a fixed point is reached.
  109.  */
  110.         niter = 0;
  111.         do {
  112.                 niter++;
  113.  
  114. #ifdef DEBUG
  115.                 fprintf(lexlog, "\n%d groups in partition %d\n", nold, niter);
  116. #endif
  117.  
  118.                 for (i = 0; i < nold; i++) {
  119.                         fprintf(lexlog, "group %d: ", i);
  120.                         pset(oldpart[i], 0);
  121.                         fprintf(lexlog, "\n");
  122.                 }
  123.                 nnew = 0;
  124.                 tp2 = newpart;
  125.                 for (i = 0; i < nold; i++) {
  126.                         gp = oldpart[i];
  127.                         for (j = 0; j < gp->s_len; j++) {
  128.                                 if (member(gp->s_els[j], newpart, tp2-newpart))
  129.                                         continue;
  130.                                 *tp2++ = gp->s_els[j];
  131.                                 for (k = 0; k < gp->s_len; k++)
  132.                                         if (k!=j &&
  133.                                             !member(gp->s_els[k], newpart,
  134.                                                 tp2-newpart) &&
  135.                                             eqstate(gp->s_els[j],gp->s_els[k]))
  136.                                                 *tp2++ = gp->s_els[k];
  137.                                 *tp2++ = -1;
  138.                         }
  139.                 }
  140.                 *tp2++ = -1;
  141.                 for (tp2 = newpart; *tp2 != -1; tp2 = ++ip) {
  142.                         for (ip = tp2; *ip != -1; ip++)
  143.                                 ;
  144.                         oldpart[nnew++] = newset(tp2, ip-tp2, 0);
  145.                 }
  146.                 i = nold; nold = nnew; nnew = i;
  147.         } while (nnew!=nold);
  148.  
  149. #ifdef DEBUG
  150.         if (ndfa==nnew)
  151.                 fprintf(lexlog, "\nno states saved by minimisation\n"); else
  152.                 fprintf(lexlog, "\n%d states saved by minimisation\n", ndfa-nnew);
  153. #endif
  154.  
  155.         free(newpart);
  156.         free(oldpart);
  157. }
  158.  
  159. eqstate(a, b)
  160. {
  161.         register struct move *dp1, *dp2;
  162.  
  163. /**  dfa vector has no element 'df_moves', transition entries have no elements
  164.         df_char nor df_set. Obviously unimplemented stuff.
  165.  
  166.         dp1 = dfa[a].df_moves;
  167.         dp2 = dfa[b].df_moves;
  168.         for (; dp1->df_set; dp1++, dp2++)
  169.                 if (dp2->df_set==0)
  170.                         return(0);
  171.                 else if (dp1->df_char != dp2->df_char ||
  172.                          dp1->df_set->s_group != dp2->df_set->s_group)
  173.                         return(0);
  174.         return(dp2->df_set==0);
  175. **/
  176.  
  177. }
  178. #endif
  179.