src/state.c

   1 /* Type definitions for nondeterministic finite state machine for bison,
   2    Copyright (C) 2001, 2002  Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23 #include "complain.h"
  24 #include "gram.h"
  25 #include "state.h"
  26
  27
  28                         /*-------------------.
  29                         | Shifts and Gotos.  |
  30                         `-------------------*/
  31
  32
  33 /*---------------------------------.
  34 | Create a new array of N shitfs.  |
  35 `---------------------------------*/
  36
  37 #define SHIFTS_ALLOC(Nshifts)                                           \
  38   (shifts *) xcalloc ((unsigned) (sizeof (shifts)                       \
  39                                   + (Nshifts - 1) * sizeof (short)), 1)
  40
  41 shifts *
  42 shifts_new (int n)
  43 {
  44   shifts *res = SHIFTS_ALLOC (n);
  45   res->nshifts = n;
  46   return res;
  47 }
  48
  49
  50
  51
  52                         /*--------------------.
  53                         | Error transitions.  |
  54                         `--------------------*/
  55
  56
  57 /*-------------------------------.
  58 | Create a new array of N errs.  |
  59 `-------------------------------*/
  60
  61 #define ERRS_ALLOC(Nerrs)                                               \
  62   (errs *) xcalloc ((unsigned) (sizeof (errs)                           \
  63                                   + (Nerrs - 1) * sizeof (short)), 1)
  64
  65
  66 errs *
  67 errs_new (int n)
  68 {
  69   errs *res = ERRS_ALLOC (n);
  70   res->nerrs = n;
  71   return res;
  72 }
  73
  74
  75 errs *
  76 errs_dup (errs *src)
  77 {
  78   errs *res = errs_new (src->nerrs);
  79   memcpy (res->errs, src->errs, src->nerrs * sizeof (src->errs[0]));
  80   return res;
  81 }
  82
  83
  84
  85
  86                         /*-------------.
  87                         | Reductions.  |
  88                         `-------------*/
  89
  90
  91 /*-------------------------------------.
  92 | Create a new array of N reductions.  |
  93 `-------------------------------------*/
  94
  95 #define REDUCTIONS_ALLOC(Nreductions)                                   \
  96   (reductions *) xcalloc ((unsigned) (sizeof (reductions)               \
  97                                   + (Nreductions - 1) * sizeof (short)), 1)
  98
  99 reductions *
 100 reductions_new (int n)
 101 {
 102   reductions *res = REDUCTIONS_ALLOC (n);
 103   res->nreds = n;
 104   return res;
 105 }
 106
 107
 108
 109                         /*---------.
 110                         | States.  |
 111                         `---------*/
 112
 113
 114 state_number_t nstates = 0;
 115 /* FINAL_STATE is properly set by new_state when it recognizes its
 116    accessing symbol: EOF.  */
 117 state_t *final_state = NULL;
 118
 119 /*------------------------------------------------------------.
 120 | Create a new state with ACCESSING_SYMBOL, for those items.  |
 121 `------------------------------------------------------------*/
 122
 123 state_t *
 124 state_new (symbol_number_t accessing_symbol,
 125            size_t core_size, item_number_t *core)
 126 {
 127   state_t *res;
 128
 129   if (nstates >= STATE_NUMBER_MAX)
 130     fatal (_("too many states (max %d)"), STATE_NUMBER_MAX);
 131
 132 #define STATE_ALLOC(Nitems)                                             \
 133   (state_t *) xcalloc ((unsigned) (sizeof (state_t)                     \
 134                                   + (Nitems - 1) * sizeof (item_number_t)), 1)
 135
 136   res = STATE_ALLOC (core_size);
 137   res->accessing_symbol = accessing_symbol;
 138   res->number = nstates;
 139   ++nstates;
 140   res->solved_conflicts = NULL;
 141
 142   res->nitems = core_size;
 143   memcpy (res->items, core, core_size * sizeof (core[0]));
 144
 145   return res;
 146 }
 147
 148
 149 /*--------------------------------------------------------------.
 150 | Print on OUT all the lookaheads such that this STATE wants to |
 151 | reduce this RULE.                                             |
 152 `--------------------------------------------------------------*/
 153
 154 void
 155 state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
 156 {
 157   int j, k;
 158   int nlookaheads = 0;
 159   /* Count the number of lookaheads corresponding to this rule.  */
 160   for (j = 0; j < state->nlookaheads; ++j)
 161     for (k = 0; k < ntokens; ++k)
 162       if (bitset_test (state->lookaheads[j], k)
 163           && state->lookaheads_rule[j]->number == rule->number)
 164         nlookaheads++;
 165
 166   /* Print them if there are.  */
 167   if (nlookaheads)
 168     {
 169       fprintf (out, "  [");
 170       for (j = 0; j < state->nlookaheads; ++j)
 171         for (k = 0; k < ntokens; ++k)
 172           if (bitset_test (state->lookaheads[j], k)
 173               && state->lookaheads_rule[j]->number == rule->number)
 174             fprintf (out, "%s%s",
 175                      symbol_tag_get (symbols[k]),
 176                      --nlookaheads ? ", " : "");
 177       fprintf (out, "]");
 178     }
 179 }