--- src/derivation.c | 107 ++++++++ src/derivation.h | 47 ++++ src/parse-simulation.c | 554 +++++++++++++++++++++++++++++++++++++++++ src/parse-simulation.h | 131 ++++++++++ 4 files changed, 839 insertions(+) create mode 100644 src/derivation.c create mode 100644 src/derivation.h create mode 100644 src/parse-simulation.c create mode 100644 src/parse-simulation.h
diff --git a/src/derivation.c b/src/derivation.c new file mode 100644 index 00000000..b845ba89 --- /dev/null +++ b/src/derivation.c @@ -0,0 +1,107 @@ +/* Counterexample derivation trees + + Copyright (C) 2019-2020 Free Software Foundation, Inc. + + This file is part of Bison, the GNU Compiler Compiler. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> +#include "derivation.h" +#include "system.h" + +static derivation d_dot = { -1, NULL }; + +const derivation * +derivation_dot (void) +{ + return &d_dot; +} + +derivation * +derivation_new (symbol_number sym, gl_list_t children) +{ + derivation *deriv = xmalloc (sizeof (derivation)); + deriv->sym = sym; + deriv->children = children; + return deriv; +} + +void +derivation_free (derivation *d) +{ + if (d && d != &d_dot) + { + if (d->children) + gl_list_free (d->children); + free (d); + } +} + +size_t +derivation_size (const derivation *deriv) +{ + if (!deriv->children) + return 1; + int size = 1; + gl_list_iterator_t it = gl_list_iterator (deriv->children); + derivation *child; + while (gl_list_iterator_next (&it, (const void **) &child, NULL)) + size += derivation_size (child); + return size; +} + +// these are used rarely enough that I don't think they should be interned. +void +derivation_print (const derivation *deriv, FILE *f) +{ + if (deriv == &d_dot) + { + fputs (" • ", f); + return; + } + symbol *sym = symbols[deriv->sym]; + if (!deriv->children) + { + fprintf (f, " %s ", sym->tag); + return; + } + gl_list_iterator_t it = gl_list_iterator (deriv->children); + derivation *child; + fprintf (f, " %s ::=[", sym->tag); + while (gl_list_iterator_next (&it, (const void **) &child, NULL)) + derivation_print (child, f); + fputs ("] ", f); +} + +void +derivation_print_leaves (const derivation *deriv, FILE *f) +{ + if (deriv == &d_dot) + { + fputs (" • ", f); + return; + } + if (!deriv->children) + { + symbol *sym = symbols[deriv->sym]; + fprintf (f, " %s ", sym->tag); + return; + } + + gl_list_iterator_t it = gl_list_iterator (deriv->children); + derivation *child; + while (gl_list_iterator_next (&it, (const void **) &child, NULL)) + derivation_print_leaves (child, f); +} diff --git a/src/derivation.h b/src/derivation.h new file mode 100644 index 00000000..c89d2f41 --- /dev/null +++ b/src/derivation.h @@ -0,0 +1,47 @@ +/* Counterexample derivation trees + + Copyright (C) 2019-2020 Free Software Foundation, Inc. + + This file is part of Bison, the GNU Compiler Compiler. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef DERIVATION_H +#define DERIVATION_H + +#include <gl_list.h> +#include "gram.h" + +/* + Derivations are trees of symbols such that each non terminal's + children are symbols that produce that nonterminal if they are + relevant to the counterexample. The leaves of a derivation form + a counterexample when printed. + */ + +typedef struct derivation +{ + symbol_number sym; + gl_list_t children; +} derivation; + +derivation *derivation_new (symbol_number sym, gl_list_t children); +size_t derivation_size (const derivation *deriv); +void derivation_print (const derivation *deriv, FILE *f); +void derivation_print_leaves (const derivation *deriv, FILE *f); +void derivation_free (derivation *deriv); + +const derivation *derivation_dot (void); + +#endif /* DERIVATION_H */ diff --git a/src/parse-simulation.c b/src/parse-simulation.c new file mode 100644 index 00000000..bb307760 --- /dev/null +++ b/src/parse-simulation.c @@ -0,0 +1,554 @@ +/* Parser simulator for unifying counterexample search + + Copyright (C) 2019-2020 Free Software Foundation, Inc. + + This file is part of Bison, the GNU Compiler Compiler. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> +#include <gl_linked_list.h> +#include <gl_xlist.h> +#include <stdlib.h> +#include "parse-simulation.h" +#include "nullable.h" +#include "lssi.h" + +typedef struct +{ + // elements newly added in this chunk + gl_list_t contents; + // properties of the linked list this chunk represents + const void *head_elt; + const void *tail_elt; + size_t total_size; +} ps_chunk; + +struct parse_state; +typedef struct parse_state +{ + // path of state-items the parser has traversed + ps_chunk state_items; + // list of derivations of the symbols + ps_chunk derivs; + struct parse_state *parent; + int reference_count; + // incremented during productions, + // decremented during reductions + int depth; + // whether the contents of the chunks should be + // prepended or appended to the list the chunks + // represent + bool prepend; + // causes chunk contents to be freed when the + // reference count is one. Used when only the chunk metadata + // will be needed. + bool free_contents_early; +} parse_state; + + +static void +ps_chunk_prepend (ps_chunk *chunk, const void *element) +{ + gl_list_add_first (chunk->contents, element); + chunk->head_elt = element; + ++chunk->total_size; + if (!chunk->tail_elt) + chunk->tail_elt = element; +} + +static void +ps_chunk_append (ps_chunk *chunk, const void *element) +{ + gl_list_add_last (chunk->contents, element); + chunk->tail_elt = element; + ++chunk->total_size; + if (!chunk->head_elt) + chunk->head_elt = element; +} + +static int allocs = 0; +static int frees = 0; + +static parse_state * +empty_parse_state (void) +{ + parse_state *ret = xcalloc (1, sizeof (parse_state)); + ret->state_items.contents = gl_list_create_empty (GL_LINKED_LIST, NULL, + NULL, NULL, true); + ret->derivs.contents = gl_list_create_empty (GL_LINKED_LIST, NULL, + NULL, NULL, true); + ++allocs; + return ret; +} + +parse_state * +new_parse_state (const state_item *si) +{ + parse_state *ret = empty_parse_state (); + ps_chunk_append (&ret->state_items, si); + ps_chunk_append (&ret->derivs, derivation_dot ()); + return ret; +} + +static parse_state * +copy_parse_state (bool prepend, parse_state *parent) +{ + parse_state *ret = xmalloc (sizeof (parse_state)); + memcpy (ret, parent, sizeof (parse_state)); + ret->state_items.contents = gl_list_create_empty (GL_LINKED_LIST, NULL, + NULL, NULL, true); + ret->derivs.contents = gl_list_create_empty (GL_LINKED_LIST, NULL, + NULL, NULL, true); + ret->parent = parent; + ret->prepend = prepend; + ret->reference_count = 0; + ret->free_contents_early = false; + ++parent->reference_count; + ++allocs; + return ret; +} + +bool +parse_state_derivation_completed (const parse_state *ps) +{ + return ps->derivs.total_size == 1; +} + +const derivation * +parse_state_derivation (const parse_state *ps) +{ + return ps->derivs.head_elt; +} + +const state_item * +parse_state_head (const parse_state *ps) +{ + return ps->state_items.head_elt; +} + +const state_item * +parse_state_tail (const parse_state *ps) +{ + return ps->state_items.tail_elt; +} + +int +parse_state_length (const parse_state *ps) +{ + return ps->state_items.total_size; +} + +int +parse_state_depth (const parse_state *ps) +{ + return ps->depth; +} + +void +parse_state_retain (parse_state *ps) +{ + ++ps->reference_count; +} + +void +parse_state_free_contents_early (parse_state *ps) +{ + ps->free_contents_early = true; +} + +void +parse_state_retain_deriv (parse_state *ps) +{ + ps->derivs.contents = NULL; +} + +void +free_parse_state (parse_state *ps) +{ + if (ps == NULL) + return; + --ps->reference_count; + // need to keep the parse state around + // for visited, but its contents can be freed + if ((ps->reference_count == 1 && ps->free_contents_early) || + (ps->reference_count == 0 && !ps->free_contents_early)) + { + if (ps->state_items.contents) + gl_list_free (ps->state_items.contents); + if (ps->derivs.contents) + gl_list_free (ps->derivs.contents); + free_parse_state (ps->parent); + } + if (ps->reference_count <= 0) + { + free (ps); + ++frees; + } +} + +size_t +parse_state_hasher (const parse_state *ps, size_t max) +{ + const ps_chunk *sis = &ps->state_items; + return ((state_item *) sis->head_elt - state_items + + (state_item *) sis->tail_elt - state_items + sis->total_size) % max; +} + +bool +parse_state_comparator (const parse_state *ps1, const parse_state *ps2) +{ + const ps_chunk *sis1 = &ps1->state_items; + const ps_chunk *sis2 = &ps2->state_items; + return sis1->head_elt == sis2->head_elt && + sis1->tail_elt == sis2->tail_elt && sis1->total_size == sis2->total_size; +} + + +void +parse_state_completed_steps (const parse_state *ps, int *shifts, int *productions) +{ + // traverse to the root parse_state, + // which will have a list of all completed productions. + const parse_state *root_ps = ps; + while (root_ps->parent) + root_ps = root_ps->parent; + + gl_list_t sis = root_ps->state_items.contents; + int count = 0; + gl_list_iterator_t it = gl_list_iterator (sis); + state_item *last = NULL; + state_item *next = NULL; + while (gl_list_iterator_next (&it, (const void **) &next, NULL)) + { + if (last && last->state == next->state) + ++count; + last = next; + } + *productions = count; + *shifts = root_ps->state_items.total_size - count; +} + +// takes an array of n gl_lists and flattens them into two list +// based off of the index split +static void +list_flatten_and_split (gl_list_t *l, gl_list_t *rets, int split, int n) +{ + int ret_index = 0; + int ret_array = 0; + for (int i = 0; i < n; ++i) + { + gl_list_iterator_t it = gl_list_iterator (l[i]); + gl_list_t l; + while (gl_list_iterator_next (&it, (const void **) &l, NULL)) + { + if (!l) + continue; + gl_list_iterator_t it2 = gl_list_iterator (l); + void *si; + while (gl_list_iterator_next (&it2, (const void **) &si, NULL)) + { + if (ret_index++ == split) + ++ret_array; + if (rets[ret_array]) + gl_list_add_last (rets[ret_array], si); + } + } + } +} + +// Emulates a reduction on a parse state by popping some amount of +// derivations and state_items off of the parse_state and returning +// the result in ret. Returns the derivation of what's popped. +static gl_list_t +parser_pop (parse_state *ps, int deriv_index, + int si_index, parse_state *ret) +{ + // prepend sis, append sis, prepend derivs, append derivs + gl_list_t chunks[4]; + for (int i = 0; i < 4; ++i) + chunks[i] = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, 1); + for (parse_state *pn = ps; pn != NULL; pn = pn->parent) + { + if (pn->prepend) + { + gl_list_add_last (chunks[0], pn->state_items.contents); + gl_list_add_last (chunks[2], pn->derivs.contents); + } + else + { + gl_list_add_first (chunks[1], pn->state_items.contents); + gl_list_add_first (chunks[3], pn->derivs.contents); + } + } + gl_list_t popped_derivs = + gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, 1); + gl_list_t ret_chunks[4] = { ret->state_items.contents, NULL, + ret->derivs.contents, popped_derivs + }; + list_flatten_and_split (chunks, ret_chunks, si_index, 2); + list_flatten_and_split (chunks + 2, ret_chunks + 2, deriv_index, 2); + size_t s_size = gl_list_size (ret->state_items.contents); + ret->state_items.total_size = s_size; + if (s_size > 0) + { + ret->state_items.tail_elt = gl_list_get_at (ret->state_items.contents, + s_size - 1); + ret->state_items.head_elt = + gl_list_get_at (ret->state_items.contents, 0); + } + else + { + ret->state_items.tail_elt = NULL; + ret->state_items.head_elt = NULL; + } + size_t d_size = gl_list_size (ret->derivs.contents); + ret->derivs.total_size = d_size; + if (d_size > 0) + { + ret->derivs.tail_elt = gl_list_get_at (ret->derivs.contents, + d_size - 1); + ret->derivs.head_elt = gl_list_get_at (ret->derivs.contents, 0); + } + else + { + ret->derivs.tail_elt = NULL; + ret->derivs.head_elt = NULL; + } + for (int i = 0; i < 4; ++i) + gl_list_free (chunks[i]); + return popped_derivs; +} + +void +parse_state_lists (parse_state *ps, gl_list_t *state_items, + gl_list_t *derivs) +{ + parse_state *temp = empty_parse_state (); + size_t si_size = ps->state_items.total_size; + size_t deriv_size = ps->derivs.total_size; + parser_pop (ps, si_size, deriv_size, temp); + *state_items = temp->state_items.contents; + *derivs = temp->derivs.contents; + // prevent the return lists from being freed + temp->state_items.contents = NULL; + temp->derivs.contents = NULL; + free_parse_state (temp); +} + +/** + * Compute the parse states that result from taking a transition on + * nullable symbols whenever possible from the given state_item. + */ +void +nullable_closure (parse_state *ps, state_item *si, gl_list_t states) +{ + parse_state *current_ps = ps; + state_item_number prev_sin = si - state_items; + for (state_item_number sin = si_trans[prev_sin]; + sin != -1; prev_sin = sin, sin = si_trans[sin]) + { + state_item *psi = state_items + prev_sin; + symbol_number sp = item_number_as_symbol_number (*psi->item); + if (ISTOKEN (sp) || !nullable[sp - ntokens]) + break; + + state_item *nsi = state_items + sin; + current_ps = copy_parse_state (false, current_ps); + ps_chunk_append (¤t_ps->state_items, nsi); + ps_chunk_append (¤t_ps->derivs, derivation_new (sp, NULL)); + ++current_ps->reference_count; + gl_list_add_last (states, current_ps); + } +} + +gl_list_t +simulate_transition (parse_state *ps) +{ + const state_item *si = ps->state_items.tail_elt; + symbol_number sym = item_number_as_symbol_number (*si->item); + // Transition on the same next symbol, taking nullable + // symbols into account. + gl_list_t result = + gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, + (gl_listelement_dispose_fn)free_parse_state, + true); + state_item_number si_next = si_trans[si - state_items]; + // check for disabled transition, shouldn't happen + // as any state_items that lead to these should be + // disabled. + if (si_next < 0) + return result; + parse_state *next_ps = copy_parse_state (false, ps); + ps_chunk_append (&next_ps->state_items, state_items + si_next); + ps_chunk_append (&next_ps->derivs, derivation_new (sym, NULL)); + ++next_ps->reference_count; + gl_list_add_last (result, next_ps); + + nullable_closure (next_ps, state_items + si_next, result); + return result; +} + +/** + * Determine if the given symbols are equal or their first sets + * intersect. + */ +static bool +compatible (symbol_number sym1, symbol_number sym2) +{ + if (sym1 == sym2) + return true; + if (ISTOKEN (sym1) && ISVAR (sym2)) + return bitset_test (FIRSTS (sym2), sym1); + else if (ISVAR (sym1) && ISTOKEN (sym2)) + return bitset_test (FIRSTS (sym1), sym2); + else if (ISVAR (sym1) && ISVAR (sym2)) + return !bitset_disjoint_p (FIRSTS (sym1), FIRSTS (sym2)); + else + return false; +} + +gl_list_t +simulate_production (parse_state *ps, symbol_number compat_sym) +{ + gl_list_t result = + gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, + (gl_listelement_dispose_fn)free_parse_state, + true); + const state_item *si = parse_state_tail (ps); + bitset prod = si_prods_lookup (si - state_items); + if (prod) + { + bitset_iterator biter; + state_item_number sin; + BITSET_FOR_EACH (biter, prod, sin, 0) + { + // Take production step only if lhs is not nullable and + // if first rhs symbol is compatible with compat_sym + state_item *next = state_items + sin; + item_number *itm1 = next->item; + if (!compatible (*itm1, compat_sym) || !production_allowed (si, next)) + continue; + parse_state *next_ps = copy_parse_state (false, ps); + ps_chunk_append (&next_ps->state_items, next); + ++next_ps->reference_count; + gl_list_add_last (result, next_ps); + if (next_ps->depth >= 0) + ++next_ps->depth; + nullable_closure (next_ps, next, result); + } + } + return result; +} + +// simulates a reduction on the given parse state, conflict_item is the +// item associated with ps's conflict. symbol_set is a lookahead set this +// reduction must be compatible with +gl_list_t +simulate_reduction (parse_state *ps, int rule_len, bitset symbol_set) +{ + gl_list_t result = + gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, + (gl_listelement_dispose_fn)free_parse_state, + true); + + int s_size = ps->state_items.total_size; + int d_size = ps->derivs.total_size; + if (ps->depth >= 0) + d_size--; // account for dot + parse_state *new_root = empty_parse_state (); + gl_list_t popped_derivs = parser_pop (ps, d_size - rule_len, + s_size - rule_len - 1, + new_root); + + // update derivation + state_item *si = (state_item *) ps->state_items.tail_elt; + const rule *r = item_rule (si->item); + symbol_number lhs = r->lhs->number; + derivation *deriv = derivation_new (lhs, popped_derivs); + --new_root->depth; + ps_chunk_append (&new_root->derivs, deriv); + + if (s_size != rule_len + 1) + { + state_item *tail = (state_item *) new_root->state_items.tail_elt; + ps_chunk_append (&new_root->state_items, + state_items + si_trans[tail - state_items]); + ++new_root->reference_count; + gl_list_add_last (result, new_root); + } + else + { + // The head state_item is a production item, so we need to prepend + // with possible source state-items. + const state_item *head = ps->state_items.head_elt; + gl_list_t prev = lssi_reverse_production (head, symbol_set); + gl_list_iterator_t it = gl_list_iterator (prev); + state_item *psis; + while (gl_list_iterator_next (&it, (const void **) &psis, NULL)) + { + //Prepend the result from the reverse production + parse_state *copy = copy_parse_state (true, new_root); + ps_chunk_prepend (©->state_items, psis); + + // Append the left hand side to the end of the parser state + copy = copy_parse_state (false, copy); + ps_chunk *sis = ©->state_items; + const state_item *tail = sis->tail_elt; + ps_chunk_append (sis, state_items + si_trans[tail - state_items]); + ++copy->reference_count; + gl_list_add_last (result, copy); + nullable_closure (copy, (state_item *) sis->tail_elt, result); + } + gl_list_free (prev); + } + return result; +} + +gl_list_t +parser_prepend (parse_state *ps) +{ + gl_list_t result = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, + (gl_listelement_dispose_fn) + free_parse_state, + true); + const state_item *head = ps->state_items.head_elt; + bitset prev = si_revs[head - state_items]; + symbol_number prepend_sym = + item_number_as_symbol_number (*(head->item - 1)); + bitset_iterator biter; + state_item_number sin; + BITSET_FOR_EACH (biter, prev, sin, 0) + { + parse_state *copy = copy_parse_state (true, ps); + copy->reference_count++; + ps_chunk_prepend (©->state_items, state_items + sin); + if (SI_TRANSITION (head)) + ps_chunk_prepend (©->derivs, derivation_new (prepend_sym, NULL)); + gl_list_add_last (result, copy); + } + return result; +} + +void +print_parse_state (parse_state *ps) +{ + printf ("(size %zu depth %d rc %d)\n", + ps->state_items.total_size, ps->depth, ps->reference_count); + print_state_item (ps->state_items.head_elt, stdout); + print_state_item (ps->state_items.tail_elt, stdout); + if (ps->derivs.total_size > 0) + derivation_print (ps->derivs.head_elt, stdout); + putc ('\n', stdout); +} diff --git a/src/parse-simulation.h b/src/parse-simulation.h new file mode 100644 index 00000000..7bb596fd --- /dev/null +++ b/src/parse-simulation.h @@ -0,0 +1,131 @@ +/* Parser simulator for unifying counterexample search + + Copyright (C) 2019-2020 Free Software Foundation, Inc. + + This file is part of Bison, the GNU Compiler Compiler. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef PARSE_SIMULATION_H +#define PARSE_SIMULATION_H + +#include <stdio.h> +#include <gl_xlist.h> +#include "state-item.h" +#include "derivation.h" + +/* + Simulating states of the parser: + Each state is an array of state-items and an array of derivations. + Each consecutive state-item represents a transition/goto or production, + and the derivations are the dereivation trees associated with the symbols + transitioned on each step. In more detail: + + Parse states are stored as a tree. Each new parse state contains two "chunks," + one corresponding to its state-items and the other corresponding to its derivations. + Chunks only have new elements which weren't present in its parent. + Each chunk also stores the head, tail, and total_size of the list it represents. + So if a parse state was to be copied it retains the list metadata but its + contents are empty. + + A transition gets the state-item which the last state-item of the parse state + transitions to. This is appended to the state-item list, and a derivation with + just the symbol being transitioned on is appended to the derivation list. + A production appends the new state-item, but does not have a derivation + associated with it. + + A reduction looks at the rule of the last state-item in the state, and pops + the last few state-items that make up the rhs of the rule along with their + derivations. The derivations become the derivation of the lhs which is then + shifted over. + + Effectively, everytime a derivation is appended, it represents a shift in + the parser. So a parse state that contains + start: A . B C D + start: A B C D . + and the state-items in between will represent a parser that has BCD on the + parse stack. + + However, the above example cannot be reduced, as it's missing A. + Since we start at a state-item that can have a dot in the middle of a rule, + it's necessary to support a prepend operation. Luckily the prepend operations + are very similar to transitions and productions with the difference being that + they operate on the head of the state-item list instead of the tail. + + A production + A transition gets the state-item which the last state-item of the parse state + transitions to. This is appended to the state-item list, and a derivation with + just the symbol being transitioned on is appended to the derivation list. + + */ + +typedef struct parse_state parse_state; + +parse_state *new_parse_state (const state_item *conflict); + +size_t parse_state_hasher (const parse_state *ps, size_t max); + +bool parse_state_comparator (const parse_state *ps1, const parse_state *ps2); + +/* Memory management */ + +void parse_state_retain (parse_state *ps); +/* This allows a parse_state to free its contents list + * when its reference count reaches 1. This is used to + * free memory while the parse state is in a hash set. */ +void parse_state_free_contents_early (parse_state *ps); +void parse_state_retain_deriv (parse_state *ps); +void free_parse_state (parse_state *ps); + +/* counts the amount of shift and production steps in this parse state */ +void parse_state_completed_steps (const parse_state *ps, int *shifts, int *productions); + +/* parse state getters */ +bool parse_state_derivation_completed (const parse_state *ps); +const derivation *parse_state_derivation (const parse_state *ps); +const state_item *parse_state_head (const parse_state *ps); +const state_item *parse_state_tail (const parse_state *ps); +int parse_state_length (const parse_state *ps); +int parse_state_depth (const parse_state *ps); + +/* returns the linked lists that the parse state is supposed to represent */ +void parse_state_lists (parse_state *ps, gl_list_t *state_items, + gl_list_t *derivs); + +/* various functions that return a list of states based off of + * whatever operation is simulated. After whatever operation, every possible + * transition on nullable nonterminals will be added to the returned list. */ + +/* Look at the tail state-item of the parse state and transition on the symbol + * after its dot. The symbol gets added to derivs, and the resulting state-item + * is appended to state-items. */ +gl_list_t simulate_transition (parse_state *ps); + +/* Look at all of the productions for the non-terminal following the dot in the tail + * state-item. Appends to state-items each production state-item which may start with + * compat_sym. */ +gl_list_t simulate_production (parse_state *ps, symbol_number compat_sym); + +/* Removes the last rule_len state-items along with their derivations. A new state-item is + * appended representing the goto after the reduction. A derivation for the non-terminal that + * was just reduced is appended which consists of the list of derivations that were just removed. */ +gl_list_t simulate_reduction (parse_state *ps, int rule_len, + bitset symbol_set); + +/* Generate states with a state-item prepended for each state-item that has a + * transition or production step to ps's head. */ +gl_list_t parser_prepend (parse_state *ps); + +void print_parse_state (parse_state *ps); +#endif /* PARSE_SIMULATION_H */ -- 2.20.1 (Apple Git-117)
