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 */