[w32file] Fix usage of copyfile (#10010)
[mono-project.git] / mcs / jay / lr0.c
blob8e2e8a0305f8b7ae1f8a5d8bfeec54637570aa16
1 /*
2 * Copyright (c) 1989 The Regents of the University of California.
3 * All rights reserved.
5 * This code is derived from software contributed to Berkeley by
6 * Robert Paul Corbett.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
37 #ifndef lint
38 static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91";
39 #endif /* not lint */
41 #include "defs.h"
43 extern short *itemset;
44 extern short *itemsetend;
45 extern unsigned *ruleset;
47 int nstates;
48 core *first_state;
49 shifts *first_shift;
50 reductions *first_reduction;
52 static int
53 get_state (int symbol);
55 static core *
56 new_state (int symbol);
58 static core **state_set;
59 static core *this_state;
60 static core *last_state;
61 static shifts *last_shift;
62 static reductions *last_reduction;
64 static int nshifts;
65 static short *shift_symbol;
67 static short *redset;
68 static short *shiftset;
70 static short **kernel_base;
71 static short **kernel_end;
72 static short *kernel_items;
74 #ifdef DEBUG
75 static void
76 print_derives (void);
77 #endif
79 static void
80 save_reductions (void);
82 static void
83 save_shifts (void);
85 static void
86 new_itemsets (void);
88 static void
89 initialize_states (void);
91 static void
92 allocate_itemsets (void)
94 register short *itemp;
95 register short *item_end;
96 register int symbol;
97 register int i;
98 register int count;
99 register int max;
100 register short *symbol_count;
102 count = 0;
103 symbol_count = NEW2(nsyms, short);
105 item_end = ritem + nitems;
106 for (itemp = ritem; itemp < item_end; itemp++)
108 symbol = *itemp;
109 if (symbol >= 0)
111 count++;
112 symbol_count[symbol]++;
116 kernel_base = NEW2(nsyms, short *);
117 kernel_items = NEW2(count, short);
119 count = 0;
120 max = 0;
121 for (i = 0; i < nsyms; i++)
123 kernel_base[i] = kernel_items + count;
124 count += symbol_count[i];
125 if (max < symbol_count[i])
126 max = symbol_count[i];
129 shift_symbol = symbol_count;
130 kernel_end = NEW2(nsyms, short *);
133 static void
134 allocate_storage (void)
136 allocate_itemsets();
137 shiftset = NEW2(nsyms, short);
138 redset = NEW2(nrules + 1, short);
139 state_set = NEW2(nitems, core *);
142 static void
143 append_states (void)
145 register int i;
146 register int j;
147 register int symbol;
149 #ifdef TRACE
150 fprintf(stderr, "Entering append_states()\n");
151 #endif
152 for (i = 1; i < nshifts; i++)
154 symbol = shift_symbol[i];
155 j = i;
156 while (j > 0 && shift_symbol[j - 1] > symbol)
158 shift_symbol[j] = shift_symbol[j - 1];
159 j--;
161 shift_symbol[j] = symbol;
164 for (i = 0; i < nshifts; i++)
166 symbol = shift_symbol[i];
167 shiftset[i] = get_state(symbol);
171 static void
172 free_storage (void)
174 FREE(shift_symbol);
175 FREE(redset);
176 FREE(shiftset);
177 FREE(kernel_base);
178 FREE(kernel_end);
179 FREE(kernel_items);
180 FREE(state_set);
183 static void
184 generate_states (void)
186 allocate_storage();
187 itemset = NEW2(nitems, short);
188 ruleset = NEW2(WORDSIZE(nrules), unsigned);
189 set_first_derives();
190 initialize_states();
192 while (this_state)
194 closure(this_state->items, this_state->nitems);
195 save_reductions();
196 new_itemsets();
197 append_states();
199 if (nshifts > 0)
200 save_shifts();
202 this_state = this_state->next;
205 finalize_closure();
206 free_storage();
210 get_state (int symbol)
212 register int key;
213 register short *isp1;
214 register short *isp2;
215 register short *iend;
216 register core *sp;
217 register int found;
218 register int n;
220 #ifdef TRACE
221 fprintf(stderr, "Entering get_state(%d)\n", symbol);
222 #endif
224 isp1 = kernel_base[symbol];
225 iend = kernel_end[symbol];
226 n = iend - isp1;
228 key = *isp1;
229 assert(0 <= key && key < nitems);
230 sp = state_set[key];
231 if (sp)
233 found = 0;
234 while (!found)
236 if (sp->nitems == n)
238 found = 1;
239 isp1 = kernel_base[symbol];
240 isp2 = sp->items;
242 while (found && isp1 < iend)
244 if (*isp1++ != *isp2++)
245 found = 0;
249 if (!found)
251 if (sp->link)
253 sp = sp->link;
255 else
257 sp = sp->link = new_state(symbol);
258 found = 1;
263 else
265 state_set[key] = sp = new_state(symbol);
268 return (sp->number);
271 static void
272 initialize_states (void)
274 register int i;
275 register short *start_derives;
276 register core *p;
278 start_derives = derives[start_symbol];
279 for (i = 0; start_derives[i] >= 0; ++i)
280 continue;
282 p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
283 if (p == 0) no_space();
285 p->next = 0;
286 p->link = 0;
287 p->number = 0;
288 p->accessing_symbol = 0;
289 p->nitems = i;
291 for (i = 0; start_derives[i] >= 0; ++i)
292 p->items[i] = rrhs[start_derives[i]];
294 first_state = last_state = this_state = p;
295 nstates = 1;
298 static void
299 new_itemsets (void)
301 register int i;
302 register int shiftcount;
303 register short *isp;
304 register short *ksp;
305 register int symbol;
307 for (i = 0; i < nsyms; i++)
308 kernel_end[i] = 0;
310 shiftcount = 0;
311 isp = itemset;
312 while (isp < itemsetend)
314 i = *isp++;
315 symbol = ritem[i];
316 if (symbol > 0)
318 ksp = kernel_end[symbol];
319 if (!ksp)
321 shift_symbol[shiftcount++] = symbol;
322 ksp = kernel_base[symbol];
325 *ksp++ = i + 1;
326 kernel_end[symbol] = ksp;
330 nshifts = shiftcount;
333 static core *
334 new_state (int symbol)
336 register int n;
337 register core *p;
338 register short *isp1;
339 register short *isp2;
340 register short *iend;
342 #ifdef TRACE
343 fprintf(stderr, "Entering new_state(%d)\n", symbol);
344 #endif
346 if (nstates >= MAXSHORT)
347 fatal("too many states");
349 isp1 = kernel_base[symbol];
350 iend = kernel_end[symbol];
351 n = iend - isp1;
353 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
354 p->accessing_symbol = symbol;
355 p->number = nstates;
356 p->nitems = n;
358 isp2 = p->items;
359 while (isp1 < iend)
360 *isp2++ = *isp1++;
362 last_state->next = p;
363 last_state = p;
365 nstates++;
367 return (p);
370 /* show_cores is used for debugging */
372 void
373 show_cores (void)
375 core *p;
376 int i, j, k, n;
377 int itemno;
379 k = 0;
380 for (p = first_state; p; ++k, p = p->next)
382 if (k) printf("\n");
383 printf("state %d, number = %d, accessing symbol = %s\n",
384 k, p->number, symbol_name[p->accessing_symbol]);
385 n = p->nitems;
386 for (i = 0; i < n; ++i)
388 itemno = p->items[i];
389 printf("%4d ", itemno);
390 j = itemno;
391 while (ritem[j] >= 0) ++j;
392 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
393 j = rrhs[-ritem[j]];
394 while (j < itemno)
395 printf(" %s", symbol_name[ritem[j++]]);
396 printf(" .");
397 while (ritem[j] >= 0)
398 printf(" %s", symbol_name[ritem[j++]]);
399 printf("\n");
400 fflush(stdout);
406 /* show_ritems is used for debugging */
408 void
409 show_ritems (void)
411 int i;
413 for (i = 0; i < nitems; ++i)
414 printf("ritem[%d] = %d\n", i, ritem[i]);
417 /* show_rrhs is used for debugging */
418 void
419 show_rrhs (void)
421 int i;
423 for (i = 0; i < nrules; ++i)
424 printf("rrhs[%d] = %d\n", i, rrhs[i]);
428 /* show_shifts is used for debugging */
430 void
431 show_shifts (void)
433 shifts *p;
434 int i, j, k;
436 k = 0;
437 for (p = first_shift; p; ++k, p = p->next)
439 if (k) printf("\n");
440 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
441 p->nshifts);
442 j = p->nshifts;
443 for (i = 0; i < j; ++i)
444 printf("\t%d\n", p->shift[i]);
448 static void
449 save_shifts (void)
451 register shifts *p;
452 register short *sp1;
453 register short *sp2;
454 register short *send;
456 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
457 (nshifts - 1) * sizeof(short)));
459 p->number = this_state->number;
460 p->nshifts = nshifts;
462 sp1 = shiftset;
463 sp2 = p->shift;
464 send = shiftset + nshifts;
466 while (sp1 < send)
467 *sp2++ = *sp1++;
469 if (last_shift)
471 last_shift->next = p;
472 last_shift = p;
474 else
476 first_shift = p;
477 last_shift = p;
481 static void
482 save_reductions (void)
484 register short *isp;
485 register short *rp1;
486 register short *rp2;
487 register int item;
488 register int count;
489 register reductions *p;
490 register short *rend;
492 count = 0;
493 for (isp = itemset; isp < itemsetend; isp++)
495 item = ritem[*isp];
496 if (item < 0)
498 redset[count++] = -item;
502 if (count)
504 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
505 (count - 1) * sizeof(short)));
507 p->number = this_state->number;
508 p->nreds = count;
510 rp1 = redset;
511 rp2 = p->rules;
512 rend = rp1 + count;
514 while (rp1 < rend)
515 *rp2++ = *rp1++;
517 if (last_reduction)
519 last_reduction->next = p;
520 last_reduction = p;
522 else
524 first_reduction = p;
525 last_reduction = p;
530 static void
531 set_derives (void)
533 register int i, k;
534 register int lhs;
535 register short *rules;
537 derives = NEW2(nsyms, short *);
538 rules = NEW2(nvars + nrules, short);
540 k = 0;
541 for (lhs = start_symbol; lhs < nsyms; lhs++)
543 derives[lhs] = rules + k;
544 for (i = 0; i < nrules; i++)
546 if (rlhs[i] == lhs)
548 rules[k] = i;
549 k++;
552 rules[k] = -1;
553 k++;
556 #ifdef DEBUG
557 print_derives();
558 #endif
561 #if 0
562 void
563 free_derives (void)
565 FREE(derives[start_symbol]);
566 FREE(derives);
568 #endif
570 #ifdef DEBUG
571 static void
572 print_derives (void)
574 register int i;
575 register short *sp;
577 printf("\nDERIVES\n\n");
579 for (i = start_symbol; i < nsyms; i++)
581 printf("%s derives ", symbol_name[i]);
582 for (sp = derives[i]; *sp >= 0; sp++)
584 printf(" %d", *sp);
586 putchar('\n');
589 putchar('\n');
591 #endif
593 static void
594 set_nullable (void)
596 register int i, j;
597 register int empty;
598 int done;
600 nullable = (char*)MALLOC(nsyms);
601 if (nullable == 0) no_space();
603 for (i = 0; i < nsyms; ++i)
604 nullable[i] = 0;
606 done = 0;
607 while (!done)
609 done = 1;
610 for (i = 1; i < nitems; i++)
612 empty = 1;
613 while ((j = ritem[i]) >= 0)
615 if (!nullable[j])
616 empty = 0;
617 ++i;
619 if (empty)
621 j = rlhs[-j];
622 if (!nullable[j])
624 nullable[j] = 1;
625 done = 0;
631 #ifdef DEBUG
632 for (i = 0; i < nsyms; i++)
634 if (nullable[i])
635 printf("%s is nullable\n", symbol_name[i]);
636 else
637 printf("%s is not nullable\n", symbol_name[i]);
639 #endif
642 void
643 free_nullable (void)
645 FREE(nullable);
648 void
649 lr0 (void)
651 set_derives();
652 set_nullable();
653 generate_states();