rexp/rexp.c

   1
   2 /********************************************
   3 rexp.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: rexp.c,v $
  14  *Revision 1.3  1996/09/02 18:47:36  mike
  15  *Make ^* and ^+ syntax errors.
  16  *
  17  *Revision 1.2  1993/07/23 13:21:32  mike
  18  *cleanup rexp code
  19  *
  20  * Revision 1.1.1.1  1993/07/03  18:58:26  mike
  21  * move source to cvs
  22  *
  23  * Revision 3.4  1991/08/13  09:09:59  brennan
  24  * VERSION .9994
  25  *
  26  * Revision 3.3  91/08/04  15:45:03  brennan
  27  * no longer attempt to recover mem on failed REcompile
  28  * Its not worth the effort
  29  *
  30  * Revision 3.2  91/08/03  07:24:06  brennan
  31  * check for empty machine stack (missing operand) wasn't quite right
  32  *
  33  * Revision 3.1  91/06/07  10:33:16  brennan
  34  * VERSION 0.995
  35  *
  36  * Revision 1.7  91/06/05  08:58:47  brennan
  37  * change RE_free to free
  38  *
  39  * Revision 1.6  91/06/03  07:07:17  brennan
  40  * moved parser stacks inside REcompile
  41  * removed unnecessary copying
  42  *
  43 */
  44
  45 /*  op precedence  parser for regular expressions  */
  46
  47 #include  "rexp.h"
  48
  49
  50 /*  DATA   */
  51 int REerrno ;
  52 char *REerrlist[] =
  53 {(char *) 0,
  54  /* 1  */ "missing '('",
  55  /* 2  */ "missing ')'",
  56  /* 3  */ "bad class -- [], [^] or [",
  57  /* 4  */ "missing operand",
  58  /* 5  */ "resource exhaustion -- regular expression too large" ,
  59  /* 6  */ "syntax error ^* or ^+"
  60 } ;
  61 /* E5 is very unlikely to occur */
  62
  63
  64 /* This table drives the operator precedence parser */
  65 static  short  table[8][8]  =  {
  66
  67 /*        0   |   CAT   *   +   ?   (   )   */
  68 /* 0 */   {0,  L,  L,    L,  L,  L,  L,  E1},
  69 /* | */   {G,  G,  L,    L,  L,  L,  L,  G},
  70 /* CAT*/  {G,  G,  G,    L,  L,  L,  L,  G},
  71 /* * */   {G,  G,  G,    G,  G,  G, E7,  G},
  72 /* + */   {G,  G,  G,    G,  G,  G, E7,  G},
  73 /* ? */   {G,  G,  G,    G,  G,  G, E7,  G},
  74 /* ( */   {E2, L,  L,    L,  L,  L,  L,  EQ},
  75 /* ) */   {G , G,  G,    G,  G,  G,  E7,  G}     }   ;
  76
  77
  78 #define  STACKSZ   64
  79
  80
  81 static jmp_buf err_buf ;         /*  used to trap on error */
  82
  83 void
  84 RE_error_trap(x)
  85    int x ;
  86 {
  87    REerrno = x ;
  88    longjmp(err_buf, 1) ;
  89 }
  90
  91
  92 PTR
  93 REcompile(re)
  94    char *re ;
  95 {
  96    MACHINE m_stack[STACKSZ] ;
  97    struct op
  98    {
  99       int token ;
 100       int prec ;
 101    }
 102    op_stack[STACKSZ] ;
 103    register MACHINE *m_ptr ;
 104    register struct op *op_ptr ;
 105    register int t ;
 106
 107    /* do this first because it also checks if we have a
 108      run time stack */
 109    RE_lex_init(re) ;
 110
 111    if (*re == 0)
 112    {
 113       STATE *p = (STATE *) RE_malloc(sizeof(STATE)) ;
 114       p->type = M_ACCEPT ;
 115       return (PTR) p ;
 116    }
 117
 118    if (setjmp(err_buf))  return (PTR) 0 ;
 119    /* we used to try to recover memory left on machine stack ;
 120      but now m_ptr is in a register so it won't be right unless
 121      we force it out of a register which isn't worth the trouble */
 122
 123    /* initialize the stacks  */
 124    m_ptr = m_stack - 1 ;
 125    op_ptr = op_stack ;
 126    op_ptr->token = 0 ;
 127
 128    t = RE_lex(m_stack) ;
 129
 130    while (1)
 131    {
 132       switch (t)
 133       {
 134          case T_STR:
 135          case T_ANY:
 136          case T_U:
 137          case T_START:
 138          case T_END:
 139          case T_CLASS:
 140             m_ptr++ ;
 141             break ;
 142
 143          case 0:                /*  end of reg expr   */
 144             if (op_ptr->token == 0)
 145             {
 146                /*  done   */
 147                if (m_ptr == m_stack)  return (PTR) m_ptr->start ;
 148                else
 149                {
 150                   /* machines still on the stack  */
 151                   RE_panic("values still on machine stack") ;
 152                }
 153             }
 154
 155             /*  otherwise  fall  thru to default
 156              which is operator case  */
 157
 158          default:
 159
 160             if ((op_ptr->prec = table[op_ptr->token][t]) == G)
 161             {
 162                do
 163                {                /* op_pop   */
 164
 165                   if (op_ptr->token <= T_CAT)   /*binary op*/
 166                      m_ptr-- ;
 167                   /* if not enough values on machine stack
 168                    then we have a missing operand */
 169                   if (m_ptr < m_stack)  RE_error_trap(-E4) ;
 170
 171                   switch (op_ptr->token)
 172                   {
 173                      case T_CAT:
 174                         RE_cat(m_ptr, m_ptr + 1) ;
 175                         break ;
 176
 177                      case T_OR:
 178                         RE_or(m_ptr, m_ptr + 1) ;
 179                         break ;
 180
 181                      case T_STAR:
 182                         RE_close(m_ptr) ;
 183                         break ;
 184
 185                      case T_PLUS:
 186                         RE_poscl(m_ptr) ;
 187                         break ;
 188
 189                      case T_Q:
 190                         RE_01(m_ptr) ;
 191                         break ;
 192
 193                      default:
 194                         /*nothing on ( or ) */
 195                         break ;
 196                   }
 197
 198                   op_ptr-- ;
 199                }
 200                while (op_ptr->prec != L);
 201
 202                continue ;        /* back thru switch at top */
 203             }
 204
 205             if (op_ptr->prec < 0)
 206             {
 207                if (op_ptr->prec == E7)  RE_panic("parser returns E7") ;
 208                else  RE_error_trap(-op_ptr->prec) ;
 209             }
 210
 211             if (++op_ptr == op_stack + STACKSZ)
 212             {
 213                /* stack overflow */
 214                RE_error_trap(-E5) ;
 215             }
 216
 217             op_ptr->token = t ;
 218       }                         /* end of switch */
 219
 220       if (m_ptr == m_stack + (STACKSZ - 1))
 221       {
 222          /*overflow*/
 223          RE_error_trap(-E5) ;
 224       }
 225
 226       t = RE_lex(m_ptr + 1) ;
 227    }
 228 }
 229
 230
 231 /* getting here means a logic flaw or unforeseen case */
 232 void
 233 RE_panic(s)
 234    char *s ;
 235 {
 236    fprintf(stderr, "REcompile() - panic:  %s\n", s) ;
 237    exit(100) ;
 238 }