2 * Copyright (c) 1989 The Regents of the University of California.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 static char sccsid
[] = "@(#)lalr.c 5.3 (Berkeley) 6/1/90";
55 short *accessing_symbol
;
58 reductions
**reduction_table
;
64 transpose (short **R
, int n
);
70 static short **includes
;
71 static shorts
**lookback
;
74 static short *VERTICES
;
78 set_state_table (void);
81 set_accessing_symbol (void);
84 set_shift_table (void);
87 set_reduction_table (void);
102 build_relations (void);
105 compute_FOLLOWS (void);
108 compute_lookaheads (void);
114 digraph (short **relation
);
117 add_lookback_edge (int stateno
, int ruleno
, int gotono
);
122 tokensetsize
= WORDSIZE(ntokens
);
125 set_accessing_symbol();
127 set_reduction_table();
134 compute_lookaheads();
138 set_state_table (void)
142 state_table
= NEW2(nstates
, core
*);
143 for (sp
= first_state
; sp
; sp
= sp
->next
)
144 state_table
[sp
->number
] = sp
;
148 set_accessing_symbol (void)
152 accessing_symbol
= NEW2(nstates
, short);
153 for (sp
= first_state
; sp
; sp
= sp
->next
)
154 accessing_symbol
[sp
->number
] = sp
->accessing_symbol
;
158 set_shift_table (void)
162 shift_table
= NEW2(nstates
, shifts
*);
163 for (sp
= first_shift
; sp
; sp
= sp
->next
)
164 shift_table
[sp
->number
] = sp
;
168 set_reduction_table (void)
170 register reductions
*rp
;
172 reduction_table
= NEW2(nstates
, reductions
*);
173 for (rp
= first_reduction
; rp
; rp
= rp
->next
)
174 reduction_table
[rp
->number
] = rp
;
180 register short *itemp
;
181 register short *item_end
;
187 item_end
= ritem
+ nitems
;
188 for (itemp
= ritem
; itemp
< item_end
; itemp
++)
196 if (length
> max
) max
= length
;
207 register int i
, j
, k
;
208 register reductions
*rp
;
210 lookaheads
= NEW2(nstates
+ 1, short);
213 for (i
= 0; i
< nstates
; i
++)
216 rp
= reduction_table
[i
];
220 lookaheads
[nstates
] = k
;
222 LA
= NEW2(k
* tokensetsize
, unsigned);
223 LAruleno
= NEW2(k
, short);
224 lookback
= NEW2(k
, shorts
*);
227 for (i
= 0; i
< nstates
; i
++)
229 rp
= reduction_table
[i
];
232 for (j
= 0; j
< rp
->nreds
; j
++)
234 LAruleno
[k
] = rp
->rules
[j
];
248 register short *temp_map
;
252 goto_map
= NEW2(nvars
+ 1, short) - ntokens
;
253 temp_map
= NEW2(nvars
+ 1, short) - ntokens
;
256 for (sp
= first_shift
; sp
; sp
= sp
->next
)
258 for (i
= sp
->nshifts
- 1; i
>= 0; i
--)
260 symbol
= accessing_symbol
[sp
->shift
[i
]];
262 if (ISTOKEN(symbol
)) break;
264 if (ngotos
== MAXSHORT
)
265 fatal("too many gotos");
273 for (i
= ntokens
; i
< nsyms
; i
++)
279 for (i
= ntokens
; i
< nsyms
; i
++)
280 goto_map
[i
] = temp_map
[i
];
282 goto_map
[nsyms
] = ngotos
;
283 temp_map
[nsyms
] = ngotos
;
285 from_state
= NEW2(ngotos
, short);
286 to_state
= NEW2(ngotos
, short);
288 for (sp
= first_shift
; sp
; sp
= sp
->next
)
291 for (i
= sp
->nshifts
- 1; i
>= 0; i
--)
293 state2
= sp
->shift
[i
];
294 symbol
= accessing_symbol
[state2
];
296 if (ISTOKEN(symbol
)) break;
298 k
= temp_map
[symbol
]++;
299 from_state
[k
] = state1
;
300 to_state
[k
] = state2
;
304 FREE(temp_map
+ ntokens
);
309 /* Map_goto maps a state/symbol pair into its numeric representation. */
312 map_goto (int state
, int symbol
)
319 low
= goto_map
[symbol
];
320 high
= goto_map
[symbol
+ 1];
325 middle
= (low
+ high
) >> 1;
326 s
= from_state
[middle
];
343 register short *edge
;
344 register unsigned *rowp
;
346 register short **reads
;
348 register int stateno
;
352 nwords
= ngotos
* tokensetsize
;
353 F
= NEW2(nwords
, unsigned);
355 reads
= NEW2(ngotos
, short *);
356 edge
= NEW2(ngotos
+ 1, short);
360 for (i
= 0; i
< ngotos
; i
++)
362 stateno
= to_state
[i
];
363 sp
= shift_table
[stateno
];
369 for (j
= 0; j
< k
; j
++)
371 symbol
= accessing_symbol
[sp
->shift
[j
]];
374 SETBIT(rowp
, symbol
);
379 symbol
= accessing_symbol
[sp
->shift
[j
]];
380 if (nullable
[symbol
])
381 edge
[nedges
++] = map_goto(stateno
, symbol
);
386 reads
[i
] = rp
= NEW2(nedges
+ 1, short);
388 for (j
= 0; j
< nedges
; j
++)
396 rowp
+= tokensetsize
;
402 for (i
= 0; i
< ngotos
; i
++)
413 build_relations (void)
418 register short *rulep
;
425 register int stateno
;
426 register int symbol1
;
427 register int symbol2
;
428 register short *shortp
;
429 register short *edge
;
430 register short *states
;
431 register short **new_includes
;
433 includes
= NEW2(ngotos
, short *);
434 edge
= NEW2(ngotos
+ 1, short);
435 states
= NEW2(maxrhs
+ 1, short);
437 for (i
= 0; i
< ngotos
; i
++)
440 state1
= from_state
[i
];
441 symbol1
= accessing_symbol
[to_state
[i
]];
443 for (rulep
= derives
[symbol1
]; *rulep
>= 0; rulep
++)
449 for (rp
= ritem
+ rrhs
[*rulep
]; *rp
>= 0; rp
++)
452 sp
= shift_table
[stateno
];
455 for (j
= 0; j
< k
; j
++)
457 stateno
= sp
->shift
[j
];
458 if (accessing_symbol
[stateno
] == symbol2
) break;
461 states
[length
++] = stateno
;
464 add_lookback_edge(stateno
, *rulep
, i
);
474 stateno
= states
[--length
];
475 edge
[nedges
++] = map_goto(stateno
, *rp
);
476 if (nullable
[*rp
] && length
> 0) done
= 0;
483 includes
[i
] = shortp
= NEW2(nedges
+ 1, short);
484 for (j
= 0; j
< nedges
; j
++)
490 new_includes
= transpose(includes
, ngotos
);
492 for (i
= 0; i
< ngotos
; i
++)
498 includes
= new_includes
;
505 add_lookback_edge (int stateno
, int ruleno
, int gotono
)
511 i
= lookaheads
[stateno
];
512 k
= lookaheads
[stateno
+ 1];
514 while (!found
&& i
< k
)
516 if (LAruleno
[i
] == ruleno
)
524 sp
->next
= lookback
[i
];
530 transpose (short **R
, int n
)
532 register short **new_R
;
533 register short **temp_R
;
534 register short *nedges
;
539 nedges
= NEW2(n
, short);
541 for (i
= 0; i
< n
; i
++)
551 new_R
= NEW2(n
, short *);
552 temp_R
= NEW2(n
, short *);
554 for (i
= 0; i
< n
; i
++)
559 sp
= NEW2(k
+ 1, short);
568 for (i
= 0; i
< n
; i
++)
574 *temp_R
[*sp
++]++ = i
;
584 compute_FOLLOWS (void)
590 compute_lookaheads (void)
593 register unsigned *fp1
, *fp2
, *fp3
;
594 register shorts
*sp
, *next
;
595 register unsigned *rowp
;
598 n
= lookaheads
[nstates
];
599 for (i
= 0; i
< n
; i
++)
601 fp3
= rowp
+ tokensetsize
;
602 for (sp
= lookback
[i
]; sp
; sp
= sp
->next
)
605 fp2
= F
+ tokensetsize
* sp
->value
;
612 for (i
= 0; i
< n
; i
++)
613 for (sp
= lookback
[i
]; sp
; sp
= next
)
624 digraph (short **relation
)
628 infinity
= ngotos
+ 2;
629 INDEX
= NEW2(ngotos
+ 1, short);
630 VERTICES
= NEW2(ngotos
+ 1, short);
635 for (i
= 0; i
< ngotos
; i
++)
638 for (i
= 0; i
< ngotos
; i
++)
640 if (INDEX
[i
] == 0 && R
[i
])
651 register unsigned *fp1
;
652 register unsigned *fp2
;
653 register unsigned *fp3
;
661 INDEX
[i
] = height
= top
;
663 base
= F
+ i
* tokensetsize
;
664 fp3
= base
+ tokensetsize
;
669 while ((j
= *rp
++) >= 0)
674 if (INDEX
[i
] > INDEX
[j
])
678 fp2
= F
+ j
* tokensetsize
;
685 if (INDEX
[i
] == height
)
696 fp2
= F
+ j
* tokensetsize
;