1  /* Compute lookahead criteria for bison,
       2  
       3     Copyright (C) 1984, 1986, 1989, 2000, 2002, 2004, 2006-2007,
       4     2009-2015, 2018-2021 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 <https://www.gnu.org/licenses/>.  */
      20  
      21  #ifndef LALR_H_
      22  # define LALR_H_
      23  
      24  # include <bitset.h>
      25  # include <bitsetv.h>
      26  
      27  /* Import the definition of RULE_T. */
      28  # include "gram.h"
      29  
      30  /* Import the definition of CORE, TRANSITIONS and REDUCTIONS. */
      31  # include "state.h"
      32  
      33  
      34  /** Build the LALR(1) automaton.
      35  
      36     Find which rules need lookahead in each state, and which lookahead
      37     tokens they accept.
      38  
      39     Also builds:
      40       - #goto_map
      41       - #from_state
      42       - #to_state
      43       - #goto_follows
      44  */
      45  void lalr (void);
      46  
      47  /**
      48   * Set #nLA and allocate all reduction lookahead sets.  Normally invoked by
      49   * #lalr.
      50   */
      51  void initialize_LA (void);
      52  
      53  /**
      54   * Build only:
      55   *   - #goto_map
      56   *   - #from_state
      57   *   - #to_state
      58   * Normally invoked by #lalr.
      59   */
      60  void set_goto_map (void);
      61  
      62  /**
      63   * Update state numbers recorded in #goto_map, #from_state, and #to_state such
      64   * that:
      65   *   - \c nstates_old is the old number of states.
      66   *   - Where \c i is the old state number, <tt>old_to_new[i]</tt> is either:
      67   *     - \c nstates_old if state \c i is removed because it is unreachable.
      68   *       Thus, remove all goto entries involving this state.
      69   *     - The new state number.
      70   */
      71  void lalr_update_state_numbers (state_number old_to_new[],
      72                                  state_number nstates_old);
      73  
      74  
      75  /** Release the information related to lookahead tokens.
      76  
      77     Can be performed once the action tables are computed.  */
      78  void lalr_free (void);
      79  
      80  typedef size_t goto_number;
      81  # define GOTO_NUMBER_MAXIMUM ((goto_number) -1)
      82  
      83  /** Index into #from_state and #to_state.
      84  
      85     All the transitions that accept a particular variable are grouped
      86     together in FROM_STATE and TO_STATE, with indexes from GOTO_MAP[I -
      87     NTOKENS] to GOTO_MAP[I - NTOKENS + 1] - 1 (including both).  */
      88  extern goto_number *goto_map;
      89  
      90  /** The size of #from_state and #to_state.  */
      91  extern goto_number ngotos;
      92  
      93  /** State number which a transition leads from.  */
      94  extern state_number *from_state;
      95  
      96  /** State number it leads to.  */
      97  extern state_number *to_state;
      98  
      99  /** The number of the goto from state SRC labeled with nterm SYM.  */
     100  goto_number map_goto (state_number src, symbol_number sym);
     101  
     102  /* goto_follows[i] is the set of tokens following goto i.  */
     103  extern bitsetv goto_follows;
     104  
     105  #endif /* !LALR_H_ */