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