[unix-history] / usr / src / old / yacc / y4.c

#ifndef lint
static char sccsid[] = "@(#)y4.c	4.1	(Berkeley)	%G%";
#endif not lint

# include "dextern"

# define a amem
# define mem mem0
# define pa indgo
# define yypact temp1
# define greed tystate

int * ggreed = lkst[0].lset;
int * pgo = wsets[0].ws.lset;
int *yypgo = &nontrst[0].tvalue;

int maxspr = 0;  /* maximum spread of any entry */
int maxoff = 0;  /* maximum offset into a array */
int *pmem = mem;
int *maxa;
# define NOMORE -1000

int nxdb = 0;
int adb = 0;

callopt(){

	register i, *p, j, k, *q;

	/* read the arrays from tempfile and set parameters */

	if( (finput=fopen(TEMPNAME,"r")) == NULL ) error( "optimizer cannot open tempfile" );

	pgo[0] = 0;
	yypact[0] = 0;
	nstate = 0;
	nnonter = 0;
	for(;;){
		switch( gtnm() ){

		case '\n':
			yypact[++nstate] = (--pmem) - mem;
		case ',':
			continue;

		case '$':
			break;

		default:
			error( "bad tempfile" );
			}
		break;
		}

	yypact[nstate] = yypgo[0] = (--pmem) - mem;

	for(;;){
		switch( gtnm() ){

		case '\n':
			yypgo[++nnonter]= pmem-mem;
		case ',':
			continue;

		case EOF:
			break;

		default:
			error( "bad tempfile" );
			}
		break;
		}

	yypgo[nnonter--] = (--pmem) - mem;


	for( i=0; i<nstate; ++i ){

		k = 32000;
		j = 0;
		q = mem + yypact[i+1];
		for( p = mem + yypact[i]; p<q ; p += 2 ){
			if( *p > j ) j = *p;
			if( *p < k ) k = *p;
			}
		if( k <= j ){ /* nontrivial situation */
			/* temporarily, kill this for compatibility
			j -= k;  /* j is now the range */
			if( k > maxoff ) maxoff = k;
			}
		greed[i] = (yypact[i+1]-yypact[i]) + 2*j;
		if( j > maxspr ) maxspr = j;
		}

	/* initialize ggreed table */

	for( i=1; i<=nnonter; ++i ){
		ggreed[i] = 1;
		j = 0;
		/* minimum entry index is always 0 */
		q = mem + yypgo[i+1] -1;
		for( p = mem+yypgo[i]; p<q ; p += 2 ) {
			ggreed[i] += 2;
			if( *p > j ) j = *p;
			}
		ggreed[i] = ggreed[i] + 2*j;
		if( j > maxoff ) maxoff = j;
		}


	/* now, prepare to put the shift actions into the a array */

	for( i=0; i<ACTSIZE; ++i ) a[i] = 0;
	maxa = a;

	for( i=0; i<nstate; ++i ) {
		if( greed[i]==0 && adb>1 ) fprintf( ftable, "State %d: null\n", i );
		pa[i] = YYFLAG1;
		}

	while( (i = nxti()) != NOMORE ) {
		if( i >= 0 ) stin(i);
		else gin(-i);

		}

	if( adb>2 ){ /* print a array */
		for( p=a; p <= maxa; p += 10){
			fprintf( ftable, "%4d  ", p-a );
			for( i=0; i<10; ++i ) fprintf( ftable, "%4d  ", p[i] );
			fprintf( ftable, "\n" );
			}
		}
	/* write out the output appropriate to the language */

	aoutput();

	osummary();
	ZAPFILE(TEMPNAME);
	}

gin(i){

	register *p, *r, *s, *q1, *q2;

	/* enter gotos on nonterminal i into array a */

	ggreed[i] = 0;

	q2 = mem+ yypgo[i+1] - 1;
	q1 = mem + yypgo[i];

	/* now, find a place for it */

	for( p=a; p < &a[ACTSIZE]; ++p ){
		if( *p ) continue;
		for( r=q1; r<q2; r+=2 ){
			s = p + *r +1;
			if( *s ) goto nextgp;
			if( s > maxa ){
				if( (maxa=s) > &a[ACTSIZE] ) error( "a array overflow" );
				}
			}
		/* we have found a spot */

		*p = *q2;
		if( p > maxa ){
			if( (maxa=p) > &a[ACTSIZE] ) error( "a array overflow" );
			}
		for( r=q1; r<q2; r+=2 ){
			s = p + *r + 1;
			*s = r[1];
			}

		pgo[i] = p-a;
		if( adb>1 ) fprintf( ftable, "Nonterminal %d, entry at %d\n" , i, pgo[i] );
		goto nextgi;

		nextgp:  ;
		}

	error( "cannot place goto %d\n", i );

	nextgi:  ;
	}

stin(i){
	register *r, *s, n, flag, j, *q1, *q2;

	greed[i] = 0;

	/* enter state i into the a array */

	q2 = mem+yypact[i+1];
	q1 = mem+yypact[i];
	/* find an acceptable place */

	for( n= -maxoff; n<ACTSIZE; ++n ){

		flag = 0;
		for( r = q1; r < q2; r += 2 ){
			if( (s = *r + n + a ) < a ) goto nextn;
			if( *s == 0 ) ++flag;
			else if( *s != r[1] ) goto nextn;
			}

		/* check that the position equals another only if the states are identical */

		for( j=0; j<nstate; ++j ){
			if( pa[j] == n ) {
				if( flag ) goto nextn;  /* we have some disagreement */
				if( yypact[j+1] + yypact[i] == yypact[j] + yypact[i+1] ){
					/* states are equal */
					pa[i] = n;
					if( adb>1 ) fprintf( ftable, "State %d: entry at %d equals state %d\n",
						i, n, j );
					return;
					}
				goto nextn;  /* we have some disagreement */
				}
			}

		for( r = q1; r < q2; r += 2 ){
			if( (s = *r + n + a ) >= &a[ACTSIZE] ) error( "out of space in optimizer a array" );
			if( s > maxa ) maxa = s;
			if( *s != 0 && *s != r[1] ) error( "clobber of a array, pos'n %d, by %d", s-a, r[1] );
			*s = r[1];
			}
		pa[i] = n;
		if( adb>1 ) fprintf( ftable, "State %d: entry at %d\n", i, pa[i] );
		return;

		nextn:  ;
		}

	error( "Error; failure to place state %d\n", i );

	}

nxti(){ /* finds the next i */
	register i, max, maxi;

	max = 0;

	for( i=1; i<= nnonter; ++i ) if( ggreed[i] >= max ){
		max = ggreed[i];
		maxi = -i;
		}

	for( i=0; i<nstate; ++i ) if( greed[i] >= max ){
		max = greed[i];
		maxi = i;
		}

	if( nxdb ) fprintf( ftable, "nxti = %d, max = %d\n", maxi, max );
	if( max==0 ) return( NOMORE );
	else return( maxi );
	}

osummary(){
	/* write summary */

	register i, *p;

	if( foutput == NULL ) return;
	i=0;
	for( p=maxa; p>=a; --p ) {
		if( *p == 0 ) ++i;
		}

	fprintf( foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
		pmem-mem+1, MEMSIZE, maxa-a+1, ACTSIZE );
	fprintf( foutput, "%d table entries, %d zero\n", (maxa-a)+1, i );
	fprintf( foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff );

	}

aoutput(){ /* this version is for C */


	/* write out the optimized parser */

	fprintf( ftable, "# define YYLAST %d\n", maxa-a+1 );

	arout( "yyact", a, (maxa-a)+1 );
	arout( "yypact", pa, nstate );
	arout( "yypgo", pgo, nnonter+1 );

	}

arout( s, v, n ) char *s; int *v, n; {

	register i;

	fprintf( ftable, "short %s[]={\n", s );
	for( i=0; i<n; ){
		if( i%10 == 0 ) fprintf( ftable, "\n" );
		fprintf( ftable, "%4d", v[i] );
		if( ++i == n ) fprintf( ftable, " };\n" );
		else fprintf( ftable, "," );
		}
	}


gtnm(){

	register s, val, c;

	/* read and convert an integer from the standard input */
	/* return the terminating character */
	/* blanks, tabs, and newlines are ignored */

	s = 1;
	val = 0;

	while( (c=getc(finput)) != EOF ){
		if( isdigit(c) ){
			val = val * 10 + c - '0';
			}
		else if ( c == '-' ) s = -1;
		else break;
		}

	*pmem++ = s*val;
	if( pmem > &mem[MEMSIZE] ) error( "out of space" );
	return( c );

	}
Commit	Line	Data
39d276e4 RH	1	#ifndef lint
	2	static char sccsid[] = "@(#)y4.c 4.1 (Berkeley) %G%";
	3	#endif not lint
	4
	5	# include "dextern"
	6
	7	# define a amem
	8	# define mem mem0
	9	# define pa indgo
	10	# define yypact temp1
	11	# define greed tystate
	12
	13	int * ggreed = lkst[0].lset;
	14	int * pgo = wsets[0].ws.lset;
	15	int *yypgo = &nontrst[0].tvalue;
	16
	17	int maxspr = 0; /* maximum spread of any entry */
	18	int maxoff = 0; /* maximum offset into a array */
	19	int *pmem = mem;
	20	int *maxa;
	21	# define NOMORE -1000
	22
	23	int nxdb = 0;
	24	int adb = 0;
	25
	26	callopt(){
	27
	28	register i, p, j, k, q;
	29
	30	/* read the arrays from tempfile and set parameters */
	31
	32	if( (finput=fopen(TEMPNAME,"r")) == NULL ) error( "optimizer cannot open tempfile" );
	33
	34	pgo[0] = 0;
	35	yypact[0] = 0;
	36	nstate = 0;
	37	nnonter = 0;
	38	for(;;){
	39	switch( gtnm() ){
	40
	41	case '\n':
	42	yypact[++nstate] = (--pmem) - mem;
	43	case ',':
	44	continue;
	45
	46	case '$':
	47	break;
	48
	49	default:
	50	error( "bad tempfile" );
	51	}
	52	break;
	53	}
	54
	55	yypact[nstate] = yypgo[0] = (--pmem) - mem;
	56
	57	for(;;){
	58	switch( gtnm() ){
	59
	60	case '\n':
	61	yypgo[++nnonter]= pmem-mem;
	62	case ',':
	63	continue;
	64
65	case EOF:
66	break;
67
68	default:
69	error( "bad tempfile" );
70	}
71	break;
72	}
73
74	yypgo[nnonter--] = (--pmem) - mem;
75
76
77
78	for( i=0; i<nstate; ++i ){
79
80	k = 32000;
81	j = 0;
82	q = mem + yypact[i+1];
83	for( p = mem + yypact[i]; p<q ; p += 2 ){
84	if( p > j ) j = p;
85	if( p < k ) k = p;
86	}
87	if( k <= j ){ /* nontrivial situation */
88	/* temporarily, kill this for compatibility
89	j -= k; /* j is now the range */
90	if( k > maxoff ) maxoff = k;
91	}
92	greed[i] = (yypact[i+1]-yypact[i]) + 2*j;
93	if( j > maxspr ) maxspr = j;
94	}
95
96	/* initialize ggreed table */
97
98	for( i=1; i<=nnonter; ++i ){
99	ggreed[i] = 1;
100	j = 0;
101	/* minimum entry index is always 0 */
102	q = mem + yypgo[i+1] -1;
103	for( p = mem+yypgo[i]; p<q ; p += 2 ) {
104	ggreed[i] += 2;
105	if( p > j ) j = p;
106	}
107	ggreed[i] = ggreed[i] + 2*j;
108	if( j > maxoff ) maxoff = j;
109	}
110
111
112	/* now, prepare to put the shift actions into the a array */
113
114	for( i=0; i<ACTSIZE; ++i ) a[i] = 0;
115	maxa = a;
116
117	for( i=0; i<nstate; ++i ) {
118	if( greed[i]==0 && adb>1 ) fprintf( ftable, "State %d: null\n", i );
119	pa[i] = YYFLAG1;
120	}
121
122	while( (i = nxti()) != NOMORE ) {
123	if( i >= 0 ) stin(i);
124	else gin(-i);
125
126	}
127
128	if( adb>2 ){ /* print a array */
129	for( p=a; p <= maxa; p += 10){
130	fprintf( ftable, "%4d ", p-a );
131	for( i=0; i<10; ++i ) fprintf( ftable, "%4d ", p[i] );
132	fprintf( ftable, "\n" );
133	}
134	}
135	/* write out the output appropriate to the language */
136
137	aoutput();
138
139	osummary();
140	ZAPFILE(TEMPNAME);
141	}
142
143	gin(i){
144
145	register p, r, s, q1, *q2;
146
147	/* enter gotos on nonterminal i into array a */
148
149	ggreed[i] = 0;
150
151	q2 = mem+ yypgo[i+1] - 1;
152	q1 = mem + yypgo[i];
153
154	/* now, find a place for it */
155
156	for( p=a; p < &a[ACTSIZE]; ++p ){
157	if( *p ) continue;
158	for( r=q1; r<q2; r+=2 ){
159	s = p + *r +1;
160	if( *s ) goto nextgp;
161	if( s > maxa ){
162	if( (maxa=s) > &a[ACTSIZE] ) error( "a array overflow" );
163	}
164	}
165	/* we have found a spot */
166
167	p = q2;
168	if( p > maxa ){
169	if( (maxa=p) > &a[ACTSIZE] ) error( "a array overflow" );
170	}
171	for( r=q1; r<q2; r+=2 ){
172	s = p + *r + 1;
173	*s = r[1];
174	}
175
176	pgo[i] = p-a;
177	if( adb>1 ) fprintf( ftable, "Nonterminal %d, entry at %d\n" , i, pgo[i] );
178	goto nextgi;
179
180	nextgp: ;
181	}
182
183	error( "cannot place goto %d\n", i );
184
185	nextgi: ;
186	}
187
188	stin(i){
189	register r, s, n, flag, j, q1, q2;
190
191	greed[i] = 0;
192
193	/* enter state i into the a array */
194
195	q2 = mem+yypact[i+1];
196	q1 = mem+yypact[i];
197	/* find an acceptable place */
198
199	for( n= -maxoff; n<ACTSIZE; ++n ){
200
201	flag = 0;
202	for( r = q1; r < q2; r += 2 ){
203	if( (s = *r + n + a ) < a ) goto nextn;
204	if( *s == 0 ) ++flag;
205	else if( *s != r[1] ) goto nextn;
206	}
207
208	/* check that the position equals another only if the states are identical */
209
210	for( j=0; j<nstate; ++j ){
211	if( pa[j] == n ) {
212	if( flag ) goto nextn; /* we have some disagreement */
213	if( yypact[j+1] + yypact[i] == yypact[j] + yypact[i+1] ){
214	/* states are equal */
215	pa[i] = n;
216	if( adb>1 ) fprintf( ftable, "State %d: entry at %d equals state %d\n",
217	i, n, j );
218	return;
219	}
220	goto nextn; /* we have some disagreement */
221	}
222	}
223
224	for( r = q1; r < q2; r += 2 ){
225	if( (s = *r + n + a ) >= &a[ACTSIZE] ) error( "out of space in optimizer a array" );
226	if( s > maxa ) maxa = s;
227	if( s != 0 && s != r[1] ) error( "clobber of a array, pos'n %d, by %d", s-a, r[1] );
228	*s = r[1];
229	}
230	pa[i] = n;
231	if( adb>1 ) fprintf( ftable, "State %d: entry at %d\n", i, pa[i] );
232	return;
233
234	nextn: ;
235	}
236
237	error( "Error; failure to place state %d\n", i );
238
239	}
240
241	nxti(){ /* finds the next i */
242	register i, max, maxi;
243
244	max = 0;
245
246	for( i=1; i<= nnonter; ++i ) if( ggreed[i] >= max ){
247	max = ggreed[i];
248	maxi = -i;
249	}
250
251	for( i=0; i<nstate; ++i ) if( greed[i] >= max ){
252	max = greed[i];
253	maxi = i;
254	}
255
256	if( nxdb ) fprintf( ftable, "nxti = %d, max = %d\n", maxi, max );
257	if( max==0 ) return( NOMORE );
258	else return( maxi );
259	}
260
261	osummary(){
262	/* write summary */
263
264	register i, *p;
265
266	if( foutput == NULL ) return;
267	i=0;
268	for( p=maxa; p>=a; --p ) {
269	if( *p == 0 ) ++i;
270	}
271
272	fprintf( foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
273	pmem-mem+1, MEMSIZE, maxa-a+1, ACTSIZE );
274	fprintf( foutput, "%d table entries, %d zero\n", (maxa-a)+1, i );
275	fprintf( foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff );
276
277	}
278
279	aoutput(){ /* this version is for C */
280
281
282	/* write out the optimized parser */
283
284	fprintf( ftable, "# define YYLAST %d\n", maxa-a+1 );
285
286	arout( "yyact", a, (maxa-a)+1 );
287	arout( "yypact", pa, nstate );
288	arout( "yypgo", pgo, nnonter+1 );
289
290	}
291
292	arout( s, v, n ) char s; int v, n; {
293
294	register i;
295
296	fprintf( ftable, "short %s[]={\n", s );
297	for( i=0; i<n; ){
298	if( i%10 == 0 ) fprintf( ftable, "\n" );
299	fprintf( ftable, "%4d", v[i] );
300	if( ++i == n ) fprintf( ftable, " };\n" );
301	else fprintf( ftable, "," );
302	}
303	}
304
305
306	gtnm(){
307
308	register s, val, c;
309
310	/* read and convert an integer from the standard input */
311	/* return the terminating character */
312	/* blanks, tabs, and newlines are ignored */
313
314	s = 1;
315	val = 0;
316
317	while( (c=getc(finput)) != EOF ){
318	if( isdigit(c) ){
319	val = val * 10 + c - '0';
320	}
321	else if ( c == '-' ) s = -1;
322	else break;
323	}
324
325	pmem++ = sval;
326	if( pmem > &mem[MEMSIZE] ) error( "out of space" );
327	return( c );
328
329	}