src/gram.c

   1 /* Allocate input grammar variables for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 2001-2003, 2005-2015, 2018-2020 Free
   4    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 "complain.h"
  25 #include "getargs.h"
  26 #include "glyphs.h"
  27 #include "gram.h"
  28 #include "print-xml.h"
  29 #include "reader.h"
  30 #include "reduce.h"
  31 #include "symtab.h"
  32
  33 /* Comments for these variables are in gram.h.  */
  34
  35 item_number *ritem = NULL;
  36 int nritems = 0;
  37
  38 rule *rules = NULL;
  39 rule_number nrules = 0;
  40
  41 symbol **symbols = NULL;
  42 int nsyms = 0;
  43 int ntokens = 1;
  44 int nnterms = 0;
  45
  46 symbol_number *token_translations = NULL;
  47
  48 int max_code = 256;
  49
  50 int required_version = 0;
  51
  52 void
  53 item_print (item_number *item, rule const *previous_rule, FILE *out)
  54 {
  55   rule const *r = item_rule (item);
  56   rule_lhs_print (r, previous_rule ? previous_rule->lhs : NULL, out);
  57
  58   for (item_number *sp = r->rhs; sp < item; sp++)
  59     fprintf (out, " %s", symbols[*sp]->tag);
  60   fprintf (out, " %s", dot);
  61   if (0 <= *r->rhs)
  62     for (item_number *sp = item; 0 <= *sp; ++sp)
  63       fprintf (out, " %s", symbols[*sp]->tag);
  64   else
  65     fprintf (out, " %%empty");
  66 }
  67
  68
  69 bool
  70 rule_useful_in_grammar_p (rule const *r)
  71 {
  72   return r->number < nrules;
  73 }
  74
  75 bool
  76 rule_useless_in_grammar_p (rule const *r)
  77 {
  78   return !rule_useful_in_grammar_p (r);
  79 }
  80
  81 bool
  82 rule_useless_in_parser_p (rule const *r)
  83 {
  84   return !r->useful && rule_useful_in_grammar_p (r);
  85 }
  86
  87 bool
  88 rule_useless_chain_p (rule const *r)
  89 {
  90   return rule_rhs_length (r) == 1 && !r->action;
  91 }
  92
  93 void
  94 rule_lhs_print (rule const *r, sym_content const *previous_lhs, FILE *out)
  95 {
  96   fprintf (out, "  %3d ", r->number);
  97   if (previous_lhs != r->lhs)
  98     fprintf (out, "%s:", r->lhs->symbol->tag);
  99   else
 100     fprintf (out, "%*s|", (int) strlen (previous_lhs->symbol->tag), "");
 101 }
 102
 103 void
 104 rule_lhs_print_xml (rule const *r, FILE *out, int level)
 105 {
 106   xml_printf (out, level, "<lhs>%s</lhs>", r->lhs->symbol->tag);
 107 }
 108
 109 size_t
 110 rule_rhs_length (rule const *r)
 111 {
 112   size_t res = 0;
 113   for (item_number *rhsp = r->rhs; 0 <= *rhsp; ++rhsp)
 114     ++res;
 115   return res;
 116 }
 117
 118 void
 119 rule_rhs_print (rule const *r, FILE *out)
 120 {
 121   if (0 <= *r->rhs)
 122     for (item_number *rhsp = r->rhs; 0 <= *rhsp; ++rhsp)
 123       fprintf (out, " %s", symbols[*rhsp]->tag);
 124   else
 125     fputs (" %empty", out);
 126 }
 127
 128 static void
 129 rule_rhs_print_xml (rule const *r, FILE *out, int level)
 130 {
 131   if (*r->rhs >= 0)
 132     {
 133       xml_puts (out, level, "<rhs>");
 134       for (item_number *rhsp = r->rhs; 0 <= *rhsp; ++rhsp)
 135         xml_printf (out, level + 1, "<symbol>%s</symbol>",
 136                     xml_escape (symbols[*rhsp]->tag));
 137       xml_puts (out, level, "</rhs>");
 138     }
 139   else
 140     {
 141       xml_puts (out, level, "<rhs>");
 142       xml_puts (out, level + 1, "<empty/>");
 143       xml_puts (out, level, "</rhs>");
 144     }
 145 }
 146
 147 void
 148 rule_print (rule const *r, rule const *prev_rule, FILE *out)
 149 {
 150   rule_lhs_print (r, prev_rule ? prev_rule->lhs : NULL, out);
 151   rule_rhs_print (r, out);
 152 }
 153
 154 void
 155 ritem_print (FILE *out)
 156 {
 157   fputs ("RITEM\n", out);
 158   for (int i = 0; i < nritems; ++i)
 159     if (ritem[i] >= 0)
 160       fprintf (out, "  %s", symbols[ritem[i]]->tag);
 161     else
 162       fprintf (out, "  (rule %d)\n", item_number_as_rule_number (ritem[i]));
 163   fputs ("\n\n", out);
 164 }
 165
 166 size_t
 167 ritem_longest_rhs (void)
 168 {
 169   int max = 0;
 170   for (rule_number r = 0; r < nrules; ++r)
 171     {
 172       size_t length = rule_rhs_length (&rules[r]);
 173       if (length > max)
 174         max = length;
 175     }
 176
 177   return max;
 178 }
 179
 180 void
 181 grammar_rules_partial_print (FILE *out, const char *title,
 182                              rule_filter filter)
 183 {
 184   bool first = true;
 185   rule *previous_rule = NULL;
 186
 187   /* rule # : LHS -> RHS */
 188   for (rule_number r = 0; r < nrules + nuseless_productions; r++)
 189     {
 190       if (filter && !filter (&rules[r]))
 191         continue;
 192       if (first)
 193         fprintf (out, "%s\n\n", title);
 194       else if (previous_rule && previous_rule->lhs != rules[r].lhs)
 195         putc ('\n', out);
 196       first = false;
 197       rule_print (&rules[r], previous_rule, out);
 198       putc ('\n', out);
 199       previous_rule = &rules[r];
 200     }
 201   if (!first)
 202     fputs ("\n\n", out);
 203 }
 204
 205 void
 206 grammar_rules_print (FILE *out)
 207 {
 208   grammar_rules_partial_print (out, _("Grammar"), rule_useful_in_grammar_p);
 209 }
 210
 211 void
 212 grammar_rules_print_xml (FILE *out, int level)
 213 {
 214   bool first = true;
 215
 216   for (rule_number r = 0; r < nrules + nuseless_productions; r++)
 217     {
 218       if (first)
 219         xml_puts (out, level + 1, "<rules>");
 220       first = false;
 221       {
 222         char const *usefulness
 223           = rule_useless_in_grammar_p (&rules[r]) ? "useless-in-grammar"
 224           : rule_useless_in_parser_p (&rules[r])  ? "useless-in-parser"
 225           :                                         "useful";
 226         xml_indent (out, level + 2);
 227         fprintf (out, "<rule number=\"%d\" usefulness=\"%s\"",
 228                  rules[r].number, usefulness);
 229         if (rules[r].precsym)
 230           fprintf (out, " percent_prec=\"%s\"",
 231                    xml_escape (rules[r].precsym->symbol->tag));
 232         fputs (">\n", out);
 233       }
 234       rule_lhs_print_xml (&rules[r], out, level + 3);
 235       rule_rhs_print_xml (&rules[r], out, level + 3);
 236       xml_puts (out, level + 2, "</rule>");
 237     }
 238   if (!first)
 239     xml_puts (out, level + 1, "</rules>");
 240   else
 241    xml_puts (out, level + 1, "<rules/>");
 242 }
 243
 244 static void
 245 section (FILE *out, const char *s)
 246 {
 247   fprintf (out, "%s\n", s);
 248   for (int i = strlen (s); 0 < i; --i)
 249     putc ('-', out);
 250   putc ('\n', out);
 251   putc ('\n', out);
 252 }
 253
 254 void
 255 grammar_dump (FILE *out, const char *title)
 256 {
 257   fprintf (out, "%s\n\n", title);
 258   fprintf (out,
 259            "ntokens = %d, nnterms = %d, nsyms = %d, nrules = %d, nritems = %d\n\n",
 260            ntokens, nnterms, nsyms, nrules, nritems);
 261
 262   section (out, "Tokens");
 263   {
 264     fprintf (out, "Value  Sprec  Sassoc  Tag\n");
 265
 266     for (symbol_number i = 0; i < ntokens; i++)
 267       fprintf (out, "%5d  %5d   %5d  %s\n",
 268                i,
 269                symbols[i]->content->prec, symbols[i]->content->assoc,
 270                symbols[i]->tag);
 271     fprintf (out, "\n\n");
 272   }
 273
 274   section (out, "Nonterminals");
 275   {
 276     fprintf (out, "Value  Tag\n");
 277
 278     for (symbol_number i = ntokens; i < nsyms; i++)
 279       fprintf (out, "%5d  %s\n",
 280                i, symbols[i]->tag);
 281     fprintf (out, "\n\n");
 282   }
 283
 284   section (out, "Rules");
 285   {
 286     fprintf (out,
 287              "Num (Prec, Assoc, Useful, UselessChain) Lhs"
 288              " -> (Ritem Range) Rhs\n");
 289     for (rule_number i = 0; i < nrules + nuseless_productions; ++i)
 290       {
 291         rule const *rule_i = &rules[i];
 292         int const rhs_itemno = rule_i->rhs - ritem;
 293         int length = rule_rhs_length (rule_i);
 294         aver (item_number_as_rule_number (rule_i->rhs[length]) == i);
 295         fprintf (out, "%3d (%2d, %2d, %2s, %2s)   %2d -> (%2u-%2u)",
 296                  i,
 297                  rule_i->prec ? rule_i->prec->prec : 0,
 298                  rule_i->prec ? rule_i->prec->assoc : 0,
 299                  rule_i->useful ? "t" : "f",
 300                  rule_useless_chain_p (rule_i) ? "t" : "f",
 301                  rule_i->lhs->number,
 302                  rhs_itemno, rhs_itemno + length - 1);
 303         /* Dumped the RHS. */
 304         for (item_number *rhsp = rule_i->rhs; 0 <= *rhsp; ++rhsp)
 305           fprintf (out, " %3d", *rhsp);
 306         putc ('\n', out);
 307       }
 308   }
 309   fprintf (out, "\n\n");
 310
 311   section (out, "Rules interpreted");
 312   for (rule_number r = 0; r < nrules + nuseless_productions; ++r)
 313     {
 314       fprintf (out, "%-5d  %s:", r, rules[r].lhs->symbol->tag);
 315       rule_rhs_print (&rules[r], out);
 316       putc ('\n', out);
 317     }
 318   fprintf (out, "\n\n");
 319 }
 320
 321 void
 322 grammar_rules_useless_report (const char *message)
 323 {
 324   for (rule_number r = 0; r < nrules; ++r)
 325     /* Don't complain about rules whose LHS is useless, we already
 326        complained about it.  */
 327     if (!reduce_nonterminal_useless_in_grammar (rules[r].lhs)
 328         && !rules[r].useful)
 329       complain (&rules[r].location, Wother, "%s", message);
 330 }
 331
 332 void
 333 grammar_free (void)
 334 {
 335   if (ritem)
 336     free (ritem - 1);
 337   free (rules);
 338   free (token_translations);
 339   /* Free the symbol table data structure.  */
 340   symbols_free ();
 341   free_merger_functions ();
 342 }