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