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