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. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * @(#)rxp.c 8.1 (Berkeley) 5/31/93
34 * $FreeBSD: src/games/quiz/rxp.c,v 1.5 1999/12/12 02:29:54 billf Exp $
35 * $DragonFly: src/games/quiz/rxp.c,v 1.4 2005/04/25 16:10:24 liamfoy Exp $
39 * regular expression parser
41 * external functions and return values are:
44 * FALSE parse failure; error message will be in char rxperr[]
46 * {...} optional pattern, equialent to [...|]
48 * [...] pattern delimiters
51 * TRUE string s matches compiled pattern
52 * FALSE match failure or regexp error
55 * char * reverse-engineered regular expression string
62 /* regexp tokens, arg */
63 #define LIT (-1) /* literal character, char */
64 #define SOT (-2) /* start text anchor, - */
65 #define EOT (-3) /* end text anchor, - */
66 #define GRP_S (-4) /* start alternate grp, ptr_to_end */
67 #define GRP_E (-5) /* end group, - */
68 #define ALT_S (-6) /* alternate starts, ptr_to_next */
69 #define ALT_E (-7) /* alternate ends, - */
70 #define END (-8) /* end of regexp, - */
72 typedef short Rxp_t
; /* type for regexp tokens */
74 static Rxp_t rxpbuf
[RXP_LINE_SZ
]; /* compiled regular expression buffer */
75 char rxperr
[128]; /* parser error message */
77 static int rxp__compile (char *, int);
78 static char *rxp__expand (int);
79 static int rxp__match (char *, int, Rxp_t
*, Rxp_t
*, char *);
84 return (rxp__compile(s
, TRUE
));
88 rxp__compile(char *s
, int first
)
100 *rp
++ = SOT
; /* auto-anchor: pat is really ^pat$ */
101 *rp
++ = GRP_S
; /* auto-group: ^pat$ is really ^[pat]$ */
108 if (rp
- rxpbuf
>= RXP_LINE_SZ
- 4) {
109 (void)snprintf(rxperr
, sizeof(rxperr
),
110 "regular expression too long %s", s
);
113 if (*sp
== ':' && !esc
)
130 if ((err
= rxp__compile(s
, FALSE
)) != TRUE
)
133 *grp_ptr
= rp
- rxpbuf
;
139 *alt_ptr
= rp
- rxpbuf
;
148 *alt_ptr
= rp
- rxpbuf
;
151 (void)snprintf(rxperr
, sizeof(rxperr
),
152 "unmatched alternator in regexp %s",
167 (void)snprintf(rxperr
, sizeof(rxperr
),
168 "unmatched alternator in regexp %s", s
);
172 *alt_ptr
= rp
- rxpbuf
;
174 *(rxpbuf
+ 2) = rp
- rxpbuf
;
181 * match string against compiled regular expression
186 return (rxp__match(s
, TRUE
, NULL
, NULL
, NULL
));
190 * jump to j_succ on successful alt match
191 * jump to j_fail on failed match
192 * reset sp to sp_fail on failed match
195 rxp__match(char *s
, int first
, Rxp_t
*j_succ
, Rxp_t
*j_fail
, char *sp_fail
)
208 while (rp
< rxpbuf
+ RXP_LINE_SZ
&& *rp
!= END
)
212 ch
= isascii(*rp
) && isupper(*rp
) ? tolower(*rp
) : *rp
;
232 grp_end
= rxpbuf
+ *rp
++;
236 if ((err
= rxp__match(sp
,
237 FALSE
, grp_end
, rxpbuf
+ *rp
++, sp
)) != TRUE
)
247 return (*rp
!= END
? FALSE
: TRUE
);
251 * Reverse engineer the regular expression, by picking first of all alternates.
256 return (rxp__expand(TRUE
));
260 rxp__expand(int first
)
262 static char buf
[RXP_LINE_SZ
/2];
272 while (rp
< rxpbuf
+ RXP_LINE_SZ
&& *rp
!= END
)
280 grp_ptr
= rxpbuf
+ *rp
;
282 if ((err
= rxp__expand(FALSE
)) == NULL
)