2 * Copyright (c) 1991, 1993
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
6 * Jim R. Oldroyd at The Instruction Set and Keith Gabryelski at
7 * Commodore Business Machines.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by the University of
20 * California, Berkeley and its contributors.
21 * 4. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * @(#)rxp.c 8.1 (Berkeley) 5/31/93
38 * $FreeBSD: src/games/quiz/rxp.c,v 1.5 1999/12/12 02:29:54 billf Exp $
39 * $DragonFly: src/games/quiz/rxp.c,v 1.3 2003/11/12 14:53:54 eirikn Exp $
43 * regular expression parser
45 * external functions and return values are:
48 * FALSE parse failure; error message will be in char rxperr[]
50 * {...} optional pattern, equialent to [...|]
52 * [...] pattern delimiters
55 * TRUE string s matches compiled pattern
56 * FALSE match failure or regexp error
59 * char * reverse-engineered regular expression string
66 /* regexp tokens, arg */
67 #define LIT (-1) /* literal character, char */
68 #define SOT (-2) /* start text anchor, - */
69 #define EOT (-3) /* end text anchor, - */
70 #define GRP_S (-4) /* start alternate grp, ptr_to_end */
71 #define GRP_E (-5) /* end group, - */
72 #define ALT_S (-6) /* alternate starts, ptr_to_next */
73 #define ALT_E (-7) /* alternate ends, - */
74 #define END (-8) /* end of regexp, - */
76 typedef short Rxp_t; /* type for regexp tokens */
78 static Rxp_t rxpbuf[RXP_LINE_SZ]; /* compiled regular expression buffer */
79 char rxperr[128]; /* parser error message */
81 static int rxp__compile (char *, int);
82 static char *rxp__expand (int);
83 static int rxp__match (char *, int, Rxp_t *, Rxp_t *, char *);
89 return (rxp__compile(s, TRUE));
93 rxp__compile(s, first)
107 *rp++ = SOT; /* auto-anchor: pat is really ^pat$ */
108 *rp++ = GRP_S; /* auto-group: ^pat$ is really ^[pat]$ */
115 if (rp - rxpbuf >= RXP_LINE_SZ - 4) {
116 (void)snprintf(rxperr, sizeof(rxperr),
117 "regular expression too long %s", s);
120 if (*sp == ':' && !esc)
137 if ((err = rxp__compile(s, FALSE)) != TRUE)
140 *grp_ptr = rp - rxpbuf;
146 *alt_ptr = rp - rxpbuf;
155 *alt_ptr = rp - rxpbuf;
158 (void)snprintf(rxperr, sizeof(rxperr),
159 "unmatched alternator in regexp %s",
174 (void)snprintf(rxperr, sizeof(rxperr),
175 "unmatched alternator in regexp %s", s);
179 *alt_ptr = rp - rxpbuf;
181 *(rxpbuf + 2) = rp - rxpbuf;
188 * match string against compiled regular expression
194 return (rxp__match(s, TRUE, NULL, NULL, NULL));
198 rxp__match(s, first, j_succ, j_fail, sp_fail)
201 Rxp_t *j_succ; /* jump here on successful alt match */
202 Rxp_t *j_fail; /* jump here on failed match */
203 char *sp_fail; /* reset sp to here on failed match */
216 while (rp < rxpbuf + RXP_LINE_SZ && *rp != END)
220 ch = isascii(*rp) && isupper(*rp) ? tolower(*rp) : *rp;
240 grp_end = rxpbuf + *rp++;
244 if ((err = rxp__match(sp,
245 FALSE, grp_end, rxpbuf + *rp++, sp)) != TRUE)
255 return (*rp != END ? FALSE : TRUE);
259 * Reverse engineer the regular expression, by picking first of all alternates.
264 return (rxp__expand(TRUE));
271 static char buf[RXP_LINE_SZ/2];
281 while (rp < rxpbuf + RXP_LINE_SZ && *rp != END)
289 grp_ptr = rxpbuf + *rp;
291 if ((err = rxp__expand(FALSE)) == NULL)