1 /* Copyright (c) 1979 Regents of the University of California */ 2 3 #ifndef lint 4 static char sccsid[] = "@(#)yycosts.c 2.1 02/08/84"; 5 #endif 6 7 #include "whoami.h" 8 #include "0.h" 9 #include "tree_ty.h" /* must be included for yy.h */ 10 #include "yy.h" 11 12 /* 13 * Symbol costs for Pascal. 14 * 15 * Cost strategy of August 14, 1977. 16 * 17 * The costs determined by the routines in this file are used by 18 * the recovery in choosing appropriate corrections. 19 * The cost vectors and the error productions in the grammar 20 * work together to define the corrective capacity of the grammar. 21 * 22 * The costs here largely derive from those given in Steve Rhode's 23 * thesis for the Pascal-I error correcting parser which he implemented. 24 * Some minor changes have been made to adjust for the fact that 25 * the current error recovery is not as "smart", both because of the 26 * limited forward move and because of the lack of any type information 27 * about identifiers. 28 * 29 * These adjustments largely take the form of increased costs for certain 30 * tokens, noticeably keywords which are major brackets such as "begin" 31 * "label", "procedure", etc. 32 * 33 * The overall weighting strategy is still similar to Rhodes' strategy. 34 * The costs can be considered: 35 * 36 * LOW <= 3 37 * MEDIUM 4 or 5 38 * HIGH >= 6 39 */ 40 41 /* 42 * Insertion costs 43 * 44 * In addition to the normal symbol insertion costs, 45 * there are zero cost insertions here. 46 * The current error recovery system treats symbols 47 * which have zero insertion cost in a special way, 48 * inserting them but suppressing diagnostics. 49 * This allows the system to hold of on bracketing 50 * error diagnostics about missing end's until the 51 * reduction occurs which knows the line number of the 52 * corresponding "begin", "repeat", etc. 53 * A more intelligent and useful diagnostic can then 54 * be printed. 55 * 56 * Although this routine never allows the insertion 57 * of the keyword begin, it can be inserted after a 58 * procedure or function body starts, if it was omitted 59 * by a special case in the panic routine, which notices 60 * the keywords in the statement body of the procedure 61 * and inserts the begin to recover. 62 * 63 * Similarly, we do not insert end-of-file, but 64 * the fact that end-of-file is the unique input 65 * is noticed by the recovery routines as a special 66 * case and handled there. 67 */ 68 inscost(sy, before) 69 register int sy, before; 70 { 71 72 switch (before) { 73 case YEND: 74 if (sy == YEND) 75 break; 76 case YPROCEDURE: 77 case YFUNCTION: 78 if (sy == YUNTIL || sy == YEND) 79 return (0); 80 } 81 switch (sy) { 82 case ';': 83 return (1); 84 case ',': 85 case ':': 86 case YOF: 87 case YDO: 88 return (2); 89 case YARRAY: 90 case '+': 91 case '*': 92 return (3); 93 default: 94 return (4); 95 case '^': 96 case YNOT: 97 case YLABEL: 98 case YCONST: 99 case YTYPE: 100 case YVAR: 101 case YUNTIL: 102 case '(': 103 case '[': 104 case YWHILE: 105 case YWITH: 106 return (5); 107 case YPROCEDURE: 108 case YFUNCTION: 109 case YCASE: 110 return (6); 111 case YEND: 112 return (8); 113 case YBEGIN: 114 case YEOF: 115 case YREPEAT: 116 case YRECORD: 117 return (INFINITY); 118 } 119 } 120 121 /* 122 * Replacement costs 123 * 124 * Most replacement costs are the same as an insertion 125 * plus a deletion cost. One special case is the replacement 126 * of a large number of keywords by an identifier. 127 * These are given lower costs, especially the keyword "to". 128 */ 129 repcost(what, with) 130 register int what, with; 131 { 132 register int c; 133 134 if (with == what) 135 return (INFINITY); 136 if (with == YID && what > ERROR) 137 switch (what) { 138 case YID: 139 case YDOTDOT: 140 case YINT: 141 case YBINT: 142 case YSTRING: 143 case YNUMB: 144 break; 145 case YTO: 146 return (3); 147 default: 148 return (5); 149 case YRECORD: 150 case YTHEN: 151 return (6); 152 case YBEGIN: 153 break; 154 } 155 if (what == YID && with == YFORWARD) 156 return(5); 157 if (what == ';' && (with == ',' || with == '.')) 158 return (CLIMIT - 1); 159 c = delcost(what) + inscost(with, what); 160 /* 161 * It costs extra to replace something which has 162 * semantics by something which doesn't. 163 */ 164 if (nullsem(what) == NIL && nullsem(with) != NIL) 165 c += 4; 166 return (c); 167 } 168 169 /* 170 * Deletion costs 171 */ 172 delcost(what) 173 int what; 174 { 175 176 switch (what) { 177 case '.': 178 case ':': 179 case ',': 180 case '=': 181 case '(': 182 return (3); 183 case YELSE: 184 case YTHEN: 185 return (4); 186 default: 187 return (5); 188 case YLABEL: 189 case YCONST: 190 case YTYPE: 191 case YVAR: 192 return (10); 193 case YPROCEDURE: 194 case YFUNCTION: 195 case YBEGIN: 196 case YEND: 197 return ((CLIMIT * 3) / 4); 198 case ';': 199 case YEOF: 200 return (INFINITY); 201 } 202 } 203 #ifdef DEBUG 204 205 /* 206 * Routine to print out costs with "-K" option. 207 */ 208 char yysyms[] = ";,:=*+/-|&()[]<>~^"; 209 210 211 yycosts() 212 { 213 register int c; 214 register char *cp; 215 216 printf("Insert\tDelete\tRep(ID)\tSymbol\n"); 217 for (cp = yysyms; *cp; cp++) 218 yydocost(*cp); 219 for (c = ERROR + 1; c < YLAST; c++) 220 yydocost(c); 221 #ifdef PXP 222 flush(); 223 #endif 224 } 225 226 yydocost(c) 227 int c; 228 { 229 230 printf("%4d\t", inscost(c, -1)); 231 printf("%4d\t", delcost(c)); 232 if (repcost(c, YID) != inscost(YID, c) + delcost(c)) 233 printf("%4d", repcost(c, YID)); 234 printf("\t%s%s\n", charname(c,1)); 235 } 236 #endif 237