home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource3 / 172_01 / min.c < prev    next >
Text File  |  1979-12-31  |  3KB  |  129 lines
  1. /*
  2.   HEADER:              CUG  nnn.nn;
  3.   TITLE:               LEX - A Lexical Analyser Generator
  4.   VERSION:             1.1 for IBM-PC
  5.   DATE:                Jan 30, 1985
  6.   DESCRIPTION:         A Lexical Analyser Generator. From UNIX
  7.   KEYWORDS:            Lexical Analyser Generator YACC C PREP
  8.   SYSTEM:              IBM-PC and Compatiables
  9.   FILENAME:            MIN.C
  10.   WARNINGS:            This program is not for the casual user. It will
  11.                        be useful primarily to expert developers.
  12.   CRC:                 N/A
  13.   SEE-ALSO:            YACC and PREP
  14.   AUTHORS:             Charles H. Forsyth
  15.                        Scott Guthery 11100 leafwood lane Austin, TX 78750
  16.                        Andrew M. Ward, Jr.  Houston, Texas (Modifications)
  17.   COMPILERS:           LATTICE C
  18.   REFERENCES:          UNIX Systems Manuals -- Lex Manual on distribution disks
  19. */
  20. /*
  21.  * Copyright (c) 1978 Charles H. Forsyth
  22.  *
  23.  */
  24.  
  25. /*
  26.  * lex -- dfa minimisation routines
  27.  */
  28.  
  29. #include <stdio.h>
  30. #include "lexlex.h"
  31.  
  32. #ifdef  MIN
  33. #else
  34. /*
  35.  * Dummy routine
  36.  */
  37. dfamin()
  38. {
  39. }
  40. #endif
  41.  
  42. #ifdef  MIN
  43.  
  44. member(e, v, i)
  45. int e, *v, i;
  46. {
  47.  
  48.     while (i--)
  49.         if (e==*v++)
  50.             return(1);
  51.     return(0);
  52. }
  53.  
  54. extern struct set **oldpart;
  55. extern int **newpart;
  56. extern int nold, nnew;
  57.  
  58. struct  xlist {
  59.     struct  set     *x_set;
  60.     struct  trans   *x_trans;
  61.           };
  62.  
  63. xcomp(a, b)
  64. struct xlist *a, *b;
  65. {
  66.     if (a->x_trans > b->x_trans)
  67.         return(1);
  68.     if (a->x_trans==b->x_trans)
  69.         return(0);
  70.     return(-1);
  71. }
  72.  
  73. dfamin()
  74. {
  75.     struct xlist *temp, *tp, *xp, *zp;
  76.     struct trans *trp;
  77.     int *tp2, *ip;
  78.  
  79.     struct set *gp, **xch;
  80.     int i, j, k, niter;
  81.  
  82.     if(mflag == 0) return;          /*** NOTE ***/
  83.  
  84.     temp = lalloc(ndfa, sizeof(*temp), "minimisation");
  85.     oldpart = lalloc(ndfa, sizeof(*oldpart), "minimisation");
  86.     newpart = lalloc(ndfa*2+1, sizeof(*newpart), "minimisation");
  87.     setlist = 0;
  88. /*
  89.  * partition first into final
  90.  * states which identify different
  91.  * translations, and non-final
  92.  * states.
  93.  */
  94.     tp = temp;
  95.     for (i = 0; i < ndfa; i++, tp++) {
  96.         tp->x_set = dfa[i].df_name;
  97.         if (tp->x_set->s_final)
  98.             tp->x_trans = nfa[tp->x_set->s_final].n_trans;
  99.         else
  100.             tp->x_trans = 0;
  101.     }
  102.     qsort(temp, tp-temp, sizeof(*tp), xcomp);
  103.     for (xp = temp; xp < tp; xp = zp) {
  104.         ip = newpart;
  105.         for (zp = xp; zp < tp && zp->x_trans==xp->x_trans; zp++)
  106.             *ip++ = zp->x_set->s_state-d&a;
  107.     }
  108. }
  109.  
  110. q_tex(i, j, k)
  111. char *i, *j, *k;
  112. {
  113.     char *ri, *rj, *rk;
  114.     int c;
  115.     int n;
  116.  
  117.     n = size;
  118.     ri = i;
  119.     rj = j;
  120.     rk = k;
  121.     do {
  122.         c = *ri;
  123.         *ri++ = *rk;
  124.         *rk++ = *rj;
  125.         *rj++ = c;
  126.     } while(--n);
  127. }
  128. #endif
  129.