source: trunk/minix/commands/byacc/lr0.c@ 11

Last change on this file since 11 was 9, checked in by Mattia Monga, 14 years ago

Minix 3.1.2a

File size: 9.4 KB
Line 
1
2#include "defs.h"
3
4extern short *itemset;
5extern short *itemsetend;
6extern unsigned *ruleset;
7
8int nstates;
9core *first_state;
10shifts *first_shift;
11reductions *first_reduction;
12
13int get_state();
14core *new_state();
15
16static core **state_set;
17static core *this_state;
18static core *last_state;
19static shifts *last_shift;
20static reductions *last_reduction;
21
22static int nshifts;
23static short *shift_symbol;
24
25static short *redset;
26static short *shiftset;
27
28static short **kernel_base;
29static short **kernel_end;
30static short *kernel_items;
31
32
33allocate_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
75allocate_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
84append_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
113free_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
126generate_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
153int
154get_state(symbol)
155int 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
218initialize_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
245new_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
281core *
282new_state(symbol)
283int 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
322show_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
357show_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 */
367show_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
378show_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
396save_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
430save_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
479set_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
509free_derives()
510{
511 FREE(derives[start_symbol]);
512 FREE(derives);
513}
514
515#ifdef DEBUG
516print_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
538set_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
587free_nullable()
588{
589 FREE(nullable);
590}
591
592
593lr0()
594{
595 set_derives();
596 set_nullable();
597 generate_states();
598}
Note: See TracBrowser for help on using the repository browser.