source: trunk/minix/commands/byacc/lalr.c@ 20

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

Minix 3.1.2a
File size: 10.0 KB
Line 
1#include "defs.h"
2
3typedef
4 struct shorts
5 {
6 struct shorts *next;
7 short value;
8 }
9 shorts;
10
11int tokensetsize;
12short *lookaheads;
13short *LAruleno;
14unsigned *LA;
15short *accessing_symbol;
16core **state_table;
17shifts **shift_table;
18reductions **reduction_table;
19short *goto_map;
20short *from_state;
21short *to_state;
22
23short **transpose();
24
25static int infinity;
26static int maxrhs;
27static int ngotos;
28static unsigned *F;
29static short **includes;
30static shorts **lookback;
31static short **R;
32static short *INDEX;
33static short *VERTICES;
34static int top;
35
36
37lalr()
38{
39 tokensetsize = WORDSIZE(ntokens);
40
41 set_state_table();
42 set_accessing_symbol();
43 set_shift_table();
44 set_reduction_table();
45 set_maxrhs();
46 initialize_LA();
47 set_goto_map();
48 initialize_F();
49 build_relations();
50 compute_FOLLOWS();
51 compute_lookaheads();
52}
53
54
55
56set_state_table()
57{
58 register core *sp;
59
60 state_table = NEW2(nstates, core *);
61 for (sp = first_state; sp; sp = sp->next)
62 state_table[sp->number] = sp;
63}
64
65
66
67set_accessing_symbol()
68{
69 register core *sp;
70
71 accessing_symbol = NEW2(nstates, short);
72 for (sp = first_state; sp; sp = sp->next)
73 accessing_symbol[sp->number] = sp->accessing_symbol;
74}
75
76
77
78set_shift_table()
79{
80 register shifts *sp;
81
82 shift_table = NEW2(nstates, shifts *);
83 for (sp = first_shift; sp; sp = sp->next)
84 shift_table[sp->number] = sp;
85}
86
87
88
89set_reduction_table()
90{
91 register reductions *rp;
92
93 reduction_table = NEW2(nstates, reductions *);
94 for (rp = first_reduction; rp; rp = rp->next)
95 reduction_table[rp->number] = rp;
96}
97
98
99
100set_maxrhs()
101{
102 register short *itemp;
103 register short *item_end;
104 register int length;
105 register int max;
106
107 length = 0;
108 max = 0;
109 item_end = ritem + nitems;
110 for (itemp = ritem; itemp < item_end; itemp++)
111 {
112 if (*itemp >= 0)
113 {
114 length++;
115 }
116 else
117 {
118 if (length > max) max = length;
119 length = 0;
120 }
121 }
122
123 maxrhs = max;
124}
125
126
127
128initialize_LA()
129{
130 register int i, j, k;
131 register reductions *rp;
132
133 lookaheads = NEW2(nstates + 1, short);
134
135 k = 0;
136 for (i = 0; i < nstates; i++)
137 {
138 lookaheads[i] = k;
139 rp = reduction_table[i];
140 if (rp)
141 k += rp->nreds;
142 }
143 lookaheads[nstates] = k;
144
145 LA = NEW2(k * tokensetsize, unsigned);
146 LAruleno = NEW2(k, short);
147 lookback = NEW2(k, shorts *);
148
149 k = 0;
150 for (i = 0; i < nstates; i++)
151 {
152 rp = reduction_table[i];
153 if (rp)
154 {
155 for (j = 0; j < rp->nreds; j++)
156 {
157 LAruleno[k] = rp->rules[j];
158 k++;
159 }
160 }
161 }
162}
163
164
165set_goto_map()
166{
167 register shifts *sp;
168 register int i;
169 register int symbol;
170 register int k;
171 register short *temp_map;
172 register int state2;
173 register int state1;
174
175 goto_map = NEW2(nvars + 1, short) - ntokens;
176 temp_map = NEW2(nvars + 1, short) - ntokens;
177
178 ngotos = 0;
179 for (sp = first_shift; sp; sp = sp->next)
180 {
181 for (i = sp->nshifts - 1; i >= 0; i--)
182 {
183 symbol = accessing_symbol[sp->shift[i]];
184
185 if (ISTOKEN(symbol)) break;
186
187 if (ngotos == MAXSHORT)
188 fatal("too many gotos");
189
190 ngotos++;
191 goto_map[symbol]++;
192 }
193 }
194
195 k = 0;
196 for (i = ntokens; i < nsyms; i++)
197 {
198 temp_map[i] = k;
199 k += goto_map[i];
200 }
201
202 for (i = ntokens; i < nsyms; i++)
203 goto_map[i] = temp_map[i];
204
205 goto_map[nsyms] = ngotos;
206 temp_map[nsyms] = ngotos;
207
208 from_state = NEW2(ngotos, short);
209 to_state = NEW2(ngotos, short);
210
211 for (sp = first_shift; sp; sp = sp->next)
212 {
213 state1 = sp->number;
214 for (i = sp->nshifts - 1; i >= 0; i--)
215 {
216 state2 = sp->shift[i];
217 symbol = accessing_symbol[state2];
218
219 if (ISTOKEN(symbol)) break;
220
221 k = temp_map[symbol]++;
222 from_state[k] = state1;
223 to_state[k] = state2;
224 }
225 }
226
227 FREE(temp_map + ntokens);
228}
229
230
231
232/* Map_goto maps a state/symbol pair into its numeric representation. */
233
234int
235map_goto(state, symbol)
236int state;
237int symbol;
238{
239 register int high;
240 register int low;
241 register int middle;
242 register int s;
243
244 low = goto_map[symbol];
245 high = goto_map[symbol + 1];
246
247 for (;;)
248 {
249 assert(low <= high);
250 middle = (low + high) >> 1;
251 s = from_state[middle];
252 if (s == state)
253 return (middle);
254 else if (s < state)
255 low = middle + 1;
256 else
257 high = middle - 1;
258 }
259}
260
261
262
263initialize_F()
264{
265 register int i;
266 register int j;
267 register int k;
268 register shifts *sp;
269 register short *edge;
270 register unsigned *rowp;
271 register short *rp;
272 register short **reads;
273 register int nedges;
274 register int stateno;
275 register int symbol;
276 register int nwords;
277
278 nwords = ngotos * tokensetsize;
279 F = NEW2(nwords, unsigned);
280
281 reads = NEW2(ngotos, short *);
282 edge = NEW2(ngotos + 1, short);
283 nedges = 0;
284
285 rowp = F;
286 for (i = 0; i < ngotos; i++)
287 {
288 stateno = to_state[i];
289 sp = shift_table[stateno];
290
291 if (sp)
292 {
293 k = sp->nshifts;
294
295 for (j = 0; j < k; j++)
296 {
297 symbol = accessing_symbol[sp->shift[j]];
298 if (ISVAR(symbol))
299 break;
300 SETBIT(rowp, symbol);
301 }
302
303 for (; j < k; j++)
304 {
305 symbol = accessing_symbol[sp->shift[j]];
306 if (nullable[symbol])
307 edge[nedges++] = map_goto(stateno, symbol);
308 }
309
310 if (nedges)
311 {
312 reads[i] = rp = NEW2(nedges + 1, short);
313
314 for (j = 0; j < nedges; j++)
315 rp[j] = edge[j];
316
317 rp[nedges] = -1;
318 nedges = 0;
319 }
320 }
321
322 rowp += tokensetsize;
323 }
324
325 SETBIT(F, 0);
326 digraph(reads);
327
328 for (i = 0; i < ngotos; i++)
329 {
330 if (reads[i])
331 FREE(reads[i]);
332 }
333
334 FREE(reads);
335 FREE(edge);
336}
337
338
339
340build_relations()
341{
342 register int i;
343 register int j;
344 register int k;
345 register short *rulep;
346 register short *rp;
347 register shifts *sp;
348 register int length;
349 register int nedges;
350 register int done;
351 register int state1;
352 register int stateno;
353 register int symbol1;
354 register int symbol2;
355 register short *shortp;
356 register short *edge;
357 register short *states;
358 register short **new_includes;
359
360 includes = NEW2(ngotos, short *);
361 edge = NEW2(ngotos + 1, short);
362 states = NEW2(maxrhs + 1, short);
363
364 for (i = 0; i < ngotos; i++)
365 {
366 nedges = 0;
367 state1 = from_state[i];
368 symbol1 = accessing_symbol[to_state[i]];
369
370 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
371 {
372 length = 1;
373 states[0] = state1;
374 stateno = state1;
375
376 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
377 {
378 symbol2 = *rp;
379 sp = shift_table[stateno];
380 k = sp->nshifts;
381
382 for (j = 0; j < k; j++)
383 {
384 stateno = sp->shift[j];
385 if (accessing_symbol[stateno] == symbol2) break;
386 }
387
388 states[length++] = stateno;
389 }
390
391 add_lookback_edge(stateno, *rulep, i);
392
393 length--;
394 done = 0;
395 while (!done)
396 {
397 done = 1;
398 rp--;
399 if (ISVAR(*rp))
400 {
401 stateno = states[--length];
402 edge[nedges++] = map_goto(stateno, *rp);
403 if (nullable[*rp] && length > 0) done = 0;
404 }
405 }
406 }
407
408 if (nedges)
409 {
410 includes[i] = shortp = NEW2(nedges + 1, short);
411 for (j = 0; j < nedges; j++)
412 shortp[j] = edge[j];
413 shortp[nedges] = -1;
414 }
415 }
416
417 new_includes = transpose(includes, ngotos);
418
419 for (i = 0; i < ngotos; i++)
420 if (includes[i])
421 FREE(includes[i]);
422
423 FREE(includes);
424
425 includes = new_includes;
426
427 FREE(edge);
428 FREE(states);
429}
430
431
432add_lookback_edge(stateno, ruleno, gotono)
433int stateno, ruleno, gotono;
434{
435 register int i, k;
436 register int found;
437 register shorts *sp;
438
439 i = lookaheads[stateno];
440 k = lookaheads[stateno + 1];
441 found = 0;
442 while (!found && i < k)
443 {
444 if (LAruleno[i] == ruleno)
445 found = 1;
446 else
447 ++i;
448 }
449 assert(found);
450
451 sp = NEW(shorts);
452 sp->next = lookback[i];
453 sp->value = gotono;
454 lookback[i] = sp;
455}
456
457
458
459short **
460transpose(R, n)
461short **R;
462int n;
463{
464 register short **new_R;
465 register short **temp_R;
466 register short *nedges;
467 register short *sp;
468 register int i;
469 register int k;
470
471 nedges = NEW2(n, short);
472
473 for (i = 0; i < n; i++)
474 {
475 sp = R[i];
476 if (sp)
477 {
478 while (*sp >= 0)
479 nedges[*sp++]++;
480 }
481 }
482
483 new_R = NEW2(n, short *);
484 temp_R = NEW2(n, short *);
485
486 for (i = 0; i < n; i++)
487 {
488 k = nedges[i];
489 if (k > 0)
490 {
491 sp = NEW2(k + 1, short);
492 new_R[i] = sp;
493 temp_R[i] = sp;
494 sp[k] = -1;
495 }
496 }
497
498 FREE(nedges);
499
500 for (i = 0; i < n; i++)
501 {
502 sp = R[i];
503 if (sp)
504 {
505 while (*sp >= 0)
506 *temp_R[*sp++]++ = i;
507 }
508 }
509
510 FREE(temp_R);
511
512 return (new_R);
513}
514
515
516
517compute_FOLLOWS()
518{
519 digraph(includes);
520}
521
522
523compute_lookaheads()
524{
525 register int i, n;
526 register unsigned *fp1, *fp2, *fp3;
527 register shorts *sp, *next;
528 register unsigned *rowp;
529
530 rowp = LA;
531 n = lookaheads[nstates];
532 for (i = 0; i < n; i++)
533 {
534 fp3 = rowp + tokensetsize;
535 for (sp = lookback[i]; sp; sp = sp->next)
536 {
537 fp1 = rowp;
538 fp2 = F + tokensetsize * sp->value;
539 while (fp1 < fp3)
540 *fp1++ |= *fp2++;
541 }
542 rowp = fp3;
543 }
544
545 for (i = 0; i < n; i++)
546 for (sp = lookback[i]; sp; sp = next)
547 {
548 next = sp->next;
549 FREE(sp);
550 }
551
552 FREE(lookback);
553 FREE(F);
554}
555
556
557digraph(relation)
558short **relation;
559{
560 register int i;
561
562 infinity = ngotos + 2;
563 INDEX = NEW2(ngotos + 1, short);
564 VERTICES = NEW2(ngotos + 1, short);
565 top = 0;
566
567 R = relation;
568
569 for (i = 0; i < ngotos; i++)
570 INDEX[i] = 0;
571
572 for (i = 0; i < ngotos; i++)
573 {
574 if (INDEX[i] == 0 && R[i])
575 traverse(i);
576 }
577
578 FREE(INDEX);
579 FREE(VERTICES);
580}
581
582
583
584traverse(i)
585register int i;
586{
587 register unsigned *fp1;
588 register unsigned *fp2;
589 register unsigned *fp3;
590 register int j;
591 register short *rp;
592
593 int height;
594 unsigned *base;
595
596 VERTICES[++top] = i;
597 INDEX[i] = height = top;
598
599 base = F + i * tokensetsize;
600 fp3 = base + tokensetsize;
601
602 rp = R[i];
603 if (rp)
604 {
605 while ((j = *rp++) >= 0)
606 {
607 if (INDEX[j] == 0)
608 traverse(j);
609
610 if (INDEX[i] > INDEX[j])
611 INDEX[i] = INDEX[j];
612
613 fp1 = base;
614 fp2 = F + j * tokensetsize;
615
616 while (fp1 < fp3)
617 *fp1++ |= *fp2++;
618 }
619 }
620
621 if (INDEX[i] == height)
622 {
623 for (;;)
624 {
625 j = VERTICES[top--];
626 INDEX[j] = infinity;
627
628 if (i == j)
629 break;
630
631 fp1 = base;
632 fp2 = F + j * tokensetsize;
633
634 while (fp1 < fp3)
635 *fp2++ = *fp1++;
636 }
637 }
638}
Note: See TracBrowser for help on using the repository browser.