home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 172_01 / base.c < prev    next >
Text File  |  1979-12-31  |  8KB  |  262 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:            BASE.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.  * More     20-Nov-83 Scott Guthery -- Adapt for IBM PC & DeSmet C
  24.  *
  25.  * Modified 22-Jun-86 Andrew Ward -- Modified code to compile under Lattice C
  26.  *                                 version 3.0h.  Corrected several errors
  27.  *                                 from the assumption that pointers and
  28.  *                                 integers are the same size.     
  29.  *                                 New debug code for LATTICE C using assert
  30.  *                                 to test for wild pointers.
  31.  */
  32.  
  33. /*
  34.  * lex -- find and set base values for `move' vector
  35.  */
  36. #include <stdio.h>
  37. #include "lexlex.h"
  38.  
  39. extern struct set *chase(struct dfa *, int);
  40. extern int resolve(struct dfa *, struct dfa *, struct xset **);
  41. extern struct move *stbase(struct xset *);
  42. extern void setbase(struct dfa *, struct move *, struct xset *);
  43.  
  44. /*
  45.  * Choose the best default state for `st'.
  46.  * Only states previous to the current state are considered,
  47.  * as these are guaranteed to exist.
  48.  */
  49.  
  50. struct dfa *defalt(st, xsep)
  51. struct dfa *st;
  52. struct xset **xsep;
  53. {
  54.         struct   dfa *dp;
  55.         int  minv, u; /* AMW: was unsigned */
  56.         struct   dfa *def;
  57.         struct   xset *xse;
  58.         int i;
  59.  
  60.         xse = *xsep;
  61.         i = xse - sets;
  62.         if( i == 0 )   return(NULL);
  63.  
  64. #ifdef DEBUG
  65.         fprintf(stdout, "State %d, Default: \n", st - dfa );
  66. #endif
  67.         minv = -1;
  68.         def = NULL;
  69.         for(dp = dfa; dp < st; dp++) {
  70.                 u = compat(st, dp, xse);
  71. #ifdef DEBUG
  72.         fprintf( stdout, "\nDEFAULT: In Loop 1 \n");
  73.         fprintf( stdout, "\t%d rates %d\n", dp - dfa, u );
  74. #endif
  75.                 if(u < minv) {
  76.                         def = dp;
  77.                         minv = u;
  78.                 }
  79.         }
  80.         if( minv == -1 || 10*(i-(int)minv) < i)
  81.                 def = NULL;
  82. #ifdef DEBUG
  83.         if(def != NULL) fprintf( stdout, "\t%d chosen\n", def - dfa);
  84.         else fprintf( stdout, "\n def - dfa = %d, will resolve", def - dfa );
  85. #endif
  86.  
  87.         if(def)
  88.                 resolve(st, def, xsep);
  89.         return(def);
  90. }
  91.  
  92. /*
  93.  * State `b' is compatible with, and hence a suitable default state
  94.  * for state `a', if its transitions agree with
  95.  * those of `a', except those for which `a' has transitions to the
  96.  * (alleged) default. Circularity of the default
  97.  * relation is also not allowed. If the state `b' has at least
  98.  * twice as many transitions as `a', it is not even worth considering.
  99.  */
  100.  
  101. int compat(a, b, xse)
  102. struct dfa *a, *b;
  103. struct xset *xse;
  104. {
  105.         struct dfa *dp;
  106.         struct xset *xs;
  107.         int nt;
  108.  
  109.         if(a==b || ( b->df_ntrans >= a->df_ntrans*2 ) )  return(-1);
  110.  
  111.         for(dp = b; dp; dp = dp->df_default)
  112.                 if (dp == a) return(-1);
  113.  
  114.         nt = b->df_ntrans + a->df_ntrans;
  115.  
  116.         for(xs = sets; xs < xse; xs++)
  117.                 if(chase(b, xs->x_char) == xs->x_set)  nt -= 2;
  118.  
  119. #ifdef DEBUG
  120.         fprintf( stdout, "\nCOMPAT: nt = %d", nt);
  121. #endif
  122.  
  123.         return( nt );
  124. }
  125.  
  126. struct set *chase(st, c)
  127. struct dfa *st;
  128. int c;
  129. {
  130.         struct move *dp;
  131.  
  132.         c &= CMASK;
  133.         while((dp = st->df_base) != NULL && ((dp += c) >= st->df_max
  134.              || dp->m_check != st) )
  135.                 if ((st = st->df_default) == NULL) return((struct set *)NULL);
  136.  
  137.         if(dp != NULL) return( dp->m_next );
  138.         else           return((struct set *)NULL);
  139. }
  140.  
  141. /*
  142.  * set `sets' to indicate those characters on which the state `a'
  143.  * and its default agree and those characters on which `a'
  144.  * should go to `error' (as the default accepts it, but `a' does not).
  145.  */
  146. int resolve(a, def, xsep)
  147. struct dfa *a, *def;
  148. struct xset **xsep;
  149. {
  150.         struct move *dp;
  151.         int c, i;
  152.         struct xset *xs, *xse;
  153.  
  154.         a = a;                          /* Quiet compiler the easy way */
  155.  
  156.         xse = *xsep;
  157.         i = xse - sets;
  158.         for(xs = sets; xs < xse; xs++) xs->x_defsame = '\0';
  159.         for(; def; def = def->df_default)
  160.         for(dp = def->df_base; dp < def->df_max; dp++)
  161.                 if(dp->m_check == def) {
  162.                         c = dp - def->df_base;
  163.                         for (xs = sets; xs < xse; xs++)
  164.                                 if (c==(xs->x_char&CMASK)) {
  165.                                         if (xs->x_set==dp->m_next) {
  166.                                                 xs->x_defsame++;
  167.                                                 i--;
  168.                                         }
  169.                                         break;
  170.                                 }
  171.                         if(xs >= xse) {
  172.                                 xs->x_defsame = '\0';
  173.                                 xs->x_char = c;
  174.                                 xs->x_set = (struct set *)NULL;
  175.                                 i++;
  176.                                 xse++;
  177.                         }
  178.                 }
  179.         *xsep = xse;
  180.         return(i);
  181. }
  182.  
  183. /*
  184.  * Choose a base in `move' for the current state.
  185.  * The transitions of that state are in the vector `sets'.
  186.  */
  187. struct move *stbase(xse)
  188. struct xset *xse;
  189. {
  190.         int  a;
  191.         struct move *base;
  192.         int conflicts;
  193.         struct xset *xs;
  194.  
  195.         if( xse == sets)
  196.                 return(NULL);
  197.         base = move;
  198.         do{
  199.                 if(base - move >= NNEXT)
  200.                 {
  201.                         error("No space in `move' (stbase)","");
  202.                         exit(1);
  203.                 }
  204.                 conflicts = 0;
  205.                 for(xs = &sets[0]; xs < xse; xs++) {
  206.                         a = xs->x_char & CMASK;
  207.                         if(xs->x_defsame == 0 &&
  208.                            ( &base[a] >= &move[NNEXT] || /* AMW: modified */
  209.                              base[a].m_check != (struct dfa*)NULL)
  210.                            )
  211.                              {
  212.                                 conflicts++;
  213.                                 base++;
  214.                                 break;
  215.                              }
  216.                 }
  217.         } while(conflicts);
  218.         return(base);
  219. }
  220.  
  221. /*
  222.  * Given a state, its `base' value in `move',
  223.  * and the set of transitions in `sets' (ending near `xse'),
  224.  * set the `move' values.
  225.  */
  226. void setbase(st, base, xse)
  227. struct dfa *st;
  228. struct move *base;
  229. struct xset *xse;
  230. {
  231.         struct move *dp;
  232.         struct xset *xs;
  233.         struct move *maxdp;
  234.  
  235.         st->df_base = base;
  236.         st->df_max = base;
  237. #ifdef DEBUG
  238.     fprintf( stdout, "\nSetbase: state %d\n", st - dfa );
  239.     if( base == NULL ) fprintf( stdout, "\tno base\n");
  240. #endif
  241.         if(base == NULL) return;
  242.         maxdp = base;
  243.         for(xs = sets; xs < xse; xs++)
  244.                 if(xs->x_defsame == '\0' ) {
  245.                 /* Base is a pointer into the move[] array */
  246.                         dp = base + (int)xs->x_char ;
  247.                         if(dp > maxdp) maxdp = dp;
  248.                         dp->m_next = xs->x_set;
  249.                         dp->m_check = st;
  250.                         if( (dp - move) > llnxtmax) llnxtmax = dp - move;
  251. #ifdef UDEBUG
  252.        /* This set of statements was causing the program to abort */
  253.                         fprintf(stdout, "\t%c nets %d\n", xs->x_char&CMASK, dp - move );
  254. #endif
  255.                 }
  256.  
  257.         st->df_max = maxdp+1;
  258. }
  259.  
  260.  
  261.  
  262.