"Fossies" - the Fresh Open Source Software Archive

Member "bison-3.4.1/src/state.c" (11 May 2019, 11547 Bytes) of package /linux/misc/bison-3.4.1.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "state.c" see the Fossies "Dox" file reference documentation.

    1 /* Type definitions for the finite state machine for Bison.
    2 
    3    Copyright (C) 2001-2007, 2009-2015, 2018-2019 Free Software
    4    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 "state.h"
   23 
   24 #include "system.h"
   25 
   26 #include <hash.h>
   27 
   28 #include "closure.h"
   29 #include "complain.h"
   30 #include "getargs.h"
   31 #include "gram.h"
   32 #include "print-xml.h"
   33 
   34 
   35                         /*-------------------.
   36                         | Shifts and Gotos.  |
   37                         `-------------------*/
   38 
   39 
   40 /*-----------------------------------------.
   41 | Create a new array of NUM shifts/gotos.  |
   42 `-----------------------------------------*/
   43 
   44 static transitions *
   45 transitions_new (int num, state **dst)
   46 {
   47   size_t states_size = num * sizeof *dst;
   48   transitions *res = xmalloc (offsetof (transitions, states) + states_size);
   49   res->num = num;
   50   memcpy (res->states, dst, states_size);
   51   return res;
   52 }
   53 
   54 
   55 state *
   56 transitions_to (state *s, symbol_number sym)
   57 {
   58   transitions *trans = s->transitions;
   59   for (int i = 0; i < trans->num; ++i)
   60     if (TRANSITION_SYMBOL (trans, i) == sym)
   61       return trans->states[i];
   62   abort ();
   63 }
   64 
   65 
   66                         /*--------------------.
   67                         | Error transitions.  |
   68                         `--------------------*/
   69 
   70 
   71 /*---------------------------------.
   72 | Create a new array of NUM errs.  |
   73 `---------------------------------*/
   74 
   75 errs *
   76 errs_new (int num, symbol **tokens)
   77 {
   78   size_t symbols_size = num * sizeof *tokens;
   79   errs *res = xmalloc (offsetof (errs, symbols) + symbols_size);
   80   res->num = num;
   81   if (tokens)
   82     memcpy (res->symbols, tokens, symbols_size);
   83   return res;
   84 }
   85 
   86 
   87 
   88 
   89                         /*-------------.
   90                         | Reductions.  |
   91                         `-------------*/
   92 
   93 
   94 /*---------------------------------------.
   95 | Create a new array of NUM reductions.  |
   96 `---------------------------------------*/
   97 
   98 static reductions *
   99 reductions_new (int num, rule **reds)
  100 {
  101   size_t rules_size = num * sizeof *reds;
  102   reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);
  103   res->num = num;
  104   res->lookahead_tokens = NULL;
  105   memcpy (res->rules, reds, rules_size);
  106   return res;
  107 }
  108 
  109 
  110 
  111                         /*---------.
  112                         | States.  |
  113                         `---------*/
  114 
  115 
  116 state_number nstates = 0;
  117 /* FINAL_STATE is properly set by new_state when it recognizes its
  118    accessing symbol: $end.  */
  119 state *final_state = NULL;
  120 
  121 
  122 /*------------------------------------------------------------------.
  123 | Create a new state with ACCESSING_SYMBOL, for those items.  Store |
  124 | it in the state hash table.                                       |
  125 `------------------------------------------------------------------*/
  126 
  127 state *
  128 state_new (symbol_number accessing_symbol,
  129            size_t nitems, item_number *core)
  130 {
  131   aver (nstates < STATE_NUMBER_MAXIMUM);
  132 
  133   size_t items_size = nitems * sizeof *core;
  134   state *res = xmalloc (offsetof (state, items) + items_size);
  135   res->number = nstates++;
  136   res->accessing_symbol = accessing_symbol;
  137   res->transitions = NULL;
  138   res->reductions = NULL;
  139   res->errs = NULL;
  140   res->state_list = NULL;
  141   res->consistent = false;
  142   res->solved_conflicts = NULL;
  143   res->solved_conflicts_xml = NULL;
  144 
  145   res->nitems = nitems;
  146   memcpy (res->items, core, items_size);
  147 
  148   state_hash_insert (res);
  149 
  150   return res;
  151 }
  152 
  153 state *
  154 state_new_isocore (state const *s)
  155 {
  156   aver (nstates < STATE_NUMBER_MAXIMUM);
  157 
  158   size_t items_size = s->nitems * sizeof *s->items;
  159   state *res = xmalloc (offsetof (state, items) + items_size);
  160   res->number = nstates++;
  161   res->accessing_symbol = s->accessing_symbol;
  162   res->transitions =
  163     transitions_new (s->transitions->num, s->transitions->states);
  164   res->reductions = reductions_new (s->reductions->num, s->reductions->rules);
  165   res->errs = NULL;
  166   res->state_list = NULL;
  167   res->consistent = s->consistent;
  168   res->solved_conflicts = NULL;
  169   res->solved_conflicts_xml = NULL;
  170 
  171   res->nitems = s->nitems;
  172   memcpy (res->items, s->items, items_size);
  173 
  174   return res;
  175 }
  176 
  177 
  178 /*---------.
  179 | Free S.  |
  180 `---------*/
  181 
  182 static void
  183 state_free (state *s)
  184 {
  185   free (s->transitions);
  186   free (s->reductions);
  187   free (s->errs);
  188   free (s);
  189 }
  190 
  191 
  192 void
  193 state_transitions_print (const state *s, FILE *out)
  194 {
  195   const transitions *trans = s->transitions;
  196   fprintf (out, "transitions of %d (%d):\n",
  197            s->number, trans->num);
  198   for (int i = 0; i < trans->num; ++i)
  199     fprintf (out, "  %d: (%d, %s, %d)\n",
  200              i,
  201              s->number,
  202              symbols[s->transitions->states[i]->accessing_symbol]->tag,
  203              s->transitions->states[i]->number);
  204 }
  205 
  206 
  207 /*---------------------------.
  208 | Set the transitions of S.  |
  209 `---------------------------*/
  210 
  211 void
  212 state_transitions_set (state *s, int num, state **dst)
  213 {
  214   aver (!s->transitions);
  215   s->transitions = transitions_new (num, dst);
  216   if (trace_flag & trace_automaton)
  217     state_transitions_print (s, stderr);
  218 }
  219 
  220 
  221 /*--------------------------.
  222 | Set the reductions of S.  |
  223 `--------------------------*/
  224 
  225 void
  226 state_reductions_set (state *s, int num, rule **reds)
  227 {
  228   aver (!s->reductions);
  229   s->reductions = reductions_new (num, reds);
  230 }
  231 
  232 
  233 int
  234 state_reduction_find (state *s, rule const *r)
  235 {
  236   reductions *reds = s->reductions;
  237   for (int i = 0; i < reds->num; ++i)
  238     if (reds->rules[i] == r)
  239       return i;
  240   abort ();
  241 }
  242 
  243 
  244 /*--------------------.
  245 | Set the errs of S.  |
  246 `--------------------*/
  247 
  248 void
  249 state_errs_set (state *s, int num, symbol **tokens)
  250 {
  251   aver (!s->errs);
  252   s->errs = errs_new (num, tokens);
  253 }
  254 
  255 
  256 
  257 /*--------------------------------------------------.
  258 | Print on OUT all the lookahead tokens such that S |
  259 | wants to reduce R.                                |
  260 `--------------------------------------------------*/
  261 
  262 void
  263 state_rule_lookahead_tokens_print (state *s, rule const *r, FILE *out)
  264 {
  265   /* Find the reduction we are handling.  */
  266   reductions *reds = s->reductions;
  267   int red = state_reduction_find (s, r);
  268 
  269   /* Print them if there are.  */
  270   if (reds->lookahead_tokens && red != -1)
  271     {
  272       bitset_iterator biter;
  273       int k;
  274       char const *sep = "";
  275       fprintf (out, "  [");
  276       BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
  277         {
  278           fprintf (out, "%s%s", sep, symbols[k]->tag);
  279           sep = ", ";
  280         }
  281       fprintf (out, "]");
  282     }
  283 }
  284 
  285 void
  286 state_rule_lookahead_tokens_print_xml (state *s, rule const *r,
  287                                        FILE *out, int level)
  288 {
  289   /* Find the reduction we are handling.  */
  290   reductions *reds = s->reductions;
  291   int red = state_reduction_find (s, r);
  292 
  293   /* Print them if there are.  */
  294   if (reds->lookahead_tokens && red != -1)
  295     {
  296       bitset_iterator biter;
  297       int k;
  298       xml_puts (out, level, "<lookaheads>");
  299       BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
  300         {
  301           xml_printf (out, level + 1, "<symbol>%s</symbol>",
  302                       xml_escape (symbols[k]->tag));
  303         }
  304       xml_puts (out, level, "</lookaheads>");
  305     }
  306 }
  307 
  308 
  309 /*---------------------.
  310 | A state hash table.  |
  311 `---------------------*/
  312 
  313 /* Initial capacity of states hash table.  */
  314 #define HT_INITIAL_CAPACITY 257
  315 
  316 static struct hash_table *state_table = NULL;
  317 
  318 /* Two states are equal if they have the same core items.  */
  319 static inline bool
  320 state_compare (state const *s1, state const *s2)
  321 {
  322   if (s1->nitems != s2->nitems)
  323     return false;
  324 
  325   for (size_t i = 0; i < s1->nitems; ++i)
  326     if (s1->items[i] != s2->items[i])
  327       return false;
  328 
  329   return true;
  330 }
  331 
  332 static bool
  333 state_comparator (void const *s1, void const *s2)
  334 {
  335   return state_compare (s1, s2);
  336 }
  337 
  338 static inline size_t
  339 state_hash (state const *s, size_t tablesize)
  340 {
  341   /* Add up the state's item numbers to get a hash key.  */
  342   size_t key = 0;
  343   for (size_t i = 0; i < s->nitems; ++i)
  344     key += s->items[i];
  345   return key % tablesize;
  346 }
  347 
  348 static size_t
  349 state_hasher (void const *s, size_t tablesize)
  350 {
  351   return state_hash (s, tablesize);
  352 }
  353 
  354 
  355 /*-------------------------------.
  356 | Create the states hash table.  |
  357 `-------------------------------*/
  358 
  359 void
  360 state_hash_new (void)
  361 {
  362   state_table = hash_initialize (HT_INITIAL_CAPACITY,
  363                                  NULL,
  364                                  state_hasher,
  365                                  state_comparator,
  366                                  NULL);
  367 }
  368 
  369 
  370 /*---------------------------------------------.
  371 | Free the states hash table, not the states.  |
  372 `---------------------------------------------*/
  373 
  374 void
  375 state_hash_free (void)
  376 {
  377   hash_free (state_table);
  378 }
  379 
  380 
  381 /*-----------------------------------.
  382 | Insert S in the state hash table.  |
  383 `-----------------------------------*/
  384 
  385 void
  386 state_hash_insert (state *s)
  387 {
  388   if (!hash_insert (state_table, s))
  389     xalloc_die ();
  390 }
  391 
  392 
  393 /*------------------------------------------------------------------.
  394 | Find the state associated to the CORE, and return it.  If it does |
  395 | not exist yet, return NULL.                                       |
  396 `------------------------------------------------------------------*/
  397 
  398 state *
  399 state_hash_lookup (size_t nitems, item_number *core)
  400 {
  401   size_t items_size = nitems * sizeof *core;
  402   state *probe = xmalloc (offsetof (state, items) + items_size);
  403   probe->nitems = nitems;
  404   memcpy (probe->items, core, items_size);
  405   state *entry = hash_lookup (state_table, probe);
  406   free (probe);
  407   return entry;
  408 }
  409 
  410 
  411 /*--------------------------------------------------------.
  412 | Record S and all states reachable from S in REACHABLE.  |
  413 `--------------------------------------------------------*/
  414 
  415 static void
  416 state_record_reachable_states (state *s, bitset reachable)
  417 {
  418   if (bitset_test (reachable, s->number))
  419     return;
  420   bitset_set (reachable, s->number);
  421   for (int i = 0; i < s->transitions->num; ++i)
  422     if (!TRANSITION_IS_DISABLED (s->transitions, i))
  423       state_record_reachable_states (s->transitions->states[i], reachable);
  424 }
  425 
  426 void
  427 state_remove_unreachable_states (state_number old_to_new[])
  428 {
  429   state_number nstates_reachable = 0;
  430   bitset reachable = bitset_create (nstates, BITSET_FIXED);
  431   state_record_reachable_states (states[0], reachable);
  432   for (state_number i = 0; i < nstates; ++i)
  433     {
  434       if (bitset_test (reachable, states[i]->number))
  435         {
  436           states[nstates_reachable] = states[i];
  437           states[nstates_reachable]->number = nstates_reachable;
  438           old_to_new[i] = nstates_reachable++;
  439         }
  440       else
  441         {
  442           state_free (states[i]);
  443           old_to_new[i] = nstates;
  444         }
  445     }
  446   nstates = nstates_reachable;
  447   bitset_free (reachable);
  448 }
  449 
  450 /* All the decorated states, indexed by the state number.  */
  451 state **states = NULL;
  452 
  453 
  454 /*----------------------.
  455 | Free all the states.  |
  456 `----------------------*/
  457 
  458 void
  459 states_free (void)
  460 {
  461   closure_free ();
  462   for (state_number i = 0; i < nstates; ++i)
  463     state_free (states[i]);
  464   free (states);
  465 }