#include "defs.h"static int nvectors;static int nentries;static short **froms;static short **tos;static short *tally;static short *width;static short *state_count;static short *order;static short *base;static short *pos;static int maxtable;static short *table;static short *check;static int lowzero;static int high;output(){    free_itemsets();    free_shifts();    free_reductions();    output_prefix();    output_stored_text();    output_defines();    output_rule_data();    output_yydefred();    output_actions();    free_parser();    output_debug();    output_stype();    if (rflag) write_section(tables);    write_section(header);    output_trailing_text();    write_section(body);    output_semantic_actions();    write_section(trailer);}output_prefix(){    if (symbol_prefix == NULL)	symbol_prefix = "yy";    else    {	++outline;	fprintf(code_file, "#define yyparse %sparse\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yylex %slex\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyerror %serror\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yychar %schar\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyval %sval\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yylval %slval\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yydebug %sdebug\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yynerrs %snerrs\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyerrflag %serrflag\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyss %sss\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyssp %sssp\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyvs %svs\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyvsp %svsp\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yylhs %slhs\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yylen %slen\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yydefred %sdefred\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yydgoto %sdgoto\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yysindex %ssindex\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyrindex %srindex\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yygindex %sgindex\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yytable %stable\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yycheck %scheck\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyname %sname\n", symbol_prefix);	++outline;	fprintf(code_file, "#define yyrule %srule\n", symbol_prefix);    }    ++outline;    fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix);}output_rule_data(){    register int i;    register int j;      fprintf(output_file, "short %slhs[] = {%42d,", symbol_prefix,	    symbol_value[start_symbol]);    j = 10;    for (i = 3; i < nrules; i++)    {	if (j >= 10)	{	    if (!rflag) ++outline;	    putc('\n', output_file);	    j = 1;	}        else	    ++j;        fprintf(output_file, "%5d,", symbol_value[rlhs[i]]);    }    if (!rflag) outline += 2;    fprintf(output_file, "\n};\n");    fprintf(output_file, "short %slen[] = {%42d,", symbol_prefix, 2);    j = 10;    for (i = 3; i < nrules; i++)    {	if (j >= 10)	{	    if (!rflag) ++outline;	    putc('\n', output_file);	    j = 1;	}	else	  j++;        fprintf(output_file, "%5d,", rrhs[i + 1] - rrhs[i] - 1);    }    if (!rflag) outline += 2;    fprintf(output_file, "\n};\n");}output_yydefred(){    register int i, j;    fprintf(output_file, "short %sdefred[] = {%39d,", symbol_prefix,	    (defred[0] ? defred[0] - 2 : 0));    j = 10;    for (i = 1; i < nstates; i++)    {	if (j < 10)	    ++j;	else	{	    if (!rflag) ++outline;	    putc('\n', output_file);	    j = 1;	}	fprintf(output_file, "%5d,", (defred[i] ? defred[i] - 2 : 0));    }    if (!rflag) outline += 2;    fprintf(output_file, "\n};\n");}output_actions(){    nvectors = 2*nstates + nvars;    froms = NEW2(nvectors, short *);    tos = NEW2(nvectors, short *);    tally = NEW2(nvectors, short);    width = NEW2(nvectors, short);    token_actions();    FREE(lookaheads);    FREE(LA);    FREE(LAruleno);    FREE(accessing_symbol);    goto_actions();    FREE(goto_map + ntokens);    FREE(from_state);    FREE(to_state);    sort_actions();    pack_table();    output_base();    output_table();    output_check();}token_actions(){    register int i, j;    register int shiftcount, reducecount;    register int max, min;    register short *actionrow, *r, *s;    register action *p;    actionrow = NEW2(2*ntokens, short);    for (i = 0; i < nstates; ++i)    {	if (parser[i])	{	    for (j = 0; j < 2*ntokens; ++j)	    actionrow[j] = 0;	    shiftcount = 0;	    reducecount = 0;	    for (p = parser[i]; p; p = p->next)	    {		if (p->suppressed == 0)		{		    if (p->action_code == SHIFT)		    {			++shiftcount;			actionrow[p->symbol] = p->number;		    }		    else if (p->action_code == REDUCE && p->number != defred[i])		    {			++reducecount;			actionrow[p->symbol + ntokens] = p->number;		    }		}	    }	    tally[i] = shiftcount;	    tally[nstates+i] = reducecount;	    width[i] = 0;	    width[nstates+i] = 0;	    if (shiftcount > 0)	    {		froms[i] = r = NEW2(shiftcount, short);		tos[i] = s = NEW2(shiftcount, short);		min = MAXSHORT;		max = 0;		for (j = 0; j < ntokens; ++j)		{		    if (actionrow[j])		    {			if (min > symbol_value[j])			    min = symbol_value[j];			if (max < symbol_value[j])			    max = symbol_value[j];			*r++ = symbol_value[j];			*s++ = actionrow[j];		    }		}		width[i] = max - min + 1;	    }	    if (reducecount > 0)	    {		froms[nstates+i] = r = NEW2(reducecount, short);		tos[nstates+i] = s = NEW2(reducecount, short);		min = MAXSHORT;		max = 0;		for (j = 0; j < ntokens; ++j)		{		    if (actionrow[ntokens+j])		    {			if (min > symbol_value[j])			    min = symbol_value[j];			if (max < symbol_value[j])			    max = symbol_value[j];			*r++ = symbol_value[j];			*s++ = actionrow[ntokens+j] - 2;		    }		}		width[nstates+i] = max - min + 1;	    }	}    }    FREE(actionrow);}goto_actions(){    register int i, j, k;    state_count = NEW2(nstates, short);    k = default_goto(start_symbol + 1);    fprintf(output_file, "short %sdgoto[] = {%40d,", symbol_prefix, k);    save_column(start_symbol + 1, k);    j = 10;    for (i = start_symbol + 2; i < nsyms; i++)    {	if (j >= 10)	{	    if (!rflag) ++outline;	    putc('\n', output_file);	    j = 1;	}	else	    ++j;	k = default_goto(i);	fprintf(output_file, "%5d,", k);	save_column(i, k);    }    if (!rflag) outline += 2;    fprintf(output_file, "\n};\n");    FREE(state_count);}intdefault_goto(symbol)int symbol;{    register int i;    register int m;    register int n;    register int default_state;    register int max;    m = goto_map[symbol];    n = goto_map[symbol + 1];    if (m == n) return (0);    for (i = 0; i < nstates; i++)	state_count[i] = 0;    for (i = m; i < n; i++)	state_count[to_state[i]]++;    max = 0;    default_state = 0;    for (i = 0; i < nstates; i++)    {	if (state_count[i] > max)	{	    max = state_count[i];	    default_state = i;	}    }    return (default_state);}save_column(symbol, default_state)int symbol;int default_state;{    register int i;    register int m;    register int n;    register short *sp;    register short *sp1;    register short *sp2;    register int count;    register int symno;    m = goto_map[symbol];    n = goto_map[symbol + 1];    count = 0;    for (i = m; i < n; i++)    {	if (to_state[i] != default_state)	    ++count;    }    if (count == 0) return;    symno = symbol_value[symbol] + 2*nstates;    froms[symno] = sp1 = sp = NEW2(count, short);    tos[symno] = sp2 = NEW2(count, short);    for (i = m; i < n; i++)    {	if (to_state[i] != default_state)	{	    *sp1++ = from_state[i];	    *sp2++ = to_state[i];	}    }    tally[symno] = count;    width[symno] = sp1[-1] - sp[0] + 1;}sort_actions(){  register int i;  register int j;  register int k;  register int t;  register int w;  order = NEW2(nvectors, short);  nentries = 0;  for (i = 0; i < nvectors; i++)    {      if (tally[i] > 0)	{	  t = tally[i];	  w = width[i];	  j = nentries - 1;	  while (j >= 0 && (width[order[j]] < w))	    j--;	  while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))	    j--;	  for (k = nentries - 1; k > j; k--)	    order[k + 1] = order[k];	  order[j + 1] = i;	  nentries++;	}    }}pack_table(){    register int i;    register int place;    register int state;    base = NEW2(nvectors, short);    pos = NEW2(nentries, short);    maxtable = 1000;    table = NEW2(maxtable, short);    check = NEW2(maxtable, short);    lowzero = 0;    high = 0;    for (i = 0; i < maxtable; i++)	check[i] = -1;    for (i = 0; i < nentries; i++)    {	state = matching_vector(i);	if (state < 0)	    place = pack_vector(i);	else	    place = base[state];	pos[i] = place;	base[order[i]] = place;    }    for (i = 0; i < nvectors; i++)    {	if (froms[i])	    FREE(froms[i]);	if (tos[i])	    FREE(tos[i]);    }    FREE(froms);    FREE(tos);    FREE(pos);}/*  The function matching_vector determines if the vector specified by	*//*  the input parameter matches a previously considered	vector.  The	*//*  test at the start of the function checks if the vector represents	*//*  a row of shifts over terminal symbols or a row of reductions, or a	*//*  column of shifts over a nonterminal symbol.  Berkeley Yacc does not	*//*  check if a column of shifts over a nonterminal symbols matches a	*//*  previously considered vector.  Because of the nature of LR parsing	*//*  tables, no two columns can match.  Therefore, the only possible	*//*  match would be between a row and a column.  Such matches are	*//*  unlikely.  Therefore, to save time, no attempt is made to see if a	*//*  column matches a previously considered vector.			*//*									*//*  Matching_vector is poorly designed.  The test could easily be made	*//*  faster.  Also, it depends on the vectors being in a specific	*//*  order.								*/intmatching_vector(vector)int vector;{    register int i;    register int j;    register int k;    register int t;    register int w;    register int match;    register int prev;    i = order[vector];    if (i >= 2*nstates)	return (-1);    t = tally[i];    w = width[i];    for (prev = vector - 1; prev >= 0; prev--)    {	j = order[prev];	if (width[j] != w || tally[j] != t)	    return (-1);	match = 1;	for (k = 0; match && k < t; k++)	{	    if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])		match = 0;	}	if (match)	    return (j);    }    return (-1);}intpack_vector(vector)int vector;{    register int i, j, k, l;    register int t;    register int loc;    register int ok;    register short *from;    register short *to;    int newmax;    i = order[vector];    t = tally[i];    assert(t);    from = froms[i];    to = tos[i];    j = lowzero - from[0];    for (k = 1; k < t; ++k)	if (lowzero - from[k] > j)	    j = lowzero - from[k];    for (;; ++j)    {	if (j == 0)	    continue;	ok = 1;	for (k = 0; ok && k < t; k++)	{	    loc = j + from[k];	    if (loc >= maxtable)	    {		if (loc >= MAXTABLE)		    fatal("maximum table size exceeded");		newmax = maxtable;		do { newmax += 200; } while (newmax <= loc);		table = (short *) REALLOC(table, newmax*sizeof(short));		if (table == 0) no_space();		check = (short *) REALLOC(check, newmax*sizeof(short));		if (check == 0) no_space();		for (l  = maxtable; l < newmax; ++l)		{		    table[l] = 0;		    check[l] = -1;		}		maxtable = newmax;	    }	    if (check[loc] != -1)		ok = 0;	}	for (k = 0; ok && k < vector; k++)	{	    if (pos[k] == j)		ok = 0;	}	if (ok)	{	    for (k = 0; k < t; k++)	    {		loc = j + from[k];		table[loc] = to[k];		check[loc] = from[k];		if (loc > high) high = loc;	    }	    while (check[lowzero] != -1)