rxp.c revision 1.7
1 /* $NetBSD: rxp.c,v 1.7 1999/09/08 21:17:56 jsm Exp $ */ 2 3 /*- 4 * Copyright (c) 1991, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Jim R. Oldroyd at The Instruction Set and Keith Gabryelski at 9 * Commodore Business Machines. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. All advertising materials mentioning features or use of this software 20 * must display the following acknowledgement: 21 * This product includes software developed by the University of 22 * California, Berkeley and its contributors. 23 * 4. Neither the name of the University nor the names of its contributors 24 * may be used to endorse or promote products derived from this software 25 * without specific prior written permission. 26 * 27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 37 * SUCH DAMAGE. 38 */ 39 40 #include <sys/cdefs.h> 41 #ifndef lint 42 #if 0 43 static char sccsid[] = "@(#)rxp.c 8.1 (Berkeley) 5/31/93"; 44 #else 45 __RCSID("$NetBSD: rxp.c,v 1.7 1999/09/08 21:17:56 jsm Exp $"); 46 #endif 47 #endif /* not lint */ 48 49 /* 50 * regular expression parser 51 * 52 * external functions and return values are: 53 * rxp_compile(s) 54 * TRUE success 55 * FALSE parse failure; error message will be in char rxperr[] 56 * metas are: 57 * {...} optional pattern, equialent to [...|] 58 * | alternate pattern 59 * [...] pattern delimiters 60 * 61 * rxp_match(s) 62 * TRUE string s matches compiled pattern 63 * FALSE match failure or regexp error 64 * 65 * rxp_expand() 66 * char * reverse-engineered regular expression string 67 * NULL regexp error 68 */ 69 70 #include <stdio.h> 71 #include <ctype.h> 72 #include "quiz.h" 73 /* regexp tokens, arg */ 74 #define LIT (-1) /* literal character, char */ 75 #define SOT (-2) /* start text anchor, - */ 76 #define EOT (-3) /* end text anchor, - */ 77 #define GRP_S (-4) /* start alternate grp, ptr_to_end */ 78 #define GRP_E (-5) /* end group, - */ 79 #define ALT_S (-6) /* alternate starts, ptr_to_next */ 80 #define ALT_E (-7) /* alternate ends, - */ 81 #define END (-8) /* end of regexp, - */ 82 83 typedef short Rxp_t; /* type for regexp tokens */ 84 85 static Rxp_t rxpbuf[RXP_LINE_SZ]; /* compiled regular expression buffer */ 86 char rxperr[128]; /* parser error message */ 87 88 static int rxp__compile __P((const char *, int)); 89 static char *rxp__expand __P((int)); 90 static int rxp__match __P((const char *, int, Rxp_t *, Rxp_t *, const char *)); 91 92 int 93 rxp_compile(s) 94 const char * s; 95 { 96 return (rxp__compile(s, TRUE)); 97 } 98 99 static int 100 rxp__compile(s, first) 101 const char *s; 102 int first; 103 { 104 static Rxp_t *rp; 105 static const char *sp; 106 Rxp_t *grp_ptr; 107 Rxp_t *alt_ptr; 108 int esc, err; 109 110 esc = 0; 111 if (first) { 112 rp = rxpbuf; 113 sp = s; 114 *rp++ = SOT; /* auto-anchor: pat is really ^pat$ */ 115 *rp++ = GRP_S; /* auto-group: ^pat$ is really ^[pat]$ */ 116 *rp++ = 0; 117 } 118 *rp++ = ALT_S; 119 alt_ptr = rp; 120 *rp++ = 0; 121 for (; *sp; ++sp) { 122 if (rp - rxpbuf >= RXP_LINE_SZ - 4) { 123 (void)snprintf(rxperr, sizeof(rxperr), 124 "regular expression too long %s", s); 125 return (FALSE); 126 } 127 if (*sp == ':' && !esc) 128 break; 129 if (esc) { 130 *rp++ = LIT; 131 *rp++ = *sp; 132 esc = 0; 133 } 134 else switch (*sp) { 135 case '\\': 136 esc = 1; 137 break; 138 case '{': 139 case '[': 140 *rp++ = GRP_S; 141 grp_ptr = rp; 142 *rp++ = 0; 143 sp++; 144 if ((err = rxp__compile(s, FALSE)) != TRUE) 145 return (err); 146 *rp++ = GRP_E; 147 *grp_ptr = rp - rxpbuf; 148 break; 149 case '}': 150 case ']': 151 case '|': 152 *rp++ = ALT_E; 153 *alt_ptr = rp - rxpbuf; 154 if (*sp != ']') { 155 *rp++ = ALT_S; 156 alt_ptr = rp; 157 *rp++ = 0; 158 } 159 if (*sp != '|') { 160 if (*sp != ']') { 161 *rp++ = ALT_E; 162 *alt_ptr = rp - rxpbuf; 163 } 164 if (first) { 165 (void)snprintf(rxperr, sizeof(rxperr), 166 "unmatched alternator in regexp %s", 167 s); 168 return (FALSE); 169 } 170 return (TRUE); 171 } 172 break; 173 default: 174 *rp++ = LIT; 175 *rp++ = *sp; 176 esc = 0; 177 break; 178 } 179 } 180 if (!first) { 181 (void)snprintf(rxperr, sizeof(rxperr), 182 "unmatched alternator in regexp %s", s); 183 return (FALSE); 184 } 185 *rp++ = ALT_E; 186 *alt_ptr = rp - rxpbuf; 187 *rp++ = GRP_E; 188 *(rxpbuf + 2) = rp - rxpbuf; 189 *rp++ = EOT; 190 *rp = END; 191 return (TRUE); 192 } 193 194 /* 195 * match string against compiled regular expression 196 */ 197 int 198 rxp_match(s) 199 const char * s; 200 { 201 return (rxp__match(s, TRUE, NULL, NULL, NULL)); 202 } 203 204 static int 205 rxp__match(s, first, j_succ, j_fail, sp_fail) 206 const char *s; 207 int first; 208 Rxp_t *j_succ; /* jump here on successful alt match */ 209 Rxp_t *j_fail; /* jump here on failed match */ 210 const char *sp_fail; /* reset sp to here on failed match */ 211 { 212 static Rxp_t *rp; 213 static const char *sp; 214 int ch; 215 Rxp_t *grp_end = NULL; 216 int err; 217 218 if (first) { 219 rp = rxpbuf; 220 sp = s; 221 } 222 while (rp < rxpbuf + RXP_LINE_SZ && *rp != END) 223 switch(*rp) { 224 case LIT: 225 rp++; 226 ch = isascii(*rp) && isupper(*rp) ? tolower(*rp) : *rp; 227 if (ch != *sp++) { 228 rp = j_fail; 229 sp = sp_fail; 230 return (TRUE); 231 } 232 rp++; 233 break; 234 case SOT: 235 if (sp != s) 236 return (FALSE); 237 rp++; 238 break; 239 case EOT: 240 if (*sp != 0) 241 return (FALSE); 242 rp++; 243 break; 244 case GRP_S: 245 rp++; 246 grp_end = rxpbuf + *rp++; 247 break; 248 case ALT_S: 249 rp++; 250 if ((err = rxp__match(sp, 251 FALSE, grp_end, rxpbuf + *rp++, sp)) != TRUE) 252 return (err); 253 break; 254 case ALT_E: 255 rp = j_succ; 256 return (TRUE); 257 case GRP_E: 258 default: 259 return (FALSE); 260 } 261 return (*rp != END ? FALSE : TRUE); 262 } 263 264 /* 265 * Reverse engineer the regular expression, by picking first of all alternates. 266 */ 267 char * 268 rxp_expand() 269 { 270 return (rxp__expand(TRUE)); 271 } 272 273 static char * 274 rxp__expand(first) 275 int first; 276 { 277 static char buf[RXP_LINE_SZ/2]; 278 static Rxp_t *rp; 279 static char *bp; 280 Rxp_t *grp_ptr; 281 char *err; 282 283 if (first) { 284 rp = rxpbuf; 285 bp = buf; 286 } 287 while (rp < rxpbuf + RXP_LINE_SZ && *rp != END) 288 switch(*rp) { 289 case LIT: 290 rp++; 291 *bp++ = *rp++; 292 break; 293 case GRP_S: 294 rp++; 295 grp_ptr = rxpbuf + *rp; 296 rp++; 297 if ((err = rxp__expand(FALSE)) == NULL) 298 return (err); 299 rp = grp_ptr; 300 break; 301 case ALT_E: 302 return (buf); 303 case ALT_S: 304 rp++; 305 /* FALLTHROUGH */ 306 case SOT: 307 case EOT: 308 case GRP_E: 309 rp++; 310 break; 311 default: 312 return (NULL); 313 } 314 if (first) { 315 if (*rp != END) 316 return (NULL); 317 *bp = '\0'; 318 } 319 return (buf); 320 } 321
Indexes created Mon Sep 29 18:09:42 GMT 2025