1 /*-
2 * Copyright (c) 1980, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.redist.c%
6 */
7
8 #ifndef lint
9 static char sccsid[] = "@(#)yycosts.c 8.1 (Berkeley) 06/06/93";
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 */
inscost(sy,before)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 */
repcost(what,with)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 */
delcost(what)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
yycosts()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
yydocost(c)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