home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / m / mawk11as.zip / REXP / REXP0.C < prev    next >
C/C++ Source or Header  |  1992-01-21  |  11KB  |  459 lines
  1.  
  2. /********************************************
  3. rexp0.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the AWK programming language.
  8.  
  9. Mawk is distributed without warranty under the terms of
  10. the GNU General Public License, version 2, 1991.
  11. ********************************************/
  12.  
  13. /*$Log:    rexp0.c,v $
  14.  * Revision 3.6  92/01/21  17:32:51  brennan
  15.  * added some casts so that character classes work with signed chars
  16.  * 
  17.  * Revision 3.5  91/10/29  10:53:57  brennan
  18.  * SIZE_T
  19.  * 
  20.  * Revision 3.4  91/08/13  09:10:05  brennan
  21.  * VERSION .9994
  22.  * 
  23.  * Revision 3.3  91/07/19  07:29:24  brennan
  24.  * backslash at end of regular expression now stands for backslash
  25.  * 
  26.  * Revision 3.2  91/07/19  06:58:23  brennan
  27.  * removed small bozo in processing of escape characters
  28.  * 
  29.  * Revision 3.1  91/06/07  10:33:20  brennan
  30.  * VERSION 0.995
  31.  * 
  32.  * Revision 1.2  91/06/05  08:59:36  brennan
  33.  * changed RE_free to free
  34.  * 
  35.  * Revision 1.1  91/06/03  07:10:15  brennan
  36.  * Initial revision
  37.  * 
  38. */
  39.  
  40. /*  lexical scanner  */
  41.  
  42. #include  "rexp.h"
  43.  
  44. /* static functions */
  45. static int  PROTO( do_str, (int, char **, MACHINE *) ) ;
  46. static int  PROTO( do_class, (char **, MACHINE *) ) ;
  47. static int  PROTO( escape, (char **) ) ;
  48. static BV   *PROTO( store_bvp, (BV *) ) ;
  49. static int  PROTO( ctohex, (int) ) ;
  50.  
  51.  
  52. #ifndef  EG  /* if EG make next array visible */
  53. static
  54. #endif
  55. char  RE_char2token[ '|' + 1 ] = {
  56. 0,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  57. 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,9,13,13,13,
  58. 6,7,3,4,13,13,10,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  59. 13,13,5,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  60. 13,13,13,13,13,13,13,13,13,13,11,12,13,8,13,13,13,13,13,13,
  61. 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  62. 13,13,13,13,1} ;
  63.  
  64. #define  char2token(x) ( (unsigned char)(x) > '|' ? T_CHAR : RE_char2token[x] )
  65.  
  66. #define NOT_STARTED    (-1)
  67.  
  68. static  int  prev  ;
  69. static  char   *lp  ;     /*  ptr to reg exp string  */
  70. static  unsigned re_len ;
  71.  
  72.  
  73. void  RE_lex_init( re )
  74.   char *re ;
  75. { 
  76.   lp = re ;
  77.   re_len = strlen(re) + 1  ;
  78.   prev = NOT_STARTED ;
  79.   RE_run_stack_init() ;
  80. }
  81.   
  82.  
  83. int   RE_lex( mp )
  84.   MACHINE  *mp ;
  85. { register int c ;
  86.  
  87.   switch( c = char2token(*lp) )
  88.    {
  89.      case T_OR :
  90.      case T_PLUS :
  91.      case T_STAR :
  92.      case T_Q :
  93.      case T_RP :
  94.            lp++ ;  return  prev = c ;
  95.      case T_SLASH :
  96.            break ;
  97.  
  98.      case 0   :   return 0 ;
  99.      
  100.      case T_LP :
  101.            switch( prev )
  102.            { 
  103.              case T_CHAR :
  104.              case T_STR  :
  105.              case T_ANY :
  106.              case T_CLASS :
  107.              case T_START :
  108.              case T_RP :
  109.              case T_PLUS :
  110.              case T_STAR :
  111.              case T_Q :
  112.              case T_U :
  113.                   return prev = T_CAT ;
  114.              default  :
  115.                   lp++ ;
  116.                   return prev = T_LP ;
  117.            }
  118.    }
  119.  
  120.   /*  *lp  is  an operand, but implicit cat op is possible   */
  121.   switch( prev )
  122.    { case  NOT_STARTED :
  123.      case  T_OR :
  124.      case  T_LP :
  125.      case T_CAT :
  126.  
  127.           switch( c )
  128.            { case  T_ANY : 
  129.              { static plus_is_star_flag = 0 ;
  130.  
  131.                   if ( * ++lp == '*' )
  132.                   { lp++ ;  *mp = RE_u() ;
  133.                     return  prev = T_U ; }
  134.                   else
  135.                   if ( *lp == '+' )
  136.                       if ( plus_is_star_flag )
  137.                       { lp++ ;  *mp = RE_u() ;
  138.                         plus_is_star_flag = 0 ;
  139.                         return prev = T_U ;
  140.                       }
  141.                       else
  142.                       { plus_is_star_flag = 1 ;
  143.                         lp-- ; *mp = RE_any() ;
  144.                         return prev = T_ANY ;
  145.                       }
  146.                   else  
  147.                   { *mp = RE_any() ;
  148.                     prev = T_ANY ;
  149.                   }
  150.               }
  151.               break ;
  152.                     
  153.              case  T_SLASH :
  154.                   lp++ ; c = escape(&lp) ;
  155.                   prev = do_str(c, &lp, mp) ;
  156.                   break ;
  157.  
  158.              case  T_CHAR  :
  159.                   c = *lp++ ;
  160.                   prev = do_str(c, &lp, mp) ;
  161.                   break ;
  162.  
  163.              case T_CLASS : prev = do_class(&lp, mp) ;
  164.                             break ;
  165.  
  166.              case T_START : *mp = RE_start() ; lp++ ;
  167.                             prev = T_START ;
  168.                             break ;
  169.  
  170.              case T_END :  
  171.                      lp++ ; *mp = RE_end() ;
  172.                      return  prev = T_END ;
  173.  
  174.              default :
  175.                      RE_panic("bad switch in RE_lex") ;
  176.            }
  177.            break ;
  178.  
  179.      default : /* don't advance the pointer, return T_CAT */
  180.           return prev = T_CAT ;
  181.     }
  182.     /* check for end character */
  183.     if ( *lp == '$' )
  184.     { mp->start->type += END_ON ; lp++ ; }
  185.     return prev ;
  186. }
  187.  
  188. static  int  do_str( c, pp, mp)
  189.   int c ; /* the first character */
  190.   char **pp ;  /* where to put the re_char pointer on exit */
  191.   MACHINE  *mp ;  /* where to put the string machine */
  192. { register char *p , *s ;
  193.   char *str ;
  194.   unsigned len ;
  195.  
  196.  
  197.   p = *pp ;
  198.   s = str = RE_malloc( re_len ) ;
  199.   *s++ = c ;  len = 1 ;
  200.  
  201.   while ( 1 )
  202.   { char *save ;
  203.   
  204.     switch( char2token(*p) )
  205.     {
  206.       case  T_CHAR :  *s++ = *p++ ;
  207.                       break ;
  208.       case  T_SLASH :
  209.                       save = ++p ;
  210.                       *s++ = escape(&save) ;
  211.                       p = save ;
  212.                       break ;
  213.  
  214.       default  :  goto  out ;
  215.     }
  216.     len++ ;
  217.   }
  218. out:
  219.   /* if len > 1 and we failed on a ? + or * , need to back up */
  220.   if ( len > 1 && (*p == '*' || *p == '+' || *p == '?' ) )
  221.   { len-- ; p-- ; s-- ; }
  222.  
  223.   *s = 0 ;
  224.   *pp = p ;
  225.   *mp = RE_str((char *) RE_realloc(str, len+1) , len) ;
  226.   return  T_STR ;
  227. }
  228.  
  229.  
  230. /*--------------------------------------------
  231.   BUILD A CHARACTER CLASS
  232.  *---------------------------*/
  233.  
  234. #define  on( b, x)  ( (b)[((unsigned char)(x))>>3] |= ( 1 << ((x)&7) ))
  235.  
  236. static  void  PROTO(block_on, (BV,int,int) ) ;
  237.  
  238. static  void  block_on( b, x, y)
  239.   BV b ; int x, y ; 
  240. { int lo = (x&0xff) >> 3 ;
  241.   int hi = (y&0xff) >> 3 ;
  242.   int  i, j, bit  ;
  243.  
  244.   if ( lo == hi )
  245.     { j = x&7 ; bit =  1 << j ; i = (y&7) - j + 1 ;
  246.       for ( ; i ; i-- , bit <<= 1 )  b[lo] |= bit ; }
  247.   else
  248.     { for ( i = lo + 1 ; i <= hi - 1 ; i++ )  b[i] = 0xff ;
  249.       b[lo] |= ( 0xff << (x&7) ) ;
  250.       b[hi] |= ~( 0xff << ((y&7)+1)) ;
  251.     }
  252. }
  253.  
  254. /* build a BV for a character class.
  255.    *start points at the '['
  256.    on exit:   *start points at the character after ']'
  257.               mp points at a machine that recognizes the class
  258. */
  259.  
  260. static int  do_class( start, mp)
  261.   char **start ; MACHINE  *mp ;
  262. { register char *p ;
  263.   register BV   *bvp ;
  264.   int  prev ;
  265.   char *q , *t;
  266.   int  cnt ;
  267.   int comp_flag ;
  268.  
  269.   p = (*start) + 1 ;
  270.   if ( *p == ']' || *p == '^' && *(p+1) == ']' )
  271.          RE_error_trap(-E3) ;
  272.   while ( 1 )  /* find the back of the class */
  273.     { if ( ! (q = strchr(p,']')) )  /* no closing bracket */
  274.          RE_error_trap(-E3) ;
  275.       p = q-1 ;
  276.       cnt = 0 ;
  277.       while ( *p == '\\') { cnt++ ; p-- ; }
  278.       if ( (cnt & 1) == 0 )  /* even number of \ */  break ;
  279.       p = q+1 ;
  280.     }
  281.   /*  q  now  pts at the back of the class   */
  282.   p = (*start) + 1 ;
  283.   *start = q + 1 ;
  284.  
  285.   bvp = (BV *) RE_malloc( sizeof(BV) ) ;
  286.   (void) memset( bvp, 0, SIZE_T(sizeof(BV)) ) ;
  287.  
  288.   comp_flag = *p == '^' ? (p++ , 1) : 0 ;
  289.   prev = -1 ;  /* indicates  -  cannot be part of a range  */
  290.  
  291.   while ( p < q )
  292.   {
  293.      switch( *p )
  294.       { case '\\' :
  295.           t = ++p ;
  296.           prev = escape(&t) ;
  297.           on(*bvp, prev) ;
  298.           p = t ;
  299.           continue ;
  300.  
  301.         case '-' :
  302.           if ( prev == -1 || p+1 == q || prev > *(unsigned char*)(p+1) )
  303.              { prev = '-' ; on(*bvp, '-') ; }
  304.           else
  305.              { p++ ;
  306.                block_on(*bvp, prev, *p) ;
  307.                prev = -1 ;
  308.              }
  309.           break ;
  310.  
  311.         default :
  312.           prev = *(unsigned char*)p ;
  313.           on(*bvp, *p) ;
  314.           break ;
  315.       }
  316.       p++ ;
  317.   }
  318.  
  319.   if ( comp_flag )
  320.     for ( p = (char *) bvp ; p < (char *) bvp + sizeof(BV) ; p++)  *p = ~*p ;
  321.  
  322.   /* make sure zero is off */
  323.   (*bvp)[0] &= 0xfe ;
  324.  
  325.   *mp = RE_class( store_bvp( bvp ) ) ;
  326.   return  T_CLASS ;
  327. }
  328.  
  329.  
  330. /* storage for bit vectors so they can be reused ,
  331.    stored in an unsorted linear array 
  332.    the array grows as needed
  333. */
  334.  
  335. #define         BV_GROWTH       6
  336.  
  337. static BV *store_bvp( bvp )
  338.   BV *bvp ;
  339. {
  340.   static BV **bv_base, **bv_limit ;
  341.   static BV **bv_next ; /* next empty slot in the array */
  342.  
  343.   register BV **p ;
  344.   unsigned t ;
  345.  
  346.  
  347.   if ( bv_next == bv_limit ) /* need to grow */
  348.   {
  349.     if ( ! bv_base )  /* first growth */
  350.     {  t = 0 ; bv_base = (BV**)RE_malloc(BV_GROWTH*sizeof(BV*)) ; }
  351.     else 
  352.     { t = bv_next - bv_base ;
  353.       bv_base = (BV**) RE_realloc(bv_base, (t+BV_GROWTH)*sizeof(BV*)) ;
  354.     }
  355.  
  356.     bv_next = bv_base + t ;
  357.     bv_limit = bv_next + BV_GROWTH ;
  358.   }
  359.  
  360.   /* put bvp in bv_next as a sentinal */
  361.   *bv_next = bvp ;
  362.   p = bv_base ;
  363.   while ( memcmp(*p, bvp, SIZE_T(sizeof(BV))) )  p++ ;
  364.  
  365.   if ( p == bv_next )  /* it is new */
  366.         bv_next++ ;
  367.   else  /* we already have it */  free(bvp) ;
  368.  
  369.   return *p ;
  370. }
  371.   
  372.  
  373. /* ----------   convert escape sequences  -------------*/
  374.  
  375. #define isoctal(x)  ((x)>='0'&&(x)<='7')
  376.  
  377. #define  NOT_HEX        16
  378. static char hex_val['f' - 'A' + 1] = {
  379. 10,11,12,13,14,15, 0, 0,
  380.  0, 0, 0, 0, 0, 0, 0, 0,
  381.  0, 0, 0, 0, 0, 0, 0, 0,
  382.  0, 0, 0, 0, 0, 0, 0, 0,
  383. 10,11,12,13,14,15 } ;
  384.  
  385. /* interpret 1 character as hex */
  386. static int ctohex( c )
  387.   register int c ;
  388. { int t ;
  389.  
  390.   if ( c >= '0' && c <= '9' )  return c - '0' ;
  391.  
  392.   if ( c >= 'A' && c <= 'f' && ( t = hex_val[c-'A'] ))  return t ;
  393.  
  394.   return NOT_HEX ;
  395. }
  396.  
  397. #define  ET_END     7
  398.  
  399. static struct { char in , out ; } escape_test[ET_END+1] = {
  400. 'n' , '\n',
  401. 't' , '\t',
  402. 'f' , '\f',
  403. 'b' , '\b',
  404. 'r' , '\r',
  405. 'a' , '\07',
  406. 'v' , '\013',
  407. 0 , 0 } ;
  408.  
  409.  
  410. /*-----------------
  411.   return the char 
  412.   and move the pointer forward
  413.   on entry *s -> at the character after the slash
  414.  *-------------------*/
  415.  
  416. static int escape(start_p)
  417.   char **start_p ;
  418. { register char *p = *start_p ;
  419.   register unsigned x ;
  420.   unsigned xx ;
  421.   int i ;
  422.  
  423.   
  424.   escape_test[ET_END].in = *p ;
  425.   i = 0 ;
  426.   while ( escape_test[i].in != *p ) i++ ;
  427.   if ( i != ET_END )  /* in table */
  428.   { *start_p = p + 1 ;
  429.     return  escape_test[i].out ;
  430.   }
  431.  
  432.   if ( isoctal(*p) )
  433.   { x = *p++ - '0' ;
  434.     if ( isoctal(*p) )
  435.     { x = (x<<3) + *p++ - '0' ;
  436.       if ( isoctal(*p) )
  437.          x = (x<<3) + *p++ - '0' ;
  438.     }
  439.     *start_p = p ;
  440.     return  x & 0xff ;
  441.   }
  442.  
  443.   if ( *p == 0 )  return '\\' ;
  444.  
  445.   if ( *p++ == 'x' ) /* might be a hex digit */
  446.   {  if ( (x = ctohex(*p)) == NOT_HEX ) 
  447.      { *start_p  = p ;  return 'x' ; }
  448.  
  449.      /* look for another hex digit */
  450.      if ( (xx = ctohex(* ++p)) != NOT_HEX )
  451.      { x = (x<<4) + xx ; p++ ; }
  452.  
  453.      *start_p = p ; return x ;
  454.   }
  455.   /* anything else \c -> c */
  456.   *start_p = p ;
  457.   return p[-1]  ;
  458. }
  459.