rexp/rexp1.c

   1
   2 /********************************************
   3 rexp1.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: rexp1.c,v $
  14  * Revision 1.3  1993/07/24  17:55:10  mike
  15  * more cleanup
  16  *
  17  * Revision 1.2  1993/07/23  13:21:41  mike
  18  * cleanup rexp code
  19  *
  20  * Revision 1.1.1.1  1993/07/03  18:58:27  mike
  21  * move source to cvs
  22  *
  23  * Revision 3.4  1992/02/20  16:08:12  brennan
  24  * change new_TWO() to work around sun acc bug
  25  *
  26  * Revision 3.3  91/10/29  10:54:01  brennan
  27  * SIZE_T
  28  *
  29  * Revision 3.2  91/08/13  09:10:11  brennan
  30  * VERSION .9994
  31  *
  32  * Revision 3.1  91/06/07  10:33:22  brennan
  33  * VERSION 0.995
  34  *
  35 */
  36
  37 /*  re machine  operations  */
  38
  39 #include  "rexp.h"
  40
  41 static void PROTO(new_TWO, (int, MACHINE *)) ;
  42
  43
  44
  45 /* initialize a two state machine */
  46 static void
  47 new_TWO(type, mp)
  48    int type ;
  49    MACHINE *mp ;                 /* init mp-> */
  50 {
  51    mp->start = (STATE *) RE_malloc(2 * STATESZ) ;
  52    mp->stop = mp->start + 1 ;
  53    mp->start->type = type ;
  54    mp->stop->type = M_ACCEPT ;
  55 }
  56
  57 /*  build a machine that recognizes any  */
  58 MACHINE
  59 RE_any()
  60 {
  61    MACHINE x ;
  62
  63    new_TWO(M_ANY, &x) ;
  64    return x ;
  65 }
  66
  67 /*  build a machine that recognizes the start of string  */
  68 MACHINE
  69 RE_start()
  70 {
  71    MACHINE x ;
  72
  73    new_TWO(M_START, &x) ;
  74    return x ;
  75 }
  76
  77 MACHINE
  78 RE_end()
  79 {
  80    MACHINE x ;
  81
  82    new_TWO(M_END, &x) ;
  83    return x ;
  84 }
  85
  86 /*  build a machine that recognizes a class  */
  87 MACHINE
  88 RE_class(bvp)
  89    BV *bvp ;
  90 {
  91    MACHINE x ;
  92
  93    new_TWO(M_CLASS, &x) ;
  94    x.start->data.bvp = bvp ;
  95    return x ;
  96 }
  97
  98 MACHINE
  99 RE_u()
 100 {
 101    MACHINE x ;
 102
 103    new_TWO(M_U, &x) ;
 104    return x ;
 105 }
 106
 107 MACHINE
 108 RE_str(str, len)
 109    char *str ;
 110    unsigned len ;
 111 {
 112    MACHINE x ;
 113
 114    new_TWO(M_STR, &x) ;
 115    x.start->len = len ;
 116    x.start->data.str = str ;
 117    return x ;
 118 }
 119
 120
 121 /*  replace m and n by a machine that recognizes  mn   */
 122 void
 123 RE_cat(mp, np)
 124    MACHINE *mp, *np ;
 125 {
 126    unsigned sz1, sz2, sz ;
 127
 128    sz1 = mp->stop - mp->start ;
 129    sz2 = np->stop - np->start + 1 ;
 130    sz = sz1 + sz2 ;
 131
 132    mp->start = (STATE *) RE_realloc(mp->start, sz * STATESZ) ;
 133    mp->stop = mp->start + (sz - 1) ;
 134    memcpy(mp->start + sz1, np->start, sz2 * STATESZ) ;
 135    free(np->start) ;
 136 }
 137
 138  /*  replace m by a machine that recognizes m|n  */
 139
 140 void
 141 RE_or(mp, np)
 142    MACHINE *mp, *np ;
 143 {
 144    register STATE *p ;
 145    unsigned szm, szn ;
 146
 147    szm = mp->stop - mp->start + 1 ;
 148    szn = np->stop - np->start + 1 ;
 149
 150    p = (STATE *) RE_malloc((szm + szn + 1) * STATESZ) ;
 151    memcpy(p + 1, mp->start, szm * STATESZ) ;
 152    free(mp->start) ;
 153    mp->start = p ;
 154    (mp->stop = p + szm + szn)->type = M_ACCEPT ;
 155    p->type = M_2JA ;
 156    p->data.jump = szm + 1 ;
 157    memcpy(p + szm + 1, np->start, szn * STATESZ) ;
 158    free(np->start) ;
 159    (p += szm)->type = M_1J ;
 160    p->data.jump = szn ;
 161 }
 162
 163 /*  UNARY  OPERATIONS     */
 164
 165 /*  replace m by m*   */
 166
 167 void
 168 RE_close(mp)
 169    MACHINE *mp ;
 170 {
 171    register STATE *p ;
 172    unsigned sz ;
 173
 174    sz = mp->stop - mp->start + 1 ;
 175    p = (STATE *) RE_malloc((sz + 2) * STATESZ) ;
 176    memcpy(p + 1, mp->start, sz * STATESZ) ;
 177    free(mp->start) ;
 178    mp->start = p ;
 179    mp->stop = p + (sz + 1) ;
 180    p->type = M_2JA ;
 181    p->data.jump = sz + 1 ;
 182    (p += sz)->type = M_2JB ;
 183    p->data.jump = -(sz - 1) ;
 184    (p + 1)->type = M_ACCEPT ;
 185 }
 186
 187 /*  replace m  by  m+  (positive closure)   */
 188
 189 void
 190 RE_poscl(mp)
 191    MACHINE *mp ;
 192 {
 193    register STATE *p ;
 194    unsigned sz ;
 195
 196    sz = mp->stop - mp->start + 1 ;
 197    mp->start = p = (STATE *) RE_realloc(mp->start, (sz + 1) * STATESZ) ;
 198    mp->stop = p + sz ;
 199    p += --sz ;
 200    p->type = M_2JB ;
 201    p->data.jump = -sz ;
 202    (p + 1)->type = M_ACCEPT ;
 203 }
 204
 205 /* replace  m  by  m? (zero or one)  */
 206
 207 void
 208 RE_01(mp)
 209    MACHINE *mp ;
 210 {
 211    unsigned sz ;
 212    register STATE *p ;
 213
 214    sz = mp->stop - mp->start + 1 ;
 215    p = (STATE *) RE_malloc((sz + 1) * STATESZ) ;
 216    memcpy(p + 1, mp->start, sz * STATESZ) ;
 217    free(mp->start) ;
 218    mp->start = p ;
 219    mp->stop = p + sz ;
 220    p->type = M_2JB ;
 221    p->data.jump = sz ;
 222 }
 223
 224 /*===================================
 225 MEMORY  ALLOCATION
 226  *==============================*/
 227
 228
 229 PTR
 230 RE_malloc(sz)
 231    unsigned sz ;
 232 {
 233    register PTR p ;
 234
 235    if (!(p = malloc(sz)))  RE_error_trap(MEMORY_FAILURE) ;
 236    return p ;
 237 }
 238
 239 PTR
 240 RE_realloc(p, sz)
 241    register PTR p ;
 242    unsigned sz ;
 243 {
 244    if (!(p = realloc(p, sz)))  RE_error_trap(MEMORY_FAILURE) ;
 245    return p ;
 246 }