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