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