1 /*-
2 * Copyright (c) 1979, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.proprietary.c%
6 */
7
8 #ifndef lint
9 static char copyright[] =
10 "@(#) Copyright (c) 1979, 1993\n\
11 The Regents of the University of California. All rights reserved.\n";
12 #endif /* not lint */
13
14 #ifndef lint
15 static char sccsid[] = "@(#)ey1.c 8.1 (Berkeley) 06/06/93";
16 #endif /* not lint */
17
18 # include "ey.h"
19 /* * * * * e y a c c * * * * */
20
21 /**** NB -----
22 *
23 * This version of yacc, known as "eyacc" has been slightly but
24 * importantly modified to allow error recovery in the UNIX Pascal
25 * translator "pi" and also in "pix".
26 *
27 * Changes here include:
28 *
29 * 1) Enumeration of test actions when "error" is an input token.
30 *
31 * 2) Change to the encoding of the action entries. Test entries
32 * are encoded as the arithmetic inverse of the symbol being tested
33 * for. This is an optimization that makes the parser run at the
34 * same speed even though, with error productions and enumerated
35 * lookaheads, it would normally be much slower. Of course the
36 * same thing could be done to the regular yacc...
37 *
38 * 3) Different table sizes
39 *
40 * 4) Recognizes form feeds
41 *
42 * 5) Also most of the numbers for the sizes of the tables have been
43 * increased, to an extent to allow for "eyacc"ing of the Pascal grammar
44 * and of a grammar which I have for "EUCLID".
45 *
46 * There seem to be subtle dependencies between the various magic
47 * numbers... I found some of them but to be safe most of the limits
48 * are very generous... for this reason "eyacc" will most likely
49 * have to run separate i/d... no matter.
50 *
51 * Bill Joy
52 * Computer Science Division
53 * EECS Department
54 * University of California, Berkeley
55 * Berkeley, California 94704
56 *
57 * Office: (415) 642-4948
58 * Home: (415) 524-4510
59 ****/
60
61 /* features to be fixed up ...
62
63 *** Print estimate of total space needed for parser
64 *** Either list inputs on y.output, or list empty prdn's in states
65 *** Mention nonterms not used (or, rules. not reduced) as nonfatal error
66 *** Output states where conflicts were found by default on y.output
67 *** Engage in newspeak: production=>grammar rules, term=>token, etc.
68 *** handle # define, #ifdef, etc., in yacc actions, %{ %}
69 */
70
71 /* new features to be added
72
73 *** reductions by single productions ( by request )
74 *** follow sets for start symbol
75 *** option to only do slr(1)
76 *** easily changed array names on output
77 *** allocate core, rather than predefined
78 *** input controlled by a grammar
79 *** support multiple choices for conflicts
80 *** better conflict diagnostics
81 */
82
83 extern char *symnam();
84
main(argc,argv)85 main(argc,argv) int argc; char *argv[]; {
86 auto int n;
87
88 setup(argc,argv); /* initialize and read productions */
89 tbitset = (nterms+16)/16;
90 cpres(); /* make table of which productions yield a given nonterminal */
91 cempty(); /* make a table of which nonterminals can match the empty string */
92 cpfir(); /* make a table of e free first lists */
93 stagen(); /* generate the states */
94 output(); /* write the states and the tables */
95 go2out();
96 summary();
97 exit(0);
98 }
99
settty()100 settty()
101 /* sets the output file to y.output */
102 {
103 cflush( foutput ); /* a bit of a cheat */
104 cout = foutput;
105 }
106
settab()107 settab(){ /* sets the output file to y.tab.c */
108
109 cflush( ftable );
110 cout = ftable;
111 }
112
chcopy(p,q)113 char *chcopy( p, q ) char *p, *q; {
114 /* copies string q into p, returning next free char ptr */
115 while( *p = *q++ ) ++p;
116 return( p );
117 }
118
writem(pp)119 char *writem(pp) struct item *pp; { /* creates output string for item pointed to by pp */
120 int i,*p;
121 static char sarr[100];
122 char *q;
123
124 for( p=pp->pitem; *p>0 ; ++p ) ;
125 p = prdptr[-*p];
126 q = chcopy( sarr, nontrst[*p-NTBASE].name );
127 q = chcopy( q, " : " );
128
129 for(;;){
130 *q++ = ++p==(pp->pitem) ? '_' : ' ';
131 if((i = *p) <= 0) break;
132 q = chcopy( q, symnam(i) );
133 }
134
135 *q = '\0' ;
136 return( sarr );
137 }
138
symnam(i)139 char *symnam(i){ /* return a pointer to the name of symbol i */
140 char *cp;
141
142 cp = (i>=NTBASE) ? nontrst[i-NTBASE].name : trmset[i].name ;
143 if( *cp == ' ' ) ++cp;
144 return( cp );
145 }
146
summary()147 summary(){ /* output the summary on the tty */
148
149 int i, s, *pn;
150
151
152 if( !rflag ){
153 settab();
154 fprintf( cout , "\nint nterms %d;",nterms);
155 fprintf( cout , "\nint nnonter %d;", nnonter);
156 fprintf( cout , "\nint nstate %d;", nstate);
157 fprintf( cout , "\nchar *yysterm[] {");
158 for (i=1;i<=nterms;i++) if( trmset[i].value >= 0400 ) fprintf( cout , "\n\"%s\",",symnam(i));
159 fprintf( cout , "\n0 };\n" );
160 fprintf( cout , "\nchar *yysnter[] {");
161 for (i=0;i<nnonter;i++) fprintf( cout , "\n\"%s\",",nontrst[i].name);
162 fprintf( cout , "\n\"%s\" };\n",nontrst[nnonter].name);
163 }
164
165 settty();
166 fprintf( cout , "\n%d/%d terminals, %d/%d nonterminals\n", nterms, tlim,
167 nnonter, ntlim );
168 fprintf( cout , "%d/%d grammar rules, %d/%d states\n", nprod, prdlim, nstate, stsize );
169 fprintf( cout , "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf );
170 pn = (int *)pstate[nstate+1];
171 fprintf( cout , "%d/%d working sets used\n", zzcwset, wssize );
172 fprintf( cout , "memory: states,etc. %d/%d, parser %d/%d\n", pn-mem0, memsiz,
173 memact, actsiz );
174 fprintf( cout , "%d/%d distinct lookahead sets\n", nlset, lsetsz );
175 fprintf( cout , "%d extra closures\n", zzclose - 2*nstate );
176 fprintf( cout , "%d action entries\n", zzacent );
177 fprintf( cout , "%d action entries saved through merging %d states\n",zzacsave,zznsave);
178 fprintf( cout , "%d goto entries\n", zzgoent );
179 fprintf( cout , "%d entries saved by goto default\n", zzgobest );
180 fprintf( cout , "%d lookahead sets saved\n", savedlook);
181 if( zzsrconf!=0 || zzrrconf!=0 ){
182 cflush( errfileno );
183 cout = errfileno;
184 fprintf( cout , "\nconflicts: ");
185 if( zzsrconf )fprintf( cout , "%d shift/reduce" , zzsrconf );
186 if( zzsrconf && zzrrconf )fprintf( cout , ", " );
187 if( zzrrconf )fprintf( cout , "%d reduce/reduce" , zzrrconf );
188 fprintf( cout , "\n" );
189 }
190 }
191
error(s,a1)192 error(s,a1){ /* write out error comment */
193
194 int c;
195 ++nerrors;
196 cflush( errfileno );
197 cout = errfileno; /* set output to tty */
198 fprintf( cout , "\n fatal error: ");
199 fprintf( cout , s,a1);
200 fprintf( cout , ", line %d\n", lineno );
201 if( !fatfl ) return;
202 summary();
203 cexit(1);
204 }
205
arrset(s)206 arrset(s) char s[]; {
207 fprintf( cout , "\nint %s[] {0", s );
208 arrndx = 1;
209 }
210
arrval(n)211 arrval(n){
212 fprintf( cout , ",%d",n);
213 if( (++arrndx%10) == 0 ) fprintf( cout , "\n");
214 }
215
arrdone()216 arrdone(){
217 fprintf( cout , ",-1};\n");
218 }
219
copy(v)220 copy(v) char *v; { /* copy ctokn to v */
221 char *p;
222
223 p=ctokn;
224 while( *v++ = *p++ );
225 }
226
compare(v)227 compare(v) char *v; { /* compare ctokn with v */
228 char *p;
229
230 for( p=ctokn; ; ++p ){
231 if( *p != *v++ ) return( 0 );
232 if( *p == 0 ) return(1);
233 }
234 }
235
yalloc(n)236 int *yalloc(n){ /* allocate n+1 words from vector mem */
237 int *omem;
238 omem = mem;
239 mem += n+1;
240 if(mem-mem0 >= memsiz) error("memory overflow");
241 return(omem);
242 }
243
aryfil(v,n,c)244 aryfil( v, n, c ) int *v,n,c; { /* set elements 0 through n-1 to c */
245 int i;
246 for( i=0; i<n; ++i ) v[i] = c;
247 }
248
UNION(a,b,c)249 UNION( a, b, c ) int *a, *b, *c; {
250 /* set a to the UNION of b and c */
251 /* a may equal b */
252 /* return 1 if c is not a subset of b, 0 otherwise */
253
254 _REGISTER int i, x, sub;
255
256 sub = 0;
257 for( i=0; i<tbitset; ++i ){
258 x = b[i] | c[i];
259 if( x != b[i] ) sub=1;
260 a[i] = x;
261 }
262 return( sub );
263 }
264
265 prlook( p ) struct looksets *p;{
266 int j, *pp;
267 pp = p->lset;
268 if( pp == 0 ) fprintf( cout , "\tNULL");
269 else {
270 fprintf( cout , " { " );
271 for( j=1; j<=nterms; ++j ){
272 if( (pp[j>>4]>>(j&017) )&01 != 0 ) fprintf( cout , "%s ", symnam(j) );
273 }
274 fprintf( cout , "}" );
275 }
276 }
277