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