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