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
[] = "@(#)mkpar.c 5.3 (Berkeley) 1/20/91";
57 parse_actions (int stateno
);
60 get_shifts (int stateno
);
63 add_reductions (int stateno
, action
*actions
);
66 add_reduce (action
*actions
, int ruleno
, int symbol
);
72 remove_conflicts (void);
75 total_conflicts (void);
78 find_final_state (void);
88 parser
= NEW2(nstates
, action
*);
89 for (i
= 0; i
< nstates
; i
++)
90 parser
[i
] = parse_actions(i
);
95 if (SRtotal
+ RRtotal
> 0) total_conflicts();
100 parse_actions (int stateno
)
102 register action
*actions
;
104 actions
= get_shifts(stateno
);
105 actions
= add_reductions(stateno
, actions
);
110 get_shifts (int stateno
)
112 register action
*actions
, *temp
;
114 register short *to_state
;
119 sp
= shift_table
[stateno
];
122 to_state
= sp
->shift
;
123 for (i
= sp
->nshifts
- 1; i
>= 0; i
--)
126 symbol
= accessing_symbol
[k
];
130 temp
->next
= actions
;
131 temp
->symbol
= symbol
;
133 temp
->prec
= symbol_prec
[symbol
];
134 temp
->action_code
= SHIFT
;
135 temp
->assoc
= symbol_assoc
[symbol
];
144 add_reductions (int stateno
, action
*actions
)
146 register int i
, j
, m
, n
;
147 register int ruleno
, tokensetsize
;
148 register unsigned *rowp
;
150 tokensetsize
= WORDSIZE(ntokens
);
151 m
= lookaheads
[stateno
];
152 n
= lookaheads
[stateno
+ 1];
153 for (i
= m
; i
< n
; i
++)
155 ruleno
= LAruleno
[i
];
156 rowp
= LA
+ i
* tokensetsize
;
157 for (j
= ntokens
- 1; j
>= 0; j
--)
160 actions
= add_reduce(actions
, ruleno
, j
);
167 add_reduce (action
*actions
, int ruleno
, int symbol
)
169 register action
*temp
, *prev
, *next
;
172 for (next
= actions
; next
&& next
->symbol
< symbol
; next
= next
->next
)
175 while (next
&& next
->symbol
== symbol
&& next
->action_code
== SHIFT
)
181 while (next
&& next
->symbol
== symbol
&&
182 next
->action_code
== REDUCE
&& next
->number
< ruleno
)
190 temp
->symbol
= symbol
;
191 temp
->number
= ruleno
;
192 temp
->prec
= rprec
[ruleno
];
193 temp
->action_code
= REDUCE
;
194 temp
->assoc
= rassoc
[ruleno
];
205 find_final_state (void)
207 register int goal
, i
;
208 register short *to_state
;
214 for (i
= p
->nshifts
- 1; i
>= 0; --i
)
216 final_state
= to_state
[i
];
217 if (accessing_symbol
[final_state
] == goal
) break;
227 rules_used
= (short *) MALLOC(nrules
*sizeof(short));
228 if (rules_used
== 0) no_space();
230 for (i
= 0; i
< nrules
; ++i
)
233 for (i
= 0; i
< nstates
; ++i
)
235 for (p
= parser
[i
]; p
; p
= p
->next
)
237 if (p
->action_code
== REDUCE
&& p
->suppressed
== 0)
238 rules_used
[p
->number
] = 1;
243 for (i
= 3; i
< nrules
; ++i
)
244 if (!rules_used
[i
]) ++nunused
;
249 fprintf(stderr
, "%s: 1 rule never reduced\n", myname
);
251 fprintf(stderr
, "%s: %d rules never reduced\n", myname
, nunused
);
256 remove_conflicts (void)
260 register action
*p
, *pref
;
264 SRconflicts
= NEW2(nstates
, short);
265 RRconflicts
= NEW2(nstates
, short);
266 for (i
= 0; i
< nstates
; i
++)
271 for (p
= parser
[i
]; p
; p
= p
->next
)
273 if (p
->symbol
!= symbol
)
278 else if (i
== final_state
&& symbol
== 0)
283 else if (pref
->action_code
== SHIFT
)
285 if (pref
->prec
> 0 && p
->prec
> 0)
287 if (pref
->prec
< p
->prec
)
289 pref
->suppressed
= 2;
292 else if (pref
->prec
> p
->prec
)
296 else if (pref
->assoc
== LEFT
)
298 pref
->suppressed
= 2;
301 else if (pref
->assoc
== RIGHT
)
307 pref
->suppressed
= 2;
325 SRconflicts
[i
] = SRcount
;
326 RRconflicts
[i
] = RRcount
;
331 total_conflicts (void)
333 fprintf(stderr
, "%s: ", myname
);
335 fprintf(stderr
, "1 shift/reduce conflict");
336 else if (SRtotal
> 1)
337 fprintf(stderr
, "%d shift/reduce conflicts", SRtotal
);
339 if (SRtotal
&& RRtotal
)
340 fprintf(stderr
, ", ");
343 fprintf(stderr
, "1 reduce/reduce conflict");
344 else if (RRtotal
> 1)
345 fprintf(stderr
, "%d reduce/reduce conflicts", RRtotal
);
347 fprintf(stderr
, ".\n");
351 sole_reduction (int stateno
)
353 register int count
, ruleno
;
358 for (p
= parser
[stateno
]; p
; p
= p
->next
)
360 if (p
->action_code
== SHIFT
&& p
->suppressed
== 0)
362 else if (p
->action_code
== REDUCE
&& p
->suppressed
== 0)
364 if (ruleno
> 0 && p
->number
!= ruleno
)
382 defred
= NEW2(nstates
, short);
383 for (i
= 0; i
< nstates
; i
++)
384 defred
[i
] = sole_reduction(i
);
388 free_action_row (action
*p
)
405 for (i
= 0; i
< nstates
; i
++)
406 free_action_row(parser
[i
]);