[unix-history] / usr / src / usr.bin / yacc / mkpar.c

/*
 * Copyright (c) 1989 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Robert Paul Corbett.
 *
 * %sccs.include.redist.c%
 */

#ifndef lint
static char sccsid[] = "@(#)mkpar.c	5.2 (Berkeley) %G%";
#endif /* not lint */

#include "defs.h"

action **parser;
int SRtotal;
int RRtotal;
short *SRconflicts;
short *RRconflicts;
short *defred;
short *rules_used;
short nunused;
short final_state;

static int SRcount;
static int RRcount;

extern action *parse_actions();
extern action *get_shifts();
extern action *add_reductions();
extern action *add_reduce();


make_parser()
{
    register int i;

    parser = NEW2(nstates, action *);
    for (i = 0; i < nstates; i++)
	parser[i] = parse_actions(i);

    find_final_state();
    remove_conflicts();
    unused_rules();
    if (SRtotal + RRtotal > 0) total_conflicts();
    defreds();
}


action *
parse_actions(stateno)
register int stateno;
{
    register action *actions;

    actions = get_shifts(stateno);
    actions = add_reductions(stateno, actions);
    return (actions);
}


action *
get_shifts(stateno)
int stateno;
{
    register action *actions, *temp;
    register shifts *sp;
    register short *to_state;
    register int i, k;
    register int symbol;

    actions = 0;
    sp = shift_table[stateno];
    if (sp)
    {
	to_state = sp->shift;
	for (i = sp->nshifts - 1; i >= 0; i--)
	{
	    k = to_state[i];
	    symbol = accessing_symbol[k];
	    if (ISTOKEN(symbol))
	    {
		temp = NEW(action);
		temp->next = actions;
		temp->symbol = symbol;
		temp->number = k;
		temp->prec = symbol_prec[symbol];
		temp->action_code = SHIFT;
		temp->assoc = symbol_assoc[symbol];
		actions = temp;
	    }
	}
    }
    return (actions);
}

action *
add_reductions(stateno, actions)
int stateno;
register action *actions;
{
    register int i, j, m, n;
    register int ruleno, tokensetsize;
    register unsigned *rowp;

    tokensetsize = WORDSIZE(ntokens);
    m = lookaheads[stateno];
    n = lookaheads[stateno + 1];
    for (i = m; i < n; i++)
    {
	ruleno = LAruleno[i];
	rowp = LA + i * tokensetsize;
	for (j = ntokens - 1; j >= 0; j--)
	{
	    if (BIT(rowp, j))
		actions = add_reduce(actions, ruleno, j);
	}
    }
    return (actions);
}


action *
add_reduce(actions, ruleno, symbol)
register action *actions;
register int ruleno, symbol;
{
    register action *temp, *prev, *next;

    prev = 0;
    for (next = actions; next && next->symbol < symbol; next = next->next)
	prev = next;

    while (next && next->symbol == symbol && next->action_code == SHIFT)
    {
	prev = next;
	next = next->next;
    }

    while (next && next->symbol == symbol &&
	    next->action_code == REDUCE && next->number < ruleno)
    {
	prev = next;
	next = next->next;
    }

    temp = NEW(action);
    temp->next = next;
    temp->symbol = symbol;
    temp->number = ruleno;
    temp->prec = rprec[ruleno];
    temp->action_code = REDUCE;
    temp->assoc = rassoc[ruleno];

    if (prev)
	prev->next = temp;
    else
	actions = temp;

    return (actions);
}


find_final_state()
{
    register int goal, i;
    register short *to_state;
    register shifts *p;

    p = shift_table[0];
    to_state = p->shift;
    goal = ritem[1];
    for (i = p->nshifts - 1; i >= 0; --i)
    {
	final_state = to_state[i];
	if (accessing_symbol[final_state] == goal) break;
    }
}


unused_rules()
{
    register int i;
    register action *p;

    rules_used = (short *) MALLOC(nrules*sizeof(short));
    if (rules_used == 0) no_space();

    for (i = 0; i < nrules; ++i)
	rules_used[i] = 0;

    for (i = 0; i < nstates; ++i)
    {
	for (p = parser[i]; p; p = p->next)
	{
	    if (p->action_code == REDUCE && p->suppressed == 0)
		rules_used[p->number] = 1;
	}
    }

    nunused = 0;
    for (i = 3; i < nrules; ++i)
	if (!rules_used[i]) ++nunused;

    if (nunused)
	if (nunused == 1)
	    fprintf(stderr, "%s: 1 rule never reduced\n", myname);
	else
	    fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
}


remove_conflicts()
{
    register int i;
    register int symbol;
    register action *p, *q;

    SRtotal = 0;
    RRtotal = 0;
    SRconflicts = NEW2(nstates, short);
    RRconflicts = NEW2(nstates, short);
    for (i = 0; i < nstates; i++)
    {
	SRcount = 0;
	RRcount = 0;
	for (p = parser[i]; p; p = q->next)
	{
	    symbol = p->symbol;
	    q = p;
	    while (q->next && q->next->symbol == symbol)
		q = q->next;
	    if (i == final_state && symbol == 0)
		end_conflicts(p, q);
	    else if (p != q)
		resolve_conflicts(p, q);
	}
	SRtotal += SRcount;
	RRtotal += RRcount;
	SRconflicts[i] = SRcount;
	RRconflicts[i] = RRcount;
    }
}


end_conflicts(p, q)
register action *p, *q;
{
    for (;;)
    {
	SRcount++;
	p->suppressed = 1;
	if (p == q) break;
	p = p->next;
    }
}


resolve_conflicts(first, last)
register action *first, *last;
{
    register action *p;
    register int count;

    count = 1;
    for (p = first; p != last; p = p->next)
 	++count;
    assert(count > 1);

    if (first->action_code == SHIFT && count == 2 &&
	    first->prec > 0 && last->prec > 0)
    {
	if (first->prec == last->prec)
	{
	    if (first->assoc == LEFT)
		first->suppressed = 2;
	    else if (first->assoc == RIGHT)
		last->suppressed = 2;
	    else
	    {
		first->suppressed = 2;
		last->suppressed = 2;
		first->action_code = ERROR;
		last->action_code = ERROR;
	    }
	}
	else if (first->prec < last->prec)
	    first->suppressed = 2;
	else
	    last->suppressed = 2;
    }
    else
    {
	if (first->action_code == SHIFT)
	    SRcount += (count - 1);
        else
	    RRcount += (count - 1);
	for (p = first; p != last; p = p->next, p->suppressed = 1)
	    continue;
    }
}


total_conflicts()
{
    fprintf(stderr, "%s: ", myname);
    if (SRtotal == 1)
	fprintf(stderr, "1 shift/reduce conflict");
    else if (SRtotal > 1)
	fprintf(stderr, "%d shift/reduce conflicts", SRtotal);

    if (SRtotal && RRtotal)
	fprintf(stderr, ", ");

    if (RRtotal == 1)
	fprintf(stderr, "1 reduce/reduce conflict");
    else if (RRtotal > 1)
	fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);

    fprintf(stderr, ".\n");
}


int
sole_reduction(stateno)
int stateno;
{
    register int count, ruleno;
    register action *p;

    count = 0;
    ruleno = 0; 
    for (p = parser[stateno]; p; p = p->next)
    {
	if (p->action_code == SHIFT && p->suppressed == 0)
	    return (0);
	else if (p->action_code == REDUCE && p->suppressed == 0)
	{
	    if (ruleno > 0 && p->number != ruleno)
		return (0);
	    if (p->symbol != 1)
		++count;
	    ruleno = p->number;
	}
    }

    if (count == 0)
	return (0);
    return (ruleno);
}


defreds()
{
    register int i;

    defred = NEW2(nstates, short);
    for (i = 0; i < nstates; i++)
	defred[i] = sole_reduction(i);
}
 
free_action_row(p)
register action *p;
{
  register action *q;

  while (p)
    {
      q = p->next;
      FREE(p);
      p = q;
    }
}

free_parser()
{
  register int i;

  for (i = 0; i < nstates; i++)
    free_action_row(parser[i]);

  FREE(parser);
}
Commit	Line	Data
c8bff85f KB	1	/*
	2	* Copyright (c) 1989 The Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* This code is derived from software contributed to Berkeley by
	6	* Robert Paul Corbett.
	7	*
6ecf3d85	8	* %sccs.include.redist.c%
c8bff85f KB	9	*/
	10
	11	#ifndef lint
6ecf3d85	12	static char sccsid[] = "@(#)mkpar.c 5.2 (Berkeley) %G%";
c8bff85f KB	13	#endif /* not lint */
	14
	15	#include "defs.h"
	16
	17	action **parser;
	18	int SRtotal;
	19	int RRtotal;
	20	short *SRconflicts;
	21	short *RRconflicts;
	22	short *defred;
	23	short *rules_used;
	24	short nunused;
	25	short final_state;
	26
	27	static int SRcount;
	28	static int RRcount;
	29
	30	extern action *parse_actions();
	31	extern action *get_shifts();
	32	extern action *add_reductions();
	33	extern action *add_reduce();
	34
	35
	36	make_parser()
	37	{
	38	register int i;
	39
	40	parser = NEW2(nstates, action *);
	41	for (i = 0; i < nstates; i++)
	42	parser[i] = parse_actions(i);
	43
	44	find_final_state();
	45	remove_conflicts();
	46	unused_rules();
	47	if (SRtotal + RRtotal > 0) total_conflicts();
	48	defreds();
	49	}
	50
	51
	52	action *
	53	parse_actions(stateno)
	54	register int stateno;
	55	{
	56	register action *actions;
	57
	58	actions = get_shifts(stateno);
	59	actions = add_reductions(stateno, actions);
	60	return (actions);
	61	}
	62
	63
	64	action *
	65	get_shifts(stateno)
	66	int stateno;
	67	{
	68	register action actions, temp;
	69	register shifts *sp;
	70	register short *to_state;
	71	register int i, k;
	72	register int symbol;
	73
	74	actions = 0;
	75	sp = shift_table[stateno];
	76	if (sp)
77	{
78	to_state = sp->shift;
79	for (i = sp->nshifts - 1; i >= 0; i--)
80	{
81	k = to_state[i];
82	symbol = accessing_symbol[k];
83	if (ISTOKEN(symbol))
84	{
85	temp = NEW(action);
86	temp->next = actions;
87	temp->symbol = symbol;
88	temp->number = k;
89	temp->prec = symbol_prec[symbol];
90	temp->action_code = SHIFT;
91	temp->assoc = symbol_assoc[symbol];
92	actions = temp;
93	}
94	}
95	}
96	return (actions);
97	}
98
99	action *
100	add_reductions(stateno, actions)
101	int stateno;
102	register action *actions;
103	{
104	register int i, j, m, n;
105	register int ruleno, tokensetsize;
106	register unsigned *rowp;
107
108	tokensetsize = WORDSIZE(ntokens);
109	m = lookaheads[stateno];
110	n = lookaheads[stateno + 1];
111	for (i = m; i < n; i++)
112	{
113	ruleno = LAruleno[i];
114	rowp = LA + i * tokensetsize;
115	for (j = ntokens - 1; j >= 0; j--)
116	{
117	if (BIT(rowp, j))
118	actions = add_reduce(actions, ruleno, j);
119	}
120	}
121	return (actions);
122	}
123
124
125	action *
126	add_reduce(actions, ruleno, symbol)
127	register action *actions;
128	register int ruleno, symbol;
129	{
130	register action temp, prev, *next;
131
132	prev = 0;
133	for (next = actions; next && next->symbol < symbol; next = next->next)
134	prev = next;
135
136	while (next && next->symbol == symbol && next->action_code == SHIFT)
137	{
138	prev = next;
139	next = next->next;
140	}
141
142	while (next && next->symbol == symbol &&
143	next->action_code == REDUCE && next->number < ruleno)
144	{
145	prev = next;
146	next = next->next;
147	}
148
149	temp = NEW(action);
150	temp->next = next;
151	temp->symbol = symbol;
152	temp->number = ruleno;
153	temp->prec = rprec[ruleno];
154	temp->action_code = REDUCE;
155	temp->assoc = rassoc[ruleno];
156
157	if (prev)
158	prev->next = temp;
159	else
160	actions = temp;
161
162	return (actions);
163	}
164
165
166	find_final_state()
167	{
168	register int goal, i;
169	register short *to_state;
170	register shifts *p;
171
172	p = shift_table[0];
173	to_state = p->shift;
174	goal = ritem[1];
175	for (i = p->nshifts - 1; i >= 0; --i)
176	{
177	final_state = to_state[i];
178	if (accessing_symbol[final_state] == goal) break;
179	}
180	}
181
182
183	unused_rules()
184	{
185	register int i;
186	register action *p;
187
188	rules_used = (short ) MALLOC(nrulessizeof(short));
189	if (rules_used == 0) no_space();
190
191	for (i = 0; i < nrules; ++i)
192	rules_used[i] = 0;
193
194	for (i = 0; i < nstates; ++i)
195	{
196	for (p = parser[i]; p; p = p->next)
197	{
198	if (p->action_code == REDUCE && p->suppressed == 0)
199	rules_used[p->number] = 1;
200	}
201	}
202
203	nunused = 0;
204	for (i = 3; i < nrules; ++i)
205	if (!rules_used[i]) ++nunused;
206
207	if (nunused)
208	if (nunused == 1)
209	fprintf(stderr, "%s: 1 rule never reduced\n", myname);
210	else
211	fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
212	}
213
214
215	remove_conflicts()
216	{
217	register int i;
218	register int symbol;
219	register action p, q;
220
221	SRtotal = 0;
222	RRtotal = 0;
223	SRconflicts = NEW2(nstates, short);
224	RRconflicts = NEW2(nstates, short);
225	for (i = 0; i < nstates; i++)
226	{
227	SRcount = 0;
228	RRcount = 0;
229	for (p = parser[i]; p; p = q->next)
230	{
231	symbol = p->symbol;
232	q = p;
233	while (q->next && q->next->symbol == symbol)
234	q = q->next;
235	if (i == final_state && symbol == 0)
236	end_conflicts(p, q);
237	else if (p != q)
238	resolve_conflicts(p, q);
239	}
240	SRtotal += SRcount;
241	RRtotal += RRcount;
242	SRconflicts[i] = SRcount;
243	RRconflicts[i] = RRcount;
244	}
245	}
246
247
248	end_conflicts(p, q)
249	register action p, q;
250	{
251	for (;;)
252	{
253	SRcount++;
254	p->suppressed = 1;
255	if (p == q) break;
256	p = p->next;
257	}
258	}
259
260
261	resolve_conflicts(first, last)
262	register action first, last;
263	{
264	register action *p;
265	register int count;
266
267	count = 1;
268	for (p = first; p != last; p = p->next)
269	++count;
270	assert(count > 1);
271
272	if (first->action_code == SHIFT && count == 2 &&
273	first->prec > 0 && last->prec > 0)
274	{
275	if (first->prec == last->prec)
276	{
277	if (first->assoc == LEFT)
278	first->suppressed = 2;
279	else if (first->assoc == RIGHT)
280	last->suppressed = 2;
281	else
282	{
283	first->suppressed = 2;
284	last->suppressed = 2;
285	first->action_code = ERROR;
286	last->action_code = ERROR;
287	}
288	}
289	else if (first->prec < last->prec)
290	first->suppressed = 2;
291	else
292	last->suppressed = 2;
293	}
294	else
295	{
296	if (first->action_code == SHIFT)
297	SRcount += (count - 1);
298	else
299	RRcount += (count - 1);
300	for (p = first; p != last; p = p->next, p->suppressed = 1)
301	continue;
302	}
303	}
304
305
306	total_conflicts()
307	{
308	fprintf(stderr, "%s: ", myname);
309	if (SRtotal == 1)
310	fprintf(stderr, "1 shift/reduce conflict");
311	else if (SRtotal > 1)
312	fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
313
314	if (SRtotal && RRtotal)
315	fprintf(stderr, ", ");
316
317	if (RRtotal == 1)
318	fprintf(stderr, "1 reduce/reduce conflict");
319	else if (RRtotal > 1)
320	fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
321
322	fprintf(stderr, ".\n");
323	}
324
325
326	int
327	sole_reduction(stateno)
328	int stateno;
329	{
330	register int count, ruleno;
331	register action *p;
332
333	count = 0;
334	ruleno = 0;
335	for (p = parser[stateno]; p; p = p->next)
336	{
337	if (p->action_code == SHIFT && p->suppressed == 0)
338	return (0);
339	else if (p->action_code == REDUCE && p->suppressed == 0)
340	{
341	if (ruleno > 0 && p->number != ruleno)
342	return (0);
343	if (p->symbol != 1)
344	++count;
345	ruleno = p->number;
346	}
347	}
348
349	if (count == 0)
350	return (0);
351	return (ruleno);
352	}
353
354
355	defreds()
356	{
357	register int i;
358
359	defred = NEW2(nstates, short);
360	for (i = 0; i < nstates; i++)
361	defred[i] = sole_reduction(i);
362	}
363
364	free_action_row(p)
365	register action *p;
366	{
367	register action *q;
368
369	while (p)
370	{
371	q = p->next;
372	FREE(p);
373	p = q;
374	}
375	}
376
377	free_parser()
378	{
379	register int i;
380
381	for (i = 0; i < nstates; i++)
382	free_action_row(parser[i]);
383
384	FREE(parser);
385	}