fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase
Log | Files | Refs

mkpar.c (7845B)


      1 /* $OpenBSD: mkpar.c,v 1.18 2014/03/13 00:59:34 tedu Exp $	 */
      2 /* $NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 jtc Exp $	 */
      3 
      4 /*
      5  * Copyright (c) 1989 The Regents of the University of California.
      6  * All rights reserved.
      7  *
      8  * This code is derived from software contributed to Berkeley by
      9  * Robert Paul Corbett.
     10  *
     11  * Redistribution and use in source and binary forms, with or without
     12  * modification, are permitted provided that the following conditions
     13  * are met:
     14  * 1. Redistributions of source code must retain the above copyright
     15  *    notice, this list of conditions and the following disclaimer.
     16  * 2. Redistributions in binary form must reproduce the above copyright
     17  *    notice, this list of conditions and the following disclaimer in the
     18  *    documentation and/or other materials provided with the distribution.
     19  * 3. Neither the name of the University nor the names of its contributors
     20  *    may be used to endorse or promote products derived from this software
     21  *    without specific prior written permission.
     22  *
     23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     33  * SUCH DAMAGE.
     34  */
     35 
     36 #include "defs.h"
     37 
     38 action **parser;
     39 int SRtotal;
     40 int SRexpect = 0;
     41 int RRtotal;
     42 short *SRconflicts;
     43 short *RRconflicts;
     44 short *defred;
     45 short *rules_used;
     46 short nunused;
     47 short final_state;
     48 
     49 static int SRcount;
     50 static int RRcount;
     51 
     52 extern action *parse_actions();
     53 extern action *get_shifts();
     54 extern action *add_reductions();
     55 extern action *add_reduce();
     56 
     57 short sole_reduction(int);
     58 void free_action_row(action *);
     59 
     60 void find_final_state(void);
     61 void unused_rules(void);
     62 void remove_conflicts(void);
     63 void total_conflicts(void);
     64 void defreds(void);
     65 
     66 
     67 void
     68 make_parser(void)
     69 {
     70 	int i;
     71 
     72 	parser = NEW2(nstates, action *);
     73 	for (i = 0; i < nstates; i++)
     74 		parser[i] = parse_actions(i);
     75 
     76 	find_final_state();
     77 	remove_conflicts();
     78 	unused_rules();
     79 	if (SRtotal + RRtotal > 0)
     80 		total_conflicts();
     81 	defreds();
     82 }
     83 
     84 
     85 action *
     86 parse_actions(int stateno)
     87 {
     88 	action *actions;
     89 
     90 	actions = get_shifts(stateno);
     91 	actions = add_reductions(stateno, actions);
     92 	return (actions);
     93 }
     94 
     95 
     96 action *
     97 get_shifts(int stateno)
     98 {
     99 	action *actions, *temp;
    100 	shifts *sp;
    101 	short *to_state;
    102 	int i, k;
    103 	int symbol;
    104 
    105 	actions = 0;
    106 	sp = shift_table[stateno];
    107 	if (sp) {
    108 		to_state = sp->shift;
    109 		for (i = sp->nshifts - 1; i >= 0; i--) {
    110 			k = to_state[i];
    111 			symbol = accessing_symbol[k];
    112 			if (ISTOKEN(symbol)) {
    113 				temp = NEW(action);
    114 				temp->next = actions;
    115 				temp->symbol = symbol;
    116 				temp->number = k;
    117 				temp->prec = symbol_prec[symbol];
    118 				temp->action_code = SHIFT;
    119 				temp->assoc = symbol_assoc[symbol];
    120 				actions = temp;
    121 			}
    122 		}
    123 	}
    124 	return (actions);
    125 }
    126 
    127 action *
    128 add_reductions(int stateno, action * actions)
    129 {
    130 	int i, j, m, n;
    131 	int ruleno, tokensetsize;
    132 	unsigned *rowp;
    133 
    134 	tokensetsize = WORDSIZE(ntokens);
    135 	m = lookaheads[stateno];
    136 	n = lookaheads[stateno + 1];
    137 	for (i = m; i < n; i++) {
    138 		ruleno = LAruleno[i];
    139 		rowp = LA + i * tokensetsize;
    140 		for (j = ntokens - 1; j >= 0; j--) {
    141 			if (BIT(rowp, j))
    142 				actions = add_reduce(actions, ruleno, j);
    143 		}
    144 	}
    145 	return (actions);
    146 }
    147 
    148 
    149 action *
    150 add_reduce(action * actions, int ruleno, int symbol)
    151 {
    152 	action *temp, *prev, *next;
    153 
    154 	prev = 0;
    155 	for (next = actions; next && next->symbol < symbol; next = next->next)
    156 		prev = next;
    157 
    158 	while (next && next->symbol == symbol && next->action_code == SHIFT) {
    159 		prev = next;
    160 		next = next->next;
    161 	}
    162 
    163 	while (next && next->symbol == symbol &&
    164 	    next->action_code == REDUCE && next->number < ruleno) {
    165 		prev = next;
    166 		next = next->next;
    167 	}
    168 
    169 	temp = NEW(action);
    170 	temp->next = next;
    171 	temp->symbol = symbol;
    172 	temp->number = ruleno;
    173 	temp->prec = rprec[ruleno];
    174 	temp->action_code = REDUCE;
    175 	temp->assoc = rassoc[ruleno];
    176 
    177 	if (prev)
    178 		prev->next = temp;
    179 	else
    180 		actions = temp;
    181 
    182 	return (actions);
    183 }
    184 
    185 
    186 void
    187 find_final_state(void)
    188 {
    189 	int goal, i;
    190 	short *to_state;
    191 	shifts *p;
    192 
    193 	p = shift_table[0];
    194 	to_state = p->shift;
    195 	goal = ritem[1];
    196 	for (i = p->nshifts - 1; i >= 0; --i) {
    197 		final_state = to_state[i];
    198 		if (accessing_symbol[final_state] == goal)
    199 			break;
    200 	}
    201 }
    202 
    203 
    204 void
    205 unused_rules(void)
    206 {
    207 	int i;
    208 	action *p;
    209 
    210 	rules_used = calloc(nrules, sizeof(short));
    211 	if (rules_used == NULL)
    212 		no_space();
    213 
    214 	for (i = 0; i < nstates; ++i) {
    215 		for (p = parser[i]; p; p = p->next) {
    216 			if (p->action_code == REDUCE && p->suppressed == 0)
    217 				rules_used[p->number] = 1;
    218 		}
    219 	}
    220 
    221 	nunused = 0;
    222 	for (i = 3; i < nrules; ++i)
    223 		if (!rules_used[i])
    224 			++nunused;
    225 
    226 	if (nunused) {
    227 		if (nunused == 1)
    228 			fprintf(stderr, "%s: 1 rule never reduced\n", __progname);
    229 		else
    230 			fprintf(stderr, "%s: %d rules never reduced\n", __progname,
    231 				nunused);
    232 	}
    233 }
    234 
    235 
    236 void
    237 remove_conflicts(void)
    238 {
    239 	int i;
    240 	int symbol;
    241 	action *p, *pref = NULL;
    242 
    243 	SRtotal = 0;
    244 	RRtotal = 0;
    245 	SRconflicts = NEW2(nstates, short);
    246 	RRconflicts = NEW2(nstates, short);
    247 	for (i = 0; i < nstates; i++) {
    248 		SRcount = 0;
    249 		RRcount = 0;
    250 		symbol = -1;
    251 		for (p = parser[i]; p; p = p->next) {
    252 			if (p->symbol != symbol) {
    253 				pref = p;
    254 				symbol = p->symbol;
    255 			} else if (i == final_state && symbol == 0) {
    256 				SRcount++;
    257 				p->suppressed = 1;
    258 			} else if (pref->action_code == SHIFT) {
    259 				if (pref->prec > 0 && p->prec > 0) {
    260 					if (pref->prec < p->prec) {
    261 						pref->suppressed = 2;
    262 						pref = p;
    263 					} else if (pref->prec > p->prec) {
    264 						p->suppressed = 2;
    265 					} else if (pref->assoc == LEFT) {
    266 						pref->suppressed = 2;
    267 						pref = p;
    268 					} else if (pref->assoc == RIGHT) {
    269 						p->suppressed = 2;
    270 					} else {
    271 						pref->suppressed = 2;
    272 						p->suppressed = 2;
    273 					}
    274 				} else {
    275 					SRcount++;
    276 					p->suppressed = 1;
    277 				}
    278 			} else {
    279 				RRcount++;
    280 				p->suppressed = 1;
    281 			}
    282 		}
    283 		SRtotal += SRcount;
    284 		RRtotal += RRcount;
    285 		SRconflicts[i] = SRcount;
    286 		RRconflicts[i] = RRcount;
    287 	}
    288 }
    289 
    290 
    291 void
    292 total_conflicts(void)
    293 {
    294 	/* Warn if s/r != expect or if any r/r */
    295 	if ((SRtotal != SRexpect) || RRtotal) {
    296 		if (SRtotal == 1)
    297 			fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
    298 				input_file_name, __progname);
    299 		else if (SRtotal > 1)
    300 			fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
    301 				input_file_name, __progname, SRtotal);
    302 	}
    303 	if (RRtotal == 1)
    304 		fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
    305 			input_file_name, __progname);
    306 	else if (RRtotal > 1)
    307 		fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
    308 			input_file_name, __progname, RRtotal);
    309 }
    310 
    311 
    312 short
    313 sole_reduction(int stateno)
    314 {
    315 	int count;
    316 	short ruleno;
    317 	action *p;
    318 
    319 	count = 0;
    320 	ruleno = 0;
    321 	for (p = parser[stateno]; p; p = p->next) {
    322 		if (p->action_code == SHIFT && p->suppressed == 0)
    323 			return (0);
    324 		else if (p->action_code == REDUCE && p->suppressed == 0) {
    325 			if (ruleno > 0 && p->number != ruleno)
    326 				return (0);
    327 			if (p->symbol != 1)
    328 				++count;
    329 			ruleno = p->number;
    330 		}
    331 	}
    332 
    333 	if (count == 0)
    334 		return (0);
    335 	return (ruleno);
    336 }
    337 
    338 
    339 void
    340 defreds(void)
    341 {
    342 	int i;
    343 
    344 	defred = NEW2(nstates, short);
    345 	for (i = 0; i < nstates; i++)
    346 		defred[i] = sole_reduction(i);
    347 }
    348 
    349 void
    350 free_action_row(action * p)
    351 {
    352 	action *q;
    353 
    354 	while (p) {
    355 		q = p->next;
    356 		free(p);
    357 		p = q;
    358 	}
    359 }
    360 
    361 void
    362 free_parser(void)
    363 {
    364 	int i;
    365 
    366 	for (i = 0; i < nstates; i++)
    367 		free_action_row(parser[i]);
    368 
    369 	free(parser);
    370 }