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.2 (Berkeley) 09/22/88"; 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 setup(argc,argv); /* initialize and read productions */ 82 tbitset = (nterms+16)/16; 83 cpres(); /* make table of which productions yield a given nonterminal */ 84 cempty(); /* make a table of which nonterminals can match the empty string */ 85 cpfir(); /* make a table of e free first lists */ 86 stagen(); /* generate the states */ 87 output(); /* write the states and the tables */ 88 go2out(); 89 summary(); 90 exit(0); 91 } 92 93 settty() 94 /* sets the output file to y.output */ 95 { 96 cflush( foutput ); /* a bit of a cheat */ 97 cout = foutput; 98 } 99 100 settab(){ /* sets the output file to y.tab.c */ 101 102 cflush( ftable ); 103 cout = ftable; 104 } 105 106 char *chcopy( p, q ) char *p, *q; { 107 /* copies string q into p, returning next free char ptr */ 108 while( *p = *q++ ) ++p; 109 return( p ); 110 } 111 112 char *writem(pp) struct item *pp; { /* creates output string for item pointed to by pp */ 113 int i,*p; 114 static char sarr[100]; 115 char *q; 116 117 for( p=pp->pitem; *p>0 ; ++p ) ; 118 p = prdptr[-*p]; 119 q = chcopy( sarr, nontrst[*p-NTBASE].name ); 120 q = chcopy( q, " : " ); 121 122 for(;;){ 123 *q++ = ++p==(pp->pitem) ? '_' : ' '; 124 if((i = *p) <= 0) break; 125 q = chcopy( q, symnam(i) ); 126 } 127 128 *q = '\0' ; 129 return( sarr ); 130 } 131 132 char *symnam(i){ /* return a pointer to the name of symbol i */ 133 char *cp; 134 135 cp = (i>=NTBASE) ? nontrst[i-NTBASE].name : trmset[i].name ; 136 if( *cp == ' ' ) ++cp; 137 return( cp ); 138 } 139 140 summary(){ /* output the summary on the tty */ 141 142 int i, s, *pn; 143 144 145 if( !rflag ){ 146 settab(); 147 fprintf( cout , "\nint nterms %d;",nterms); 148 fprintf( cout , "\nint nnonter %d;", nnonter); 149 fprintf( cout , "\nint nstate %d;", nstate); 150 fprintf( cout , "\nchar *yysterm[] {"); 151 for (i=1;i<=nterms;i++) if( trmset[i].value >= 0400 ) fprintf( cout , "\n\"%s\",",symnam(i)); 152 fprintf( cout , "\n0 };\n" ); 153 fprintf( cout , "\nchar *yysnter[] {"); 154 for (i=0;i<nnonter;i++) fprintf( cout , "\n\"%s\",",nontrst[i].name); 155 fprintf( cout , "\n\"%s\" };\n",nontrst[nnonter].name); 156 } 157 158 settty(); 159 fprintf( cout , "\n%d/%d terminals, %d/%d nonterminals\n", nterms, tlim, 160 nnonter, ntlim ); 161 fprintf( cout , "%d/%d grammar rules, %d/%d states\n", nprod, prdlim, nstate, stsize ); 162 fprintf( cout , "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf ); 163 pn = (int *)pstate[nstate+1]; 164 fprintf( cout , "%d/%d working sets used\n", zzcwset, wssize ); 165 fprintf( cout , "memory: states,etc. %d/%d, parser %d/%d\n", pn-mem0, memsiz, 166 memact, actsiz ); 167 fprintf( cout , "%d/%d distinct lookahead sets\n", nlset, lsetsz ); 168 fprintf( cout , "%d extra closures\n", zzclose - 2*nstate ); 169 fprintf( cout , "%d action entries\n", zzacent ); 170 fprintf( cout , "%d action entries saved through merging %d states\n",zzacsave,zznsave); 171 fprintf( cout , "%d goto entries\n", zzgoent ); 172 fprintf( cout , "%d entries saved by goto default\n", zzgobest ); 173 fprintf( cout , "%d lookahead sets saved\n", savedlook); 174 if( zzsrconf!=0 || zzrrconf!=0 ){ 175 cflush( errfileno ); 176 cout = errfileno; 177 fprintf( cout , "\nconflicts: "); 178 if( zzsrconf )fprintf( cout , "%d shift/reduce" , zzsrconf ); 179 if( zzsrconf && zzrrconf )fprintf( cout , ", " ); 180 if( zzrrconf )fprintf( cout , "%d reduce/reduce" , zzrrconf ); 181 fprintf( cout , "\n" ); 182 } 183 } 184 185 error(s,a1){ /* write out error comment */ 186 187 int c; 188 ++nerrors; 189 cflush( errfileno ); 190 cout = errfileno; /* set output to tty */ 191 fprintf( cout , "\n fatal error: "); 192 fprintf( cout , s,a1); 193 fprintf( cout , ", line %d\n", lineno ); 194 if( !fatfl ) return; 195 summary(); 196 cexit(1); 197 } 198 199 arrset(s) char s[]; { 200 fprintf( cout , "\nint %s[] {0", s ); 201 arrndx = 1; 202 } 203 204 arrval(n){ 205 fprintf( cout , ",%d",n); 206 if( (++arrndx%10) == 0 ) fprintf( cout , "\n"); 207 } 208 209 arrdone(){ 210 fprintf( cout , ",-1};\n"); 211 } 212 213 copy(v) char *v; { /* copy ctokn to v */ 214 char *p; 215 216 p=ctokn; 217 while( *v++ = *p++ ); 218 } 219 220 compare(v) char *v; { /* compare ctokn with v */ 221 char *p; 222 223 for( p=ctokn; ; ++p ){ 224 if( *p != *v++ ) return( 0 ); 225 if( *p == 0 ) return(1); 226 } 227 } 228 229 int *yalloc(n){ /* allocate n+1 words from vector mem */ 230 int *omem; 231 omem = mem; 232 mem += n+1; 233 if(mem-mem0 >= memsiz) error("memory overflow"); 234 return(omem); 235 } 236 237 aryfil( v, n, c ) int *v,n,c; { /* set elements 0 through n-1 to c */ 238 int i; 239 for( i=0; i<n; ++i ) v[i] = c; 240 } 241 242 UNION( a, b, c ) int *a, *b, *c; { 243 /* set a to the UNION of b and c */ 244 /* a may equal b */ 245 /* return 1 if c is not a subset of b, 0 otherwise */ 246 247 _REGISTER int i, x, sub; 248 249 sub = 0; 250 for( i=0; i<tbitset; ++i ){ 251 x = b[i] | c[i]; 252 if( x != b[i] ) sub=1; 253 a[i] = x; 254 } 255 return( sub ); 256 } 257 258 prlook( p ) struct looksets *p;{ 259 int j, *pp; 260 pp = p->lset; 261 if( pp == 0 ) fprintf( cout , "\tNULL"); 262 else { 263 fprintf( cout , " { " ); 264 for( j=1; j<=nterms; ++j ){ 265 if( (pp[j>>4]>>(j&017) )&01 != 0 ) fprintf( cout , "%s ", symnam(j) ); 266 } 267 fprintf( cout , "}" ); 268 } 269 } 270