src/parse-simulation.h

   1 /* Parser simulator for unifying counterexample search
   2
   3    Copyright (C) 2020-2021 Free Software Foundation, Inc.
   4
   5    This file is part of Bison, the GNU Compiler Compiler.
   6
   7    This program is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  19
  20 #ifndef PARSE_SIMULATION_H
  21 # define PARSE_SIMULATION_H
  22
  23 # include <stdio.h>
  24 # include <gl_xlist.h>
  25
  26 # include "derivation.h"
  27 # include "state-item.h"
  28
  29 /*
  30   Simulating states of the parser:
  31   Each state is an array of state-items and an array of derivations.
  32   Each consecutive state-item represents a transition/goto or production,
  33   and the derivations are the derivation trees associated with the symbols
  34   transitioned on each step. In more detail:
  35
  36   Parse states are stored as a tree. Each new parse state contains two "chunks,"
  37   one corresponding to its state-items and the other corresponding to its derivations.
  38   Chunks only have new elements which weren't present in its parent.
  39   Each chunk also stores the head, tail, and total_size of the list it represents.
  40   So if a parse state was to be copied it retains the list metadata but its
  41   contents are empty.
  42
  43   A transition gets the state-item which the last state-item of the parse state
  44   transitions to. This is appended to the state-item list, and a derivation with
  45   just the symbol being transitioned on is appended to the derivation list.
  46   A production appends the new state-item, but does not have a derivation
  47   associated with it.
  48
  49   A reduction looks at the rule of the last state-item in the state, and pops
  50   the last few state-items that make up the rhs of the rule along with their
  51   derivations. The derivations become the derivation of the lhs which is then
  52   shifted over.
  53
  54   Effectively, every time a derivation is appended, it represents a shift in
  55   the parser. So a parse state that contains
  56    start: A . B C D
  57    start: A B C D .
  58   and the state-items in between will represent a parser that has BCD on the
  59   parse stack.
  60
  61   However, the above example cannot be reduced, as it's missing A.
  62   Since we start at a state-item that can have a dot in the middle of a rule,
  63   it's necessary to support a prepend operation. Luckily the prepend operations
  64   are very similar to transitions and productions with the difference being that
  65   they operate on the head of the state-item list instead of the tail.
  66
  67   A production
  68   A transition gets the state-item which the last state-item of the parse state
  69   transitions to. This is appended to the state-item list, and a derivation with
  70   just the symbol being transitioned on is appended to the derivation list.
  71
  72  */
  73
  74 typedef struct parse_state parse_state;
  75 typedef gl_list_t parse_state_list;
  76
  77 static inline bool
  78 parse_state_list_next (gl_list_iterator_t *it, parse_state **ps)
  79 {
  80   const void *p = NULL;
  81   bool res = gl_list_iterator_next (it, &p, NULL);
  82   if (res)
  83     *ps = (parse_state *) p;
  84   else
  85     gl_list_iterator_free (it);
  86   return res;
  87 }
  88
  89 parse_state *new_parse_state (const state_item *conflict);
  90
  91 size_t parse_state_hasher (const parse_state *ps, size_t max);
  92
  93 bool parse_state_comparator (const parse_state *ps1, const parse_state *ps2);
  94
  95 /* Memory management */
  96
  97 void parse_state_retain (parse_state *ps);
  98 /* This allows a parse_state to free its contents list
  99  * when its reference count reaches 1. This is used to
 100  * free memory while the parse state is in a hash set. */
 101 void parse_state_free_contents_early (parse_state *ps);
 102 void free_parse_state (parse_state *ps);
 103
 104 /* counts the amount of shift and production steps in this parse state */
 105 void parse_state_completed_steps (const parse_state *ps, int *shifts, int *productions);
 106
 107 /* parse state getters */
 108 bool parse_state_derivation_completed (const parse_state *ps);
 109 derivation *parse_state_derivation (const parse_state *ps);
 110 const state_item *parse_state_head (const parse_state *ps);
 111 const state_item *parse_state_tail (const parse_state *ps);
 112 int parse_state_length (const parse_state *ps);
 113 int parse_state_depth (const parse_state *ps);
 114
 115 /* returns the linked lists that the parse state is supposed to represent */
 116 void parse_state_lists (parse_state *ps, state_item_list *state_items,
 117                         derivation_list *derivs);
 118
 119 /* various functions that return a list of states based off of
 120  * whatever operation is simulated. After whatever operation, every possible
 121  * transition on nullable nonterminals will be added to the returned list. */
 122
 123 /* Look at the tail state-item of the parse state and transition on the symbol
 124  * after its dot. The symbol gets added to derivs, and the resulting state-item
 125  * is appended to state-items. */
 126 parse_state_list simulate_transition (parse_state *ps);
 127
 128 /* Look at all of the productions for the nonterminal following the dot in the tail
 129  * state-item. Appends to state-items each production state-item which may start with
 130  * compat_sym. */
 131 parse_state_list simulate_production (parse_state *ps, symbol_number compat_sym);
 132
 133 /* Removes the last rule_len state-items along with their derivations. A new state-item is
 134  * appended representing the goto after the reduction. A derivation for the nonterminal that
 135  * was just reduced is appended which consists of the list of derivations that were just removed. */
 136 parse_state_list simulate_reduction (parse_state *ps, int rule_len,
 137                               bitset symbol_set);
 138
 139 /* Generate states with a state-item prepended for each state-item that has a
 140  * transition or production step to ps's head. */
 141 parse_state_list parser_prepend (parse_state *ps);
 142
 143 /* For debugging traces.  */
 144 void print_parse_state (parse_state *ps);
 145
 146 #endif /* PARSE_SIMULATION_H */