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 / min.c < prev    next >
Encoding:
C/C++ Source or Header  |  1980-01-01  |  5.1 KB  |  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 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.  
  64.         struct set *gp, **xch;
  65.         int i, j, k, niter;
  66.  
  67.         if(mflag == 0) return;          /*** NOTE ***/
  68.  
  69. #ifdef DEBUG
  70.         fprintf(lexlog, "\nDFA minimisation (%d states)\n", ndfa);
  71. #endif
  72.  
  73.         temp = lalloc(ndfa, sizeof(*temp), "minimisation");
  74.         oldpart = lalloc(ndfa, sizeof(*oldpart), "minimisation");
  75.         newpart = lalloc(ndfa*2+1, sizeof(*newpart), "minimisation");
  76.         setlist = 0;
  77. /*
  78.  * partition first into final
  79.  * states which identify different
  80.  * translations, and non-final
  81.  * states.
  82.  */
  83.         tp = temp;
  84.         for (i = 0; i < ndfa; i++, tp++) {
  85.                 tp->x_set = dfa[i].df_name;
  86.                 if (tp->x_set->s_final)
  87.                         tp->x_trans = nfa[tp->x_set->s_final].n_trans; else
  88.                         tp->x_trans = 0;
  89.         }
  90.         qsort(temp, tp-temp, sizeof(*tp), xcomp);
  91.         for (xp = temp; xp < tp; xp = zp) {
  92.                 ip = newpart;
  93.                 for (zp = xp; zp < tp && zp->x_trans==xp->x_trans; zp++)
  94.                         *ip++ = zp->x_set->s_state-dfa;
  95.                 oldpart[nold++] = newset(newpart, ip-newpart, 0);
  96.         }
  97.         free(temp);
  98. /*
  99.  * create a new partition,
  100.  * by considering each group in
  101.  * the old partition.  For each
  102.  * such group, create new subgroups
  103.  * such that two states are in the
  104.  * same subgroup iff they have
  105.  * transitions on the same set of
  106.  * characters into the same
  107.  * set of groups in the old partition.
  108.  * repeat this process until
  109.  * a fixed point is reached.
  110.  */
  111.         niter = 0;
  112.         do {
  113.                 niter++;
  114.  
  115. #ifdef DEBUG
  116.                 fprintf(lexlog, "\n%d groups in partition %d\n", nold, niter);
  117. #endif
  118.  
  119.                 for (i = 0; i < nold; i++) {
  120.                         fprintf(lexlog, "group %d: ", i);
  121.                         pset(oldpart[i], 0);
  122.                         fprintf(lexlog, "\n");
  123.                 }
  124.                 nnew = 0;
  125.                 tp2 = newpart;
  126.  
  127.                 for (i = 0; i < nold; i++) {
  128.                         gp = oldpart[i];
  129.                         for (j = 0; j < gp->s_len; j++) {
  130.                                 if (member(gp->s_els[j], newpart, tp2-newpart))
  131.                                         continue;
  132.                                 *tp2++ = gp->s_els[j];
  133.                                 for (k = 0; k < gp->s_len; k++)
  134.                                         if (k!=j &&
  135.                                             !member(gp->s_els[k], newpart,
  136.                                                 tp2-newpart) &&
  137.                                             eqstate(gp->s_els[j],gp->s_els[k]))
  138.                                                 *tp2++ = gp->s_els[k];
  139.                                 *tp2++ = -1;
  140.                         }
  141.                 }
  142.                 *tp2++ = -1;
  143.                 for (tp2 = newpart; *tp2 != -1; tp2 = ++ip) {
  144.                         for (ip = tp2; *ip != -1; ip++)
  145.                                 ;
  146.                         oldpart[nnew++] = newset(tp2, ip-tp2, 0);
  147.                 }
  148.                 i = nold; nold = nnew; nnew = i;
  149.         } while (nnew!=nold);
  150.  
  151. #ifdef DEBUG
  152.         if (ndfa==nnew)
  153.                 fprintf(lexlog, "\nno states saved by minimisation\n"); else
  154.                 fprintf(lexlog, "\n%d states saved by minimisation\n", ndfa-nnew);
  155. #endif
  156.  
  157.         free(newpart);
  158.         free(oldpart);
  159. }
  160.  
  161. eqstate(a, b)
  162. {
  163.         register struct move *dp1, *dp2;
  164.  
  165. /**  dfa vector has no element 'df_moves', transition entries have no elements
  166.         df_char nor df_set. Obviously unimplemented stuff.
  167.  
  168.         dp1 = dfa[a].df_moves;
  169.         dp2 = dfa[b].df_moves;
  170.         for (; dp1->df_set; dp1++, dp2++)
  171.                 if (dp2->df_set==0)
  172.                         return(0);
  173.                 else if (dp1->df_char != dp2->df_char ||
  174.                          dp1->df_set->s_group != dp2->df_set->s_group)
  175.                         return(0);
  176.         return(dp2->df_set==0);
  177. **/
  178.  
  179. }
  180. #endif
  181.