home *** CD-ROM | disk | FTP | other *** search
/ Acorn User 11 / AUCD11B.iso / LANGUAGES / WraithSet / AwkStuff / MawkSrc / rexp / c / rexp0 < prev    next >
Text File  |  1996-11-08  |  12KB  |  635 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 1.5  1996/11/08 15:39:27  mike
  15.  *While cleaning up block_on, I introduced a bug. Now fixed.
  16.  *
  17.  *Revision 1.4  1996/09/02 18:47:09  mike
  18.  *Allow []...] and [^]...] to put ] in a class.
  19.  *Make ^* and ^+ syntax errors.
  20.  *
  21.  * Revision 1.3  1994/12/26  16:37:52  mike
  22.  * 1.1.2 fix to do_str was incomplete -- fix it
  23.  *
  24.  * Revision 1.2  1993/07/23  13:21:38  mike
  25.  * cleanup rexp code
  26.  *
  27.  * Revision 1.1.1.1  1993/07/03     18:58:27  mike
  28.  * move source to cvs
  29.  *
  30.  * Revision 3.8     1992/04/21  20:22:38  brennan
  31.  * 1.1 patch2
  32.  * [c1-c2] now works if c2 is an escaped character
  33.  *
  34.  * Revision 3.7     1992/03/24  09:33:12  brennan
  35.  * 1.1 patch2
  36.  * When backing up in do_str, check if last character was escaped
  37.  *
  38.  * Revision 3.6     92/01/21  17:32:51  brennan
  39.  * added some casts so that character classes work with signed chars
  40.  *
  41.  * Revision 3.5     91/10/29  10:53:57  brennan
  42.  * SIZE_T
  43.  *
  44.  * Revision 3.4     91/08/13  09:10:05  brennan
  45.  * VERSION .9994
  46.  *
  47.  * Revision 3.3     91/07/19  07:29:24  brennan
  48.  * backslash at end of regular expression now stands for backslash
  49.  *
  50.  * Revision 3.2     91/07/19  06:58:23  brennan
  51.  * removed small bozo in processing of escape characters
  52.  *
  53.  * Revision 3.1     91/06/07  10:33:20  brennan
  54.  * VERSION 0.995
  55.  *
  56.  * Revision 1.2     91/06/05  08:59:36  brennan
  57.  * changed RE_free to free
  58.  *
  59.  * Revision 1.1     91/06/03  07:10:15  brennan
  60.  * Initial revision
  61.  *
  62. */
  63.  
  64. /*  lexical scanner  */
  65.  
  66. #include  "rexp.h"
  67.  
  68. /* static functions */
  69. static int PROTO(do_str, (int, char **, MACHINE *)) ;
  70. static int PROTO(do_class, (char **, MACHINE *)) ;
  71. static int PROTO(escape, (char **)) ;
  72. static BV *PROTO(store_bvp, (BV *)) ;
  73. static int PROTO(ctohex, (int)) ;
  74.  
  75.  
  76. #ifndef     EG    
  77. /* make next array visible */
  78. static
  79. #endif
  80. char  RE_char2token[ '|' + 1 ] = {
  81. 0,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  82. 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,9,13,13,13,
  83. 6,7,3,4,13,13,10,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  84. 13,13,5,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  85. 13,13,13,13,13,13,13,13,13,13,11,12,13,8,13,13,13,13,13,13,
  86. 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  87. 13,13,13,13,1} ;
  88.  
  89. #define     char2token(x) \
  90. ( (unsigned char)(x) > '|' ? T_CHAR : RE_char2token[x] )
  91.  
  92. #define NOT_STARTED    (-1)
  93.  
  94. static int prev ;
  95. static char *lp ;         /*  ptr to reg exp string  */
  96. static unsigned re_len ;
  97.  
  98.  
  99. void
  100. RE_lex_init(re)
  101.    char *re ;
  102. {
  103.    lp = re ;
  104.    re_len = strlen(re) + 1 ;
  105.    prev = NOT_STARTED ;
  106.    RE_run_stack_init() ;
  107. }
  108.  
  109.  
  110. int
  111. RE_lex(mp)
  112.    MACHINE *mp ;
  113. {
  114.    register int c ;
  115.  
  116. reswitch:
  117.    switch (c = char2token(*lp))
  118.    {
  119.       case T_PLUS:
  120.       case T_STAR:
  121.      if (prev == T_START) RE_error_trap(6) ;
  122.      /* fall thru */
  123.  
  124.       case T_OR:
  125.       case T_Q:
  126.       case T_RP:
  127.      lp++ ;     return     prev = c ;
  128.  
  129.       case T_SLASH:
  130.      break ;
  131.  
  132.       case 0:
  133.      return 0 ;
  134.  
  135.       case T_LP:
  136.      switch (prev)
  137.      {
  138.         case T_CHAR:
  139.         case T_STR:
  140.         case T_ANY:
  141.         case T_CLASS:
  142.         case T_START:
  143.         case T_RP:
  144.         case T_PLUS:
  145.         case T_STAR:
  146.         case T_Q:
  147.         case T_U:
  148.            return prev = T_CAT ;
  149.  
  150.         default:
  151.            lp++ ;
  152.            return prev = T_LP ;
  153.      }
  154.    }
  155.  
  156.    /*  *lp  is    an operand, but implicit cat op is possible   */
  157.    switch (prev)
  158.    {
  159.       case NOT_STARTED:
  160.       case T_OR:
  161.       case T_LP:
  162.       case T_CAT:
  163.  
  164.      switch (c)
  165.      {
  166.         case T_ANY:
  167.            {
  168.           static plus_is_star_flag = 0 ;
  169.  
  170.           if (*++lp == '*')
  171.           {
  172.              lp++ ;
  173.              *mp = RE_u() ;
  174.              return prev = T_U ;
  175.           }
  176.           else if (*lp == '+')
  177.           {
  178.              if (plus_is_star_flag)
  179.              {
  180.             lp++ ;
  181.             *mp = RE_u() ;
  182.             plus_is_star_flag = 0 ;
  183.             return prev = T_U ;
  184.              }
  185.              else
  186.              {
  187.             plus_is_star_flag = 1 ;
  188.             lp-- ;
  189.             *mp = RE_any() ;
  190.             return prev = T_ANY ;
  191.              }
  192.           }
  193.           else
  194.           {
  195.              *mp = RE_any() ;
  196.              prev = T_ANY ;
  197.           }
  198.            }
  199.            break ;
  200.  
  201.         case T_SLASH:
  202.            lp++ ;
  203.            c = escape(&lp) ;
  204.            prev = do_str(c, &lp, mp) ;
  205.            break ;
  206.  
  207.         case T_CHAR:
  208.            c = *lp++ ;
  209.            prev = do_str(c, &lp, mp) ;
  210.            break ;
  211.  
  212.         case T_CLASS:
  213.            prev = do_class(&lp, mp) ;
  214.            break ;
  215.  
  216.         case T_START:
  217.            *mp = RE_start() ;
  218.            lp++ ;
  219.            prev = T_START ;
  220.            break ;
  221.  
  222.         case T_END:
  223.            lp++ ;
  224.            *mp = RE_end() ;
  225.            return prev = T_END ;
  226.  
  227.         default:
  228.            RE_panic("bad switch in RE_lex") ;
  229.      }
  230.      break ;
  231.  
  232.       default:
  233.      /* don't advance the pointer */
  234.      return prev = T_CAT ;
  235.    }
  236.  
  237.    /* check for end character */
  238.    if (*lp == '$')
  239.    {
  240.       mp->start->type += END_ON ;
  241.       lp++ ;
  242.    }
  243.  
  244.    return prev ;
  245. }
  246.  
  247. /*
  248.   Collect a run of characters into a string machine.
  249.   If the run ends at *,+, or ?, then don't take the last
  250.   character unless the string has length one.
  251. */
  252.  
  253. static int
  254. do_str(c, pp, mp)
  255.    int c ;             /* the first character */
  256.    char **pp ;             /* where to put the re_char pointer on exit */
  257.    MACHINE *mp ;         /* where to put the string machine */
  258. {
  259.    register char *p ;         /* runs thru the input */
  260.    char *pt ;             /* trails p by one */
  261.    char *str ;             /* collect it here */
  262.    register char *s ;         /* runs thru the output */
  263.    unsigned len ;         /* length collected */
  264.  
  265.  
  266.    p = *pp ;
  267.    s = str = RE_malloc(re_len) ;
  268.    *s++ = c ;  len = 1 ;
  269.  
  270.    while (1)
  271.    {
  272.       char *save ;   
  273.  
  274.       switch (char2token(*p))
  275.       {
  276.      case T_CHAR:
  277.         pt = p ;
  278.         *s++ = *p++ ;
  279.         break ;
  280.  
  281.      case T_SLASH:
  282.         pt = p ;
  283.         save = p+1 ;   /* keep p in a register */
  284.         *s++ = escape(&save) ;
  285.         p = save ;
  286.         break ;
  287.  
  288.      default:
  289.         goto out ;
  290.       }
  291.       len++ ;
  292.    }
  293.  
  294. out:
  295.    /* if len > 1 and we stopped on a ? + or * , need to back up */
  296.    if (len > 1 && (*p == '*' || *p == '+' || *p == '?'))
  297.    {
  298.       len-- ; 
  299.       p = pt ;
  300.       s-- ;
  301.    }
  302.  
  303.    *s = 0 ;
  304.    *pp = p ;
  305.    *mp = RE_str((char *) RE_realloc(str, len + 1), len) ;
  306.    return T_STR ;
  307. }
  308.  
  309.  
  310. /*--------------------------------------------
  311.   BUILD A CHARACTER CLASS
  312.  *---------------------------*/
  313.  
  314. #define     on( b, x)  ((b)[(x)>>3] |= ( 1 << ((x)&7) ))
  315.  
  316. static void PROTO(block_on, (BV, int, int)) ;
  317.  
  318. static void
  319. block_on(b, x, y)
  320.    BV b ;
  321.    int x, y ;
  322.    /* caller makes sure x<=y and x>0 y>0 */
  323. {
  324.    int lo = x >> 3 ;
  325.    int hi = y >> 3 ;
  326.    int r_lo = x&7 ;
  327.    int r_hi = y&7 ;
  328.  
  329.    if (lo == hi)
  330.    {
  331.       b[lo] |= (1<<(r_hi+1)) - (1<<r_lo) ;
  332.    }
  333.    else
  334.    {
  335.       int i ;
  336.       for (i = lo + 1; i <  hi ; i++)  b[i] = 0xff ;
  337.       b[lo] |= (0xff << r_lo) ;
  338.       b[hi] |= ~(0xff << (r_hi+1)) ;
  339.    }
  340. }
  341.  
  342. /* build a BV for a character class.
  343.    *start points at the '['
  344.    on exit:   *start points at the character after ']'
  345.           mp points at a machine that recognizes the class
  346. */
  347.  
  348. static int
  349. do_class(start, mp)  char **start ;
  350.    MACHINE *mp ;
  351. {
  352.    register char *p ;
  353.    register BV *bvp ;
  354.    int prev ;
  355.    char *q, *t ;
  356.    int cnt ;
  357.    int comp_flag ;
  358.  
  359.    p = t = (*start) + 1 ;
  360.  
  361.    /* []...]  puts ] in a class
  362.       [^]..]  negates a class with ]
  363.    */
  364.    if (*p == ']') p++ ;
  365.    else if (*p == '^' && *(p + 1) == ']')  p += 2 ;
  366.  
  367.    while (1)            /* find the back of the class */
  368.    {
  369.       if (!(q = strchr(p, ']')))
  370.       {
  371.      /* no closing bracket */
  372.      RE_error_trap(-E3) ;
  373.       }
  374.       p = q - 1 ;
  375.       cnt = 0 ;
  376.       while (*p == '\\')
  377.       {
  378.      cnt++ ; p-- ; 
  379.       }
  380.       if ((cnt & 1) == 0)
  381.       {
  382.      /* even number of \ */
  383.      break ;
  384.       }
  385.       p = q + 1 ;
  386.    }
  387.  
  388.    /*  q  now  pts at the back of the class   */
  389.    p = t ;
  390.    *start = q + 1 ;
  391.  
  392.    bvp = (BV *) RE_malloc(sizeof(BV)) ;
  393.    memset(bvp, 0, sizeof(BV)) ;
  394.  
  395.    if (*p == '^')
  396.    {
  397.       comp_flag = 1 ; p++ ; 
  398.    }
  399.    else     comp_flag = 0 ;
  400.  
  401.    prev = -1 ;             /* indicates  -  cannot be part of a range  */
  402.  
  403.    while (p < q)
  404.    {
  405.       switch (*p)
  406.       {
  407.      case '\\':
  408.  
  409.         t = p + 1 ;
  410.         prev = escape(&t) ;
  411.         on(*bvp, prev) ;
  412.         p = t ;
  413.         break ;
  414.  
  415.      case '-':
  416.  
  417.         if (prev == -1 || p + 1 == q)
  418.         {
  419.            prev = '-' ;
  420.            on(*bvp, '-') ;
  421.            p++ ;
  422.         }
  423.         else
  424.         {
  425.            int c ;
  426.            char *mark = ++p ;
  427.  
  428.            if (*p != '\\')    c = *(unsigned char *) p++ ;
  429.            else
  430.            {
  431.           t = p + 1 ;
  432.           c = escape(&t) ;
  433.           p = t ;
  434.            }
  435.  
  436.            if (prev <= c)
  437.            {
  438.           block_on(*bvp, prev, c) ;
  439.           prev = -1 ;
  440.            }
  441.            else  /* back up */
  442.            {
  443.           p = mark ;
  444.           prev = '-' ;
  445.           on(*bvp, '-') ;
  446.            }
  447.         }
  448.         break ;
  449.  
  450.      default:
  451.         prev = *(unsigned char *) p++ ;
  452.         on(*bvp, prev) ;
  453.         break ;
  454.       }
  455.    }
  456.  
  457.    if (comp_flag)
  458.    {
  459.       for (p = (char *) bvp; p < (char *) bvp + sizeof(BV); p++)
  460.       {
  461.      *p = ~*p ;
  462.       }
  463.    }
  464.  
  465.    /* make sure zero is off */
  466.    (*bvp)[0] &= ~1 ;
  467.  
  468.    *mp = RE_class(store_bvp(bvp)) ;
  469.    return T_CLASS ;
  470. }
  471.  
  472.  
  473. /* storage for bit vectors so they can be reused ,
  474.    stored in an unsorted linear array
  475.    the array grows as needed
  476. */
  477.  
  478. #define        BV_GROWTH    6
  479.  
  480. static BV *
  481. store_bvp(bvp)
  482.    BV *bvp ;
  483. {
  484.    static BV **bv_base, **bv_limit ;
  485.    static BV **bv_next ;     /* next empty slot in the array */
  486.  
  487.    register BV **p ;
  488.    unsigned t ;
  489.  
  490.  
  491.    if (bv_next == bv_limit)
  492.    {
  493.       /* need to grow */
  494.       if (!bv_base)
  495.       {
  496.      /* first growth */
  497.      t = 0 ;
  498.      bv_base = (BV **) RE_malloc(BV_GROWTH * sizeof(BV *)) ;
  499.       }
  500.       else
  501.       {
  502.      t = bv_next - bv_base ;
  503.      bv_base = (BV **) RE_realloc(bv_base, (t + BV_GROWTH) * sizeof(BV *)) ;
  504.       }
  505.  
  506.       bv_next = bv_base + t ;
  507.       bv_limit = bv_next + BV_GROWTH ;
  508.    }
  509.  
  510.    /* put bvp in bv_next as a sentinal */
  511.    *bv_next = bvp ;
  512.    p = bv_base ;
  513.    while (memcmp(*p, bvp, sizeof(BV)))    p++ ;
  514.  
  515.    if (p == bv_next)
  516.    {
  517.       /* it is new */
  518.       bv_next++ ;
  519.    }
  520.    else
  521.    {
  522.       /* we already have it */
  523.       free(bvp) ;
  524.    }
  525.  
  526.    return *p ;
  527. }
  528.  
  529.  
  530. /* ----------    convert escape sequences  -------------*/
  531.  
  532. #define isoctal(x)  ((x)>='0'&&(x)<='7')
  533.  
  534. #define     NOT_HEX    16
  535. static char hex_val['f' - 'A' + 1] =
  536. {
  537.    10, 11, 12, 13, 14, 15, 0, 0,
  538.    0, 0, 0, 0, 0, 0, 0, 0,
  539.    0, 0, 0, 0, 0, 0, 0, 0,
  540.    0, 0, 0, 0, 0, 0, 0, 0,
  541.    10, 11, 12, 13, 14, 15} ;
  542.  
  543. /* interpret 1 character as hex */
  544. static int
  545. ctohex(c)
  546.    register int c ;
  547. {
  548.    int t ;
  549.  
  550.    if (c >= '0' && c <= '9')  return c - '0' ;
  551.    if (c >= 'A' && c <= 'f' && (t = hex_val[c - 'A']))    return t ;
  552.    return NOT_HEX ;
  553. }
  554.  
  555. #define     ET_END        7
  556.  
  557. static struct
  558. {
  559.    char in, out ;
  560. }
  561. escape_test[ET_END + 1] =
  562. {
  563.    'n', '\n',
  564.    't', '\t',
  565.    'f', '\f',
  566.    'b', '\b',
  567.    'r', '\r',
  568.    'a', '\07',
  569.    'v', '\013',
  570.    0, 0
  571. } ;
  572.  
  573.  
  574. /*-----------------
  575.   return the char
  576.   and move the pointer forward
  577.   on entry *s -> at the character after the slash
  578.  *-------------------*/
  579.  
  580. static int
  581. escape(start_p)
  582.    char **start_p ;
  583. {
  584.    register char *p = *start_p ;
  585.    register unsigned x ;
  586.    unsigned xx ;
  587.    int i ;
  588.  
  589.  
  590.    escape_test[ET_END].in = *p ;
  591.    i = 0 ;
  592.    while (escape_test[i].in != *p)  i++ ;
  593.    if (i != ET_END)
  594.    {
  595.       /* in escape_test table */
  596.       *start_p = p + 1 ;
  597.       return escape_test[i].out ;
  598.    }
  599.  
  600.    if (isoctal(*p))
  601.    {
  602.       x = *p++ - '0' ;
  603.       if (isoctal(*p))
  604.       {
  605.      x = (x << 3) + *p++ - '0' ;
  606.      if (isoctal(*p))  x = (x << 3) + *p++ - '0' ;
  607.       }
  608.       *start_p = p ;
  609.       return x & 0xff ;
  610.    }
  611.  
  612.    if (*p == 0)     return '\\' ;
  613.  
  614.    if (*p++ == 'x')
  615.    {
  616.       if ((x = ctohex(*p)) == NOT_HEX)
  617.       {
  618.      *start_p  = p ;  return 'x' ; 
  619.       }
  620.  
  621.       /* look for another hex digit */
  622.       if ((xx = ctohex(*++p)) != NOT_HEX)
  623.       {
  624.      x = (x<<4) + xx ; p++ ; 
  625.       }
  626.  
  627.       *start_p = p ; return x ;
  628.    }
  629.  
  630.    /* anything else \c -> c */
  631.    *start_p = p ;
  632.    return *(unsigned char *) (p - 1) ;
  633. }
  634.  
  635.