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 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 100 settty() 101 /* sets the output file to y.output */ 102 { 103 cflush( foutput ); /* a bit of a cheat */ 104 cout = foutput; 105 } 106 107 settab(){ /* sets the output file to y.tab.c */ 108 109 cflush( ftable ); 110 cout = ftable; 111 } 112 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 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 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 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 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 206 arrset(s) char s[]; { 207 fprintf( cout , "\nint %s[] {0", s ); 208 arrndx = 1; 209 } 210 211 arrval(n){ 212 fprintf( cout , ",%d",n); 213 if( (++arrndx%10) == 0 ) fprintf( cout , "\n"); 214 } 215 216 arrdone(){ 217 fprintf( cout , ",-1};\n"); 218 } 219 220 copy(v) char *v; { /* copy ctokn to v */ 221 char *p; 222 223 p=ctokn; 224 while( *v++ = *p++ ); 225 } 226 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 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 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 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