src/gram.c

/* Allocate input grammar variables for Bison.

   Copyright (C) 1984, 1986, 1989, 2001, 2002, 2003, 2005, 2006
   2007 Free Software Foundation, Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include <config.h>
#include "system.h"

#include <quotearg.h>

#include "gram.h"
#include "reader.h"
#include "reduce.h"
#include "symtab.h"
#include "print-xml.h"

/* Comments for these variables are in gram.h.  */

item_number *ritem = NULL;
unsigned int nritems = 0;

rule *rules = NULL;
rule_number nrules = 0;

symbol **symbols = NULL;
int nsyms = 0;
int ntokens = 1;
int nvars = 0;

symbol_number *token_translations = NULL;

int max_user_token_number = 256;

/*--------------------------------------------------------------.
| Return true IFF the rule has a `number' smaller than NRULES.  |
`--------------------------------------------------------------*/

bool
rule_useful_p (rule *r)
{
  return r->number < nrules;
}


/*-------------------------------------------------------------.
| Return true IFF the rule has a `number' higher than NRULES.  |
`-------------------------------------------------------------*/

bool
rule_useless_p (rule *r)
{
  return !rule_useful_p (r);
}


/*--------------------------------------------------------------------.
| Return true IFF the rule is not flagged as useful *and* is useful.  |
| In other words, it was discarded because of conflicts.              |
`--------------------------------------------------------------------*/

bool
rule_never_reduced_p (rule *r)
{
  return !r->useful && rule_useful_p (r);
}


/*----------------------------------------------------------------.
| Print this RULE's number and lhs on OUT.  If a PREVIOUS_LHS was |
| already displayed (by a previous call for another rule), avoid  |
| useless repetitions.                                            |
`----------------------------------------------------------------*/

void
rule_lhs_print (rule *r, symbol *previous_lhs, FILE *out)
{
  fprintf (out, "  %3d ", r->number);
  if (previous_lhs != r->lhs)
    {
      fprintf (out, "%s:", r->lhs->tag);
    }
  else
    {
      int n;
      for (n = strlen (previous_lhs->tag); n > 0; --n)
	fputc (' ', out);
      fputc ('|', out);
    }
}

void
rule_lhs_print_xml (rule *r, FILE *out, int level)
{
  xml_printf (out, level, "<lhs>%s</lhs>", r->lhs->tag);
}


/*--------------------------------------.
| Return the number of symbols in RHS.  |
`--------------------------------------*/

int
rule_rhs_length (rule *r)
{
  int res = 0;
  item_number *rhsp;
  for (rhsp = r->rhs; *rhsp >= 0; ++rhsp)
    ++res;
  return res;
}


/*-------------------------------.
| Print this rule's RHS on OUT.  |
`-------------------------------*/

void
rule_rhs_print (rule *r, FILE *out)
{
  if (*r->rhs >= 0)
    {
      item_number *rp;
      for (rp = r->rhs; *rp >= 0; rp++)
	fprintf (out, " %s", symbols[*rp]->tag);
      fputc ('\n', out);
    }
  else
    {
      fprintf (out, " /* %s */\n", _("empty"));
    }
}

static void
rule_rhs_print_xml (rule *r, FILE *out, int level)
{
  if (*r->rhs >= 0)
    {
      item_number *rp;
      xml_puts (out, level, "<rhs>");
      for (rp = r->rhs; *rp >= 0; rp++)
	xml_printf (out, level + 1, "<symbol class=\"%s\">%s</symbol>",
		    symbol_class_get_string (symbols[*rp]),
		    xml_escape (symbols[*rp]->tag));
      xml_puts (out, level, "</rhs>");
    }
  else
    {
      xml_puts (out, level, "<rhs>");
      xml_puts (out, level + 1, "<empty/>");
      xml_puts (out, level, "</rhs>");
    }
}

/*-------------------------.
| Print this rule on OUT.  |
`-------------------------*/

void
rule_print (rule *r, FILE *out)
{
  fprintf (out, "%s:", r->lhs->tag);
  rule_rhs_print (r, out);
}


/*------------------------.
| Dump RITEM for traces.  |
`------------------------*/

void
ritem_print (FILE *out)
{
  unsigned int i;
  fputs ("RITEM\n", out);
  for (i = 0; i < nritems; ++i)
    if (ritem[i] >= 0)
      fprintf (out, "  %s", symbols[ritem[i]]->tag);
    else
      fprintf (out, "  (rule %d)\n", item_number_as_rule_number (ritem[i]));
  fputs ("\n\n", out);
}


/*------------------------------------------.
| Return the size of the longest rule RHS.  |
`------------------------------------------*/

size_t
ritem_longest_rhs (void)
{
  int max = 0;
  rule_number r;

  for (r = 0; r < nrules; ++r)
    {
      int length = rule_rhs_length (&rules[r]);
      if (length > max)
	max = length;
    }

  return max;
}


/*-----------------------------------------------------------------.
| Print the grammar's rules that match FILTER on OUT under TITLE.  |
`-----------------------------------------------------------------*/

void
grammar_rules_partial_print (FILE *out, const char *title,
			     rule_filter filter)
{
  rule_number r;
  bool first = true;
  symbol *previous_lhs = NULL;

  /* rule # : LHS -> RHS */
  for (r = 0; r < nrules + nuseless_productions; r++)
    {
      if (filter && !filter (&rules[r]))
	continue;
      if (first)
	fprintf (out, "%s\n\n", title);
      else if (previous_lhs && previous_lhs != rules[r].lhs)
	fputc ('\n', out);
      first = false;
      rule_lhs_print (&rules[r], previous_lhs, out);
      rule_rhs_print (&rules[r], out);
      previous_lhs = rules[r].lhs;
    }
  if (!first)
    fputs ("\n\n", out);
}


/*----------------------------------------------------------.
| Print the grammar's rules that match FILTER on OUT (XML). |
`-----------------------------------------------------------*/

void
grammar_rules_partial_print_xml (FILE *out, int level, bool rtag,
				 rule_filter filter)
{
  rule_number r;
  bool first = true;

  for (r = 0; r < nrules + nuseless_productions; r++)
    {
      if (filter && !filter (&rules[r]))
	continue;
      if (rtag && first)
	xml_puts (out, level + 1, "<rules>");
      first = false;

      xml_printf (out, level + 2, "<rule number=\"%d\">",
		  rules[r].number);
      rule_lhs_print_xml (&rules[r], out, level + 3);
      rule_rhs_print_xml (&rules[r], out, level + 3);
      xml_puts (out, level + 2, "</rule>");
    }
  if (rtag)
    {
      if (!first)
	xml_puts (out, level + 1, "</rules>");
      else
	xml_puts (out, level + 1, "<rules/>");
    }
}

/*------------------------------------------.
| Print the grammar's useful rules on OUT.  |
`------------------------------------------*/

void
grammar_rules_print (FILE *out)
{
  grammar_rules_partial_print (out, _("Grammar"), rule_useful_p);
}

void
grammar_rules_print_xml (FILE *out, int level)
{
  grammar_rules_partial_print_xml (out, level, true, rule_useful_p);
}


/*-------------------.
| Dump the grammar.  |
`-------------------*/

void
grammar_dump (FILE *out, const char *title)
{
  fprintf (out, "%s\n\n", title);
  fprintf (out,
	   "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nritems = %d\n\n",
	   ntokens, nvars, nsyms, nrules, nritems);


  fprintf (out, "Variables\n---------\n\n");
  {
    symbol_number i;
    fprintf (out, "Value  Sprec  Sassoc  Tag\n");

    for (i = ntokens; i < nsyms; i++)
      fprintf (out, "%5d  %5d   %5d  %s\n",
	       i,
	       symbols[i]->prec, symbols[i]->assoc,
	       symbols[i]->tag);
    fprintf (out, "\n\n");
  }

  fprintf (out, "Rules\n-----\n\n");
  {
    rule_number i;
    fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n");
    for (i = 0; i < nrules + nuseless_productions; i++)
      {
	rule *rule_i = &rules[i];
	item_number *rp = NULL;
	unsigned int rhs_itemno = rule_i->rhs - ritem;
	unsigned int rhs_count = 0;
	/* Find the last RHS index in ritems. */
	for (rp = rule_i->rhs; *rp >= 0; ++rp)
	  ++rhs_count;
	fprintf (out, "%3d (%2d, %2d, %2d, %2u-%2u)   %2d ->",
		 i,
		 rule_i->prec ? rule_i->prec->prec : 0,
		 rule_i->prec ? rule_i->prec->assoc : 0,
		 rule_i->useful,
		 rhs_itemno,
		 rhs_itemno + rhs_count - 1,
		 rule_i->lhs->number);
	/* Dumped the RHS. */
	for (rp = rule_i->rhs; *rp >= 0; rp++)
	  fprintf (out, " %3d", *rp);
	fprintf (out, "  [%d]\n", item_number_as_rule_number (*rp));
      }
  }
  fprintf (out, "\n\n");

  fprintf (out, "Rules interpreted\n-----------------\n\n");
  {
    rule_number r;
    for (r = 0; r < nrules + nuseless_productions; r++)
      {
	fprintf (out, "%-5d  ", r);
	rule_print (&rules[r], out);
      }
  }
  fprintf (out, "\n\n");
}


/*------------------------------------------------------------------.
| Report on STDERR the rules that are not flagged USEFUL, using the |
| MESSAGE (which can be `useless rule' when invoked after grammar   |
| reduction, or `never reduced' after conflicts were taken into     |
| account).                                                         |
`------------------------------------------------------------------*/

void
grammar_rules_never_reduced_report (const char *message)
{
  rule_number r;
  for (r = 0; r < nrules ; ++r)
    if (!rules[r].useful)
      {
	location_print (stderr, rules[r].location);
	fprintf (stderr, ": %s: %s: ", _("warning"), message);
	rule_print (&rules[r], stderr);
      }
}

void
grammar_free (void)
{
  if (ritem)
    free (ritem - 1);
  free (rules);
  free (token_translations);
  /* Free the symbol table data structure.  */
  symbols_free ();
  free_merger_functions ();
}
Commit	Line	Data
	1	/* Allocate input grammar variables for Bison.
	2
	3	Copyright (C) 1984, 1986, 1989, 2001, 2002, 2003, 2005, 2006
	4	2007 Free Software Foundation, Inc.
	5
	6	This file is part of Bison, the GNU Compiler Compiler.
	7
	8	This program is free software: you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
	10	the Free Software Foundation, either version 3 of the License, or
	11	(at your option) any later version.
	12
	13	This program is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with this program. If not, see <http://www.gnu.org/licenses/>. */
	20
	21	#include <config.h>
	22	#include "system.h"
	23
	24	#include <quotearg.h>
	25
	26	#include "gram.h"
	27	#include "reader.h"
	28	#include "reduce.h"
	29	#include "symtab.h"
	30	#include "print-xml.h"
	31
	32	/* Comments for these variables are in gram.h. */
	33
	34	item_number *ritem = NULL;
	35	unsigned int nritems = 0;
	36
	37	rule *rules = NULL;
	38	rule_number nrules = 0;
	39
	40	symbol **symbols = NULL;
	41	int nsyms = 0;
	42	int ntokens = 1;
	43	int nvars = 0;
	44
	45	symbol_number *token_translations = NULL;
	46
	47	int max_user_token_number = 256;
	48
	49	/*--------------------------------------------------------------.
	50	\| Return true IFF the rule has a `number' smaller than NRULES. \|
	51	`--------------------------------------------------------------*/
	52
	53	bool
	54	rule_useful_p (rule *r)
	55	{
	56	return r->number < nrules;
	57	}
	58
	59
	60	/*-------------------------------------------------------------.
	61	\| Return true IFF the rule has a `number' higher than NRULES. \|
	62	`-------------------------------------------------------------*/
	63
	64	bool
	65	rule_useless_p (rule *r)
	66	{
	67	return !rule_useful_p (r);
	68	}
	69
	70
	71	/*--------------------------------------------------------------------.
	72	\| Return true IFF the rule is not flagged as useful and is useful. \|
	73	\| In other words, it was discarded because of conflicts. \|
	74	`--------------------------------------------------------------------*/
	75
	76	bool
	77	rule_never_reduced_p (rule *r)
	78	{
	79	return !r->useful && rule_useful_p (r);
	80	}
	81
	82
	83	/*----------------------------------------------------------------.
	84	\| Print this RULE's number and lhs on OUT. If a PREVIOUS_LHS was \|
	85	\| already displayed (by a previous call for another rule), avoid \|
	86	\| useless repetitions. \|
	87	`----------------------------------------------------------------*/
	88
	89	void
	90	rule_lhs_print (rule r, symbol previous_lhs, FILE *out)
	91	{
	92	fprintf (out, " %3d ", r->number);
	93	if (previous_lhs != r->lhs)
	94	{
	95	fprintf (out, "%s:", r->lhs->tag);
	96	}
	97	else
	98	{
	99	int n;
	100	for (n = strlen (previous_lhs->tag); n > 0; --n)
	101	fputc (' ', out);
	102	fputc ('\|', out);
	103	}
	104	}
	105
	106	void
	107	rule_lhs_print_xml (rule r, FILE out, int level)
	108	{
	109	xml_printf (out, level, "<lhs>%s</lhs>", r->lhs->tag);
	110	}
	111
	112
	113	/*--------------------------------------.
	114	\| Return the number of symbols in RHS. \|
	115	`--------------------------------------*/
	116
	117	int
	118	rule_rhs_length (rule *r)
	119	{
	120	int res = 0;
	121	item_number *rhsp;
	122	for (rhsp = r->rhs; *rhsp >= 0; ++rhsp)
	123	++res;
	124	return res;
	125	}
	126
	127
	128	/*-------------------------------.
	129	\| Print this rule's RHS on OUT. \|
	130	`-------------------------------*/
	131
	132	void
	133	rule_rhs_print (rule r, FILE out)
	134	{
	135	if (*r->rhs >= 0)
	136	{
	137	item_number *rp;
	138	for (rp = r->rhs; *rp >= 0; rp++)
	139	fprintf (out, " %s", symbols[*rp]->tag);
	140	fputc ('\n', out);
	141	}
	142	else
	143	{
	144	fprintf (out, " /* %s */\n", _("empty"));
	145	}
	146	}
	147
	148	static void
	149	rule_rhs_print_xml (rule r, FILE out, int level)
	150	{
	151	if (*r->rhs >= 0)
	152	{
	153	item_number *rp;
	154	xml_puts (out, level, "<rhs>");
	155	for (rp = r->rhs; *rp >= 0; rp++)
	156	xml_printf (out, level + 1, "<symbol class=\"%s\">%s</symbol>",
	157	symbol_class_get_string (symbols[*rp]),
	158	xml_escape (symbols[*rp]->tag));
	159	xml_puts (out, level, "</rhs>");
	160	}
	161	else
	162	{
	163	xml_puts (out, level, "<rhs>");
	164	xml_puts (out, level + 1, "<empty/>");
	165	xml_puts (out, level, "</rhs>");
	166	}
	167	}
	168
	169	/*-------------------------.
	170	\| Print this rule on OUT. \|
	171	`-------------------------*/
	172
	173	void
	174	rule_print (rule r, FILE out)
	175	{
	176	fprintf (out, "%s:", r->lhs->tag);
	177	rule_rhs_print (r, out);
	178	}
	179
	180
	181	/*------------------------.
	182	\| Dump RITEM for traces. \|
	183	`------------------------*/
	184
	185	void
	186	ritem_print (FILE *out)
	187	{
	188	unsigned int i;
	189	fputs ("RITEM\n", out);
	190	for (i = 0; i < nritems; ++i)
	191	if (ritem[i] >= 0)
	192	fprintf (out, " %s", symbols[ritem[i]]->tag);
	193	else
	194	fprintf (out, " (rule %d)\n", item_number_as_rule_number (ritem[i]));
	195	fputs ("\n\n", out);
	196	}
	197
	198
	199	/*------------------------------------------.
	200	\| Return the size of the longest rule RHS. \|
	201	`------------------------------------------*/
	202
	203	size_t
	204	ritem_longest_rhs (void)
	205	{
	206	int max = 0;
	207	rule_number r;
	208
	209	for (r = 0; r < nrules; ++r)
	210	{
	211	int length = rule_rhs_length (&rules[r]);
	212	if (length > max)
	213	max = length;
	214	}
	215
	216	return max;
	217	}
	218
	219
	220	/*-----------------------------------------------------------------.
	221	\| Print the grammar's rules that match FILTER on OUT under TITLE. \|
	222	`-----------------------------------------------------------------*/
	223
	224	void
	225	grammar_rules_partial_print (FILE out, const char title,
	226	rule_filter filter)
	227	{
	228	rule_number r;
	229	bool first = true;
	230	symbol *previous_lhs = NULL;
	231
	232	/* rule # : LHS -> RHS */
	233	for (r = 0; r < nrules + nuseless_productions; r++)
	234	{
	235	if (filter && !filter (&rules[r]))
	236	continue;
	237	if (first)
	238	fprintf (out, "%s\n\n", title);
	239	else if (previous_lhs && previous_lhs != rules[r].lhs)
	240	fputc ('\n', out);
	241	first = false;
	242	rule_lhs_print (&rules[r], previous_lhs, out);
	243	rule_rhs_print (&rules[r], out);
	244	previous_lhs = rules[r].lhs;
	245	}
	246	if (!first)
	247	fputs ("\n\n", out);
	248	}
	249
	250
	251	/*----------------------------------------------------------.
	252	\| Print the grammar's rules that match FILTER on OUT (XML). \|
	253	`-----------------------------------------------------------*/
	254
	255	void
	256	grammar_rules_partial_print_xml (FILE *out, int level, bool rtag,
	257	rule_filter filter)
	258	{
	259	rule_number r;
	260	bool first = true;
	261
	262	for (r = 0; r < nrules + nuseless_productions; r++)
	263	{
	264	if (filter && !filter (&rules[r]))
	265	continue;
	266	if (rtag && first)
	267	xml_puts (out, level + 1, "<rules>");
	268	first = false;
	269
	270	xml_printf (out, level + 2, "<rule number=\"%d\">",
	271	rules[r].number);
	272	rule_lhs_print_xml (&rules[r], out, level + 3);
	273	rule_rhs_print_xml (&rules[r], out, level + 3);
	274	xml_puts (out, level + 2, "</rule>");
	275	}
	276	if (rtag)
	277	{
	278	if (!first)
	279	xml_puts (out, level + 1, "</rules>");
	280	else
	281	xml_puts (out, level + 1, "<rules/>");
	282	}
	283	}
	284
	285	/*------------------------------------------.
	286	\| Print the grammar's useful rules on OUT. \|
	287	`------------------------------------------*/
	288
	289	void
	290	grammar_rules_print (FILE *out)
	291	{
	292	grammar_rules_partial_print (out, _("Grammar"), rule_useful_p);
	293	}
	294
	295	void
	296	grammar_rules_print_xml (FILE *out, int level)
	297	{
	298	grammar_rules_partial_print_xml (out, level, true, rule_useful_p);
	299	}
	300
	301
	302	/*-------------------.
	303	\| Dump the grammar. \|
	304	`-------------------*/
	305
	306	void
	307	grammar_dump (FILE out, const char title)
	308	{
	309	fprintf (out, "%s\n\n", title);
	310	fprintf (out,
	311	"ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nritems = %d\n\n",
	312	ntokens, nvars, nsyms, nrules, nritems);
	313
	314
	315	fprintf (out, "Variables\n---------\n\n");
	316	{
	317	symbol_number i;
	318	fprintf (out, "Value Sprec Sassoc Tag\n");
	319
	320	for (i = ntokens; i < nsyms; i++)
	321	fprintf (out, "%5d %5d %5d %s\n",
	322	i,
	323	symbols[i]->prec, symbols[i]->assoc,
	324	symbols[i]->tag);
	325	fprintf (out, "\n\n");
	326	}
	327
	328	fprintf (out, "Rules\n-----\n\n");
	329	{
	330	rule_number i;
	331	fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n");
	332	for (i = 0; i < nrules + nuseless_productions; i++)
	333	{
	334	rule *rule_i = &rules[i];
	335	item_number *rp = NULL;
	336	unsigned int rhs_itemno = rule_i->rhs - ritem;
	337	unsigned int rhs_count = 0;
	338	/* Find the last RHS index in ritems. */
	339	for (rp = rule_i->rhs; *rp >= 0; ++rp)
	340	++rhs_count;
	341	fprintf (out, "%3d (%2d, %2d, %2d, %2u-%2u) %2d ->",
	342	i,
	343	rule_i->prec ? rule_i->prec->prec : 0,
	344	rule_i->prec ? rule_i->prec->assoc : 0,
	345	rule_i->useful,
	346	rhs_itemno,
	347	rhs_itemno + rhs_count - 1,
	348	rule_i->lhs->number);
	349	/* Dumped the RHS. */
	350	for (rp = rule_i->rhs; *rp >= 0; rp++)
	351	fprintf (out, " %3d", *rp);
	352	fprintf (out, " [%d]\n", item_number_as_rule_number (*rp));
	353	}
	354	}
	355	fprintf (out, "\n\n");
	356
	357	fprintf (out, "Rules interpreted\n-----------------\n\n");
	358	{
	359	rule_number r;
	360	for (r = 0; r < nrules + nuseless_productions; r++)
	361	{
	362	fprintf (out, "%-5d ", r);
	363	rule_print (&rules[r], out);
	364	}
	365	}
	366	fprintf (out, "\n\n");
	367	}
	368
	369
	370	/*------------------------------------------------------------------.
	371	\| Report on STDERR the rules that are not flagged USEFUL, using the \|
	372	\| MESSAGE (which can be `useless rule' when invoked after grammar \|
	373	\| reduction, or `never reduced' after conflicts were taken into \|
	374	\| account). \|
	375	`------------------------------------------------------------------*/
	376
	377	void
	378	grammar_rules_never_reduced_report (const char *message)
	379	{
	380	rule_number r;
	381	for (r = 0; r < nrules ; ++r)
	382	if (!rules[r].useful)
	383	{
	384	location_print (stderr, rules[r].location);
	385	fprintf (stderr, ": %s: %s: ", _("warning"), message);
	386	rule_print (&rules[r], stderr);
	387	}
	388	}
	389
	390	void
	391	grammar_free (void)
	392	{
	393	if (ritem)
	394	free (ritem - 1);
	395	free (rules);
	396	free (token_translations);
	397	/* Free the symbol table data structure. */
	398	symbols_free ();
	399	free_merger_functions ();
	400	}