Commit | Line | Data |
---|---|---|
15637ed4 RG |
1 | |
2 | #include "defs.h" | |
3 | ||
4 | extern short *itemset; | |
5 | extern short *itemsetend; | |
6 | extern unsigned *ruleset; | |
7 | ||
8 | int nstates; | |
9 | core *first_state; | |
10 | shifts *first_shift; | |
11 | reductions *first_reduction; | |
12 | ||
13 | int get_state(); | |
14 | core *new_state(); | |
15 | ||
16 | static core **state_set; | |
17 | static core *this_state; | |
18 | static core *last_state; | |
19 | static shifts *last_shift; | |
20 | static reductions *last_reduction; | |
21 | ||
22 | static int nshifts; | |
23 | static short *shift_symbol; | |
24 | ||
25 | static short *redset; | |
26 | static short *shiftset; | |
27 | ||
28 | static short **kernel_base; | |
29 | static short **kernel_end; | |
30 | static short *kernel_items; | |
31 | ||
32 | ||
33 | allocate_itemsets() | |
34 | { | |
35 | register short *itemp; | |
36 | register short *item_end; | |
37 | register int symbol; | |
38 | register int i; | |
39 | register int count; | |
40 | register int max; | |
41 | register short *symbol_count; | |
42 | ||
43 | count = 0; | |
44 | symbol_count = NEW2(nsyms, short); | |
45 | ||
46 | item_end = ritem + nitems; | |
47 | for (itemp = ritem; itemp < item_end; itemp++) | |
48 | { | |
49 | symbol = *itemp; | |
50 | if (symbol >= 0) | |
51 | { | |
52 | count++; | |
53 | symbol_count[symbol]++; | |
54 | } | |
55 | } | |
56 | ||
57 | kernel_base = NEW2(nsyms, short *); | |
58 | kernel_items = NEW2(count, short); | |
59 | ||
60 | count = 0; | |
61 | max = 0; | |
62 | for (i = 0; i < nsyms; i++) | |
63 | { | |
64 | kernel_base[i] = kernel_items + count; | |
65 | count += symbol_count[i]; | |
66 | if (max < symbol_count[i]) | |
67 | max = symbol_count[i]; | |
68 | } | |
69 | ||
70 | shift_symbol = symbol_count; | |
71 | kernel_end = NEW2(nsyms, short *); | |
72 | } | |
73 | ||
74 | ||
75 | allocate_storage() | |
76 | { | |
77 | allocate_itemsets(); | |
78 | shiftset = NEW2(nsyms, short); | |
79 | redset = NEW2(nrules + 1, short); | |
80 | state_set = NEW2(nitems, core *); | |
81 | } | |
82 | ||
83 | ||
84 | append_states() | |
85 | { | |
86 | register int i; | |
87 | register int j; | |
88 | register int symbol; | |
89 | ||
90 | #ifdef TRACE | |
91 | fprintf(stderr, "Entering append_states()\n"); | |
92 | #endif | |
93 | for (i = 1; i < nshifts; i++) | |
94 | { | |
95 | symbol = shift_symbol[i]; | |
96 | j = i; | |
97 | while (j > 0 && shift_symbol[j - 1] > symbol) | |
98 | { | |
99 | shift_symbol[j] = shift_symbol[j - 1]; | |
100 | j--; | |
101 | } | |
102 | shift_symbol[j] = symbol; | |
103 | } | |
104 | ||
105 | for (i = 0; i < nshifts; i++) | |
106 | { | |
107 | symbol = shift_symbol[i]; | |
108 | shiftset[i] = get_state(symbol); | |
109 | } | |
110 | } | |
111 | ||
112 | ||
113 | free_storage() | |
114 | { | |
115 | FREE(shift_symbol); | |
116 | FREE(redset); | |
117 | FREE(shiftset); | |
118 | FREE(kernel_base); | |
119 | FREE(kernel_end); | |
120 | FREE(kernel_items); | |
121 | FREE(state_set); | |
122 | } | |
123 | ||
124 | ||
125 | ||
126 | generate_states() | |
127 | { | |
128 | allocate_storage(); | |
129 | itemset = NEW2(nitems, short); | |
130 | ruleset = NEW2(WORDSIZE(nrules), unsigned); | |
131 | set_first_derives(); | |
132 | initialize_states(); | |
133 | ||
134 | while (this_state) | |
135 | { | |
136 | closure(this_state->items, this_state->nitems); | |
137 | save_reductions(); | |
138 | new_itemsets(); | |
139 | append_states(); | |
140 | ||
141 | if (nshifts > 0) | |
142 | save_shifts(); | |
143 | ||
144 | this_state = this_state->next; | |
145 | } | |
146 | ||
147 | finalize_closure(); | |
148 | free_storage(); | |
149 | } | |
150 | ||
151 | ||
152 | ||
153 | int | |
154 | get_state(symbol) | |
155 | int symbol; | |
156 | { | |
157 | register int key; | |
158 | register short *isp1; | |
159 | register short *isp2; | |
160 | register short *iend; | |
161 | register core *sp; | |
162 | register int found; | |
163 | register int n; | |
164 | ||
165 | #ifdef TRACE | |
166 | fprintf(stderr, "Entering get_state(%d)\n", symbol); | |
167 | #endif | |
168 | ||
169 | isp1 = kernel_base[symbol]; | |
170 | iend = kernel_end[symbol]; | |
171 | n = iend - isp1; | |
172 | ||
173 | key = *isp1; | |
174 | assert(0 <= key && key < nitems); | |
175 | sp = state_set[key]; | |
176 | if (sp) | |
177 | { | |
178 | found = 0; | |
179 | while (!found) | |
180 | { | |
181 | if (sp->nitems == n) | |
182 | { | |
183 | found = 1; | |
184 | isp1 = kernel_base[symbol]; | |
185 | isp2 = sp->items; | |
186 | ||
187 | while (found && isp1 < iend) | |
188 | { | |
189 | if (*isp1++ != *isp2++) | |
190 | found = 0; | |
191 | } | |
192 | } | |
193 | ||
194 | if (!found) | |
195 | { | |
196 | if (sp->link) | |
197 | { | |
198 | sp = sp->link; | |
199 | } | |
200 | else | |
201 | { | |
202 | sp = sp->link = new_state(symbol); | |
203 | found = 1; | |
204 | } | |
205 | } | |
206 | } | |
207 | } | |
208 | else | |
209 | { | |
210 | state_set[key] = sp = new_state(symbol); | |
211 | } | |
212 | ||
213 | return (sp->number); | |
214 | } | |
215 | ||
216 | ||
217 | ||
218 | initialize_states() | |
219 | { | |
220 | register int i; | |
221 | register short *start_derives; | |
222 | register core *p; | |
223 | ||
224 | start_derives = derives[start_symbol]; | |
225 | for (i = 0; start_derives[i] >= 0; ++i) | |
226 | continue; | |
227 | ||
228 | p = (core *) MALLOC(sizeof(core) + i*sizeof(short)); | |
229 | if (p == 0) no_space(); | |
230 | ||
231 | p->next = 0; | |
232 | p->link = 0; | |
233 | p->number = 0; | |
234 | p->accessing_symbol = 0; | |
235 | p->nitems = i; | |
236 | ||
237 | for (i = 0; start_derives[i] >= 0; ++i) | |
238 | p->items[i] = rrhs[start_derives[i]]; | |
239 | ||
240 | first_state = last_state = this_state = p; | |
241 | nstates = 1; | |
242 | } | |
243 | ||
244 | ||
245 | new_itemsets() | |
246 | { | |
247 | register int i; | |
248 | register int shiftcount; | |
249 | register short *isp; | |
250 | register short *ksp; | |
251 | register int symbol; | |
252 | ||
253 | for (i = 0; i < nsyms; i++) | |
254 | kernel_end[i] = 0; | |
255 | ||
256 | shiftcount = 0; | |
257 | isp = itemset; | |
258 | while (isp < itemsetend) | |
259 | { | |
260 | i = *isp++; | |
261 | symbol = ritem[i]; | |
262 | if (symbol > 0) | |
263 | { | |
264 | ksp = kernel_end[symbol]; | |
265 | if (!ksp) | |
266 | { | |
267 | shift_symbol[shiftcount++] = symbol; | |
268 | ksp = kernel_base[symbol]; | |
269 | } | |
270 | ||
271 | *ksp++ = i + 1; | |
272 | kernel_end[symbol] = ksp; | |
273 | } | |
274 | } | |
275 | ||
276 | nshifts = shiftcount; | |
277 | } | |
278 | ||
279 | ||
280 | ||
281 | core * | |
282 | new_state(symbol) | |
283 | int symbol; | |
284 | { | |
285 | register int n; | |
286 | register core *p; | |
287 | register short *isp1; | |
288 | register short *isp2; | |
289 | register short *iend; | |
290 | ||
291 | #ifdef TRACE | |
292 | fprintf(stderr, "Entering new_state(%d)\n", symbol); | |
293 | #endif | |
294 | ||
295 | if (nstates >= MAXSHORT) | |
296 | fatal("too many states"); | |
297 | ||
298 | isp1 = kernel_base[symbol]; | |
299 | iend = kernel_end[symbol]; | |
300 | n = iend - isp1; | |
301 | ||
302 | p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short))); | |
303 | p->accessing_symbol = symbol; | |
304 | p->number = nstates; | |
305 | p->nitems = n; | |
306 | ||
307 | isp2 = p->items; | |
308 | while (isp1 < iend) | |
309 | *isp2++ = *isp1++; | |
310 | ||
311 | last_state->next = p; | |
312 | last_state = p; | |
313 | ||
314 | nstates++; | |
315 | ||
316 | return (p); | |
317 | } | |
318 | ||
319 | ||
320 | /* show_cores is used for debugging */ | |
321 | ||
322 | show_cores() | |
323 | { | |
324 | core *p; | |
325 | int i, j, k, n; | |
326 | int itemno; | |
327 | ||
328 | k = 0; | |
329 | for (p = first_state; p; ++k, p = p->next) | |
330 | { | |
331 | if (k) printf("\n"); | |
332 | printf("state %d, number = %d, accessing symbol = %s\n", | |
333 | k, p->number, symbol_name[p->accessing_symbol]); | |
334 | n = p->nitems; | |
335 | for (i = 0; i < n; ++i) | |
336 | { | |
337 | itemno = p->items[i]; | |
338 | printf("%4d ", itemno); | |
339 | j = itemno; | |
340 | while (ritem[j] >= 0) ++j; | |
341 | printf("%s :", symbol_name[rlhs[-ritem[j]]]); | |
342 | j = rrhs[-ritem[j]]; | |
343 | while (j < itemno) | |
344 | printf(" %s", symbol_name[ritem[j++]]); | |
345 | printf(" ."); | |
346 | while (ritem[j] >= 0) | |
347 | printf(" %s", symbol_name[ritem[j++]]); | |
348 | printf("\n"); | |
349 | fflush(stdout); | |
350 | } | |
351 | } | |
352 | } | |
353 | ||
354 | ||
355 | /* show_ritems is used for debugging */ | |
356 | ||
357 | show_ritems() | |
358 | { | |
359 | int i; | |
360 | ||
361 | for (i = 0; i < nitems; ++i) | |
362 | printf("ritem[%d] = %d\n", i, ritem[i]); | |
363 | } | |
364 | ||
365 | ||
366 | /* show_rrhs is used for debugging */ | |
367 | show_rrhs() | |
368 | { | |
369 | int i; | |
370 | ||
371 | for (i = 0; i < nrules; ++i) | |
372 | printf("rrhs[%d] = %d\n", i, rrhs[i]); | |
373 | } | |
374 | ||
375 | ||
376 | /* show_shifts is used for debugging */ | |
377 | ||
378 | show_shifts() | |
379 | { | |
380 | shifts *p; | |
381 | int i, j, k; | |
382 | ||
383 | k = 0; | |
384 | for (p = first_shift; p; ++k, p = p->next) | |
385 | { | |
386 | if (k) printf("\n"); | |
387 | printf("shift %d, number = %d, nshifts = %d\n", k, p->number, | |
388 | p->nshifts); | |
389 | j = p->nshifts; | |
390 | for (i = 0; i < j; ++i) | |
391 | printf("\t%d\n", p->shift[i]); | |
392 | } | |
393 | } | |
394 | ||
395 | ||
396 | save_shifts() | |
397 | { | |
398 | register shifts *p; | |
399 | register short *sp1; | |
400 | register short *sp2; | |
401 | register short *send; | |
402 | ||
403 | p = (shifts *) allocate((unsigned) (sizeof(shifts) + | |
404 | (nshifts - 1) * sizeof(short))); | |
405 | ||
406 | p->number = this_state->number; | |
407 | p->nshifts = nshifts; | |
408 | ||
409 | sp1 = shiftset; | |
410 | sp2 = p->shift; | |
411 | send = shiftset + nshifts; | |
412 | ||
413 | while (sp1 < send) | |
414 | *sp2++ = *sp1++; | |
415 | ||
416 | if (last_shift) | |
417 | { | |
418 | last_shift->next = p; | |
419 | last_shift = p; | |
420 | } | |
421 | else | |
422 | { | |
423 | first_shift = p; | |
424 | last_shift = p; | |
425 | } | |
426 | } | |
427 | ||
428 | ||
429 | ||
430 | save_reductions() | |
431 | { | |
432 | register short *isp; | |
433 | register short *rp1; | |
434 | register short *rp2; | |
435 | register int item; | |
436 | register int count; | |
437 | register reductions *p; | |
438 | register short *rend; | |
439 | ||
440 | count = 0; | |
441 | for (isp = itemset; isp < itemsetend; isp++) | |
442 | { | |
443 | item = ritem[*isp]; | |
444 | if (item < 0) | |
445 | { | |
446 | redset[count++] = -item; | |
447 | } | |
448 | } | |
449 | ||
450 | if (count) | |
451 | { | |
452 | p = (reductions *) allocate((unsigned) (sizeof(reductions) + | |
453 | (count - 1) * sizeof(short))); | |
454 | ||
455 | p->number = this_state->number; | |
456 | p->nreds = count; | |
457 | ||
458 | rp1 = redset; | |
459 | rp2 = p->rules; | |
460 | rend = rp1 + count; | |
461 | ||
462 | while (rp1 < rend) | |
463 | *rp2++ = *rp1++; | |
464 | ||
465 | if (last_reduction) | |
466 | { | |
467 | last_reduction->next = p; | |
468 | last_reduction = p; | |
469 | } | |
470 | else | |
471 | { | |
472 | first_reduction = p; | |
473 | last_reduction = p; | |
474 | } | |
475 | } | |
476 | } | |
477 | ||
478 | ||
479 | set_derives() | |
480 | { | |
481 | register int i, k; | |
482 | register int lhs; | |
483 | register short *rules; | |
484 | ||
485 | derives = NEW2(nsyms, short *); | |
486 | rules = NEW2(nvars + nrules, short); | |
487 | ||
488 | k = 0; | |
489 | for (lhs = start_symbol; lhs < nsyms; lhs++) | |
490 | { | |
491 | derives[lhs] = rules + k; | |
492 | for (i = 0; i < nrules; i++) | |
493 | { | |
494 | if (rlhs[i] == lhs) | |
495 | { | |
496 | rules[k] = i; | |
497 | k++; | |
498 | } | |
499 | } | |
500 | rules[k] = -1; | |
501 | k++; | |
502 | } | |
503 | ||
504 | #ifdef DEBUG | |
505 | print_derives(); | |
506 | #endif | |
507 | } | |
508 | ||
509 | free_derives() | |
510 | { | |
511 | FREE(derives[start_symbol]); | |
512 | FREE(derives); | |
513 | } | |
514 | ||
515 | #ifdef DEBUG | |
516 | print_derives() | |
517 | { | |
518 | register int i; | |
519 | register short *sp; | |
520 | ||
521 | printf("\nDERIVES\n\n"); | |
522 | ||
523 | for (i = start_symbol; i < nsyms; i++) | |
524 | { | |
525 | printf("%s derives ", symbol_name[i]); | |
526 | for (sp = derives[i]; *sp >= 0; sp++) | |
527 | { | |
528 | printf(" %d", *sp); | |
529 | } | |
530 | putchar('\n'); | |
531 | } | |
532 | ||
533 | putchar('\n'); | |
534 | } | |
535 | #endif | |
536 | ||
537 | ||
538 | set_nullable() | |
539 | { | |
540 | register int i, j; | |
541 | register int empty; | |
542 | int done; | |
543 | ||
544 | nullable = MALLOC(nsyms); | |
545 | if (nullable == 0) no_space(); | |
546 | ||
547 | for (i = 0; i < nsyms; ++i) | |
548 | nullable[i] = 0; | |
549 | ||
550 | done = 0; | |
551 | while (!done) | |
552 | { | |
553 | done = 1; | |
554 | for (i = 1; i < nitems; i++) | |
555 | { | |
556 | empty = 1; | |
557 | while ((j = ritem[i]) >= 0) | |
558 | { | |
559 | if (!nullable[j]) | |
560 | empty = 0; | |
561 | ++i; | |
562 | } | |
563 | if (empty) | |
564 | { | |
565 | j = rlhs[-j]; | |
566 | if (!nullable[j]) | |
567 | { | |
568 | nullable[j] = 1; | |
569 | done = 0; | |
570 | } | |
571 | } | |
572 | } | |
573 | } | |
574 | ||
575 | #ifdef DEBUG | |
576 | for (i = 0; i < nsyms; i++) | |
577 | { | |
578 | if (nullable[i]) | |
579 | printf("%s is nullable\n", symbol_name[i]); | |
580 | else | |
581 | printf("%s is not nullable\n", symbol_name[i]); | |
582 | } | |
583 | #endif | |
584 | } | |
585 | ||
586 | ||
587 | free_nullable() | |
588 | { | |
589 | FREE(nullable); | |
590 | } | |
591 | ||
592 | ||
593 | lr0() | |
594 | { | |
595 | set_derives(); | |
596 | set_nullable(); | |
597 | generate_states(); | |
598 | } |