diff options
Diffstat (limited to 'src/AnnotationList.h')
| -rw-r--r-- | src/AnnotationList.h | 177 |
1 files changed, 177 insertions, 0 deletions
diff --git a/src/AnnotationList.h b/src/AnnotationList.h new file mode 100644 index 00000000..02d4a2be --- /dev/null +++ b/src/AnnotationList.h @@ -0,0 +1,177 @@ +/* IELR's inadequacy annotation list. + + Copyright (C) 2009 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 ANNOTATION_LIST_H_ +# define ANNOTATION_LIST_H_ + +#include <bitsetv.h> +#include "Sbitset.h" +#include "InadequacyList.h" +#include "state.h" + +typedef unsigned int AnnotationIndex; + +/** + * A node in a list of annotations on a particular LR(0) state. Each + * annotation records how isocores of that LR(0) state might contribute to an + * individual inadequacy, which might manifest in a different state. Don't + * break encapsulation by modifying the fields directly. Use the provided + * interface functions. + */ +typedef struct AnnotationList +{ + /** The next node in the list or \c NULL if none. */ + struct AnnotationList *next; + /** The \c InadequacyList node describing how this inadequacy manifests. */ + InadequacyList *inadequacyNode; + /** + * List of how the "always", "never", and potential contributions of the + * inadequacy might be made by isocores of the annotated LR(0) state: + * - The number of rows is the number of contributions. That is, + * <tt>AnnotationList::inadequacyNode->contributionCount</tt>. + * - The token associated with contribution \c i is + * <tt>InadequacyList__getContributionToken (AnnotationList::inadequacyNode, i)</tt>. + * - Iff <tt>AnnotationList::contributions[i] = NULL</tt>, contribution + * \c i is an "always" contribution. That is, for every isocore of the + * annotated LR(0) state, its core or the core of one its eventual + * successors will definitely make this contribution to the inadequacy. + * It may contribute by either: + * - Creating a shift of contribution <tt>i</tt>'s token in the state + * that can manifest the inadequacy. + * - Propagating that token to the lookahead set of contribution + * <tt>i</tt>'s reduction in the state that can manifest the + * inadequacy. + * - Otherwise: + * - The number of columns in <tt>AnnotationList::contributions[i]</tt> + * is the number of kernel items in any isocore of the annotated LR(0) + * state. + * - Iff <tt>AnnotationList::contributions[i]</tt> is empty, contribution + * \c i is a "never" contribution. That is, no isocore of the + * annotated LR(0) state can make this contribution to the inadequacy. + * - Otherwise, for each bit \c j that is set in + * <tt>AnnotationList::contributions[i]</tt>, if the token associated + * with contribution \c i is present in the lookahead set of kernel + * item \c j of an isocore of the annotated LR(0) state, that isocore + * will make contribution \c i to the inadequacy by propagating the + * contribution's token to the lookahead set of the contribution's + * reduction in the state that can manifest the inadequacy. + */ + Sbitset contributions[1]; +} AnnotationList; + +/** + * \pre + * - <tt>s != NULL</tt>. + * - \c follow_kernel_items, \c always_follows, and \c predecessors were + * computed by \c ielr_compute_auxiliary_tables. + * - The size of each of \c annotation_lists and \c annotation_counts is + * \c ::nstates. + * \post + * - <tt>inadequacy_lists[s->number]</tt> now describes all inadequacies that + * manifest in \c s. + * - For every state <tt>states[i]</tt>, <tt>annotation_lists[i]</tt> now + * contains all annotations associated with all inadequacies that manifest + * in \c s. + * - <tt>annotation_counts[i]</tt> was incremented by the number of new + * annotations added to <tt>states[i]</tt>. + * - <tt>*max_contributionsp</tt> is the higher of: + * - The maximum number of contributions computed per annotation. + * - <tt>*max_contributionsp \@pre</tt>. + * - All memory for all new annotations was allocated on + * \c annotations_obstackp. + */ +void +AnnotationList__compute_from_inadequacies (state *s, + bitsetv follow_kernel_items, + bitsetv always_follows, + state ***predecessors, + bitset **item_lookahead_sets, + InadequacyList **inadequacy_lists, + AnnotationList **annotation_lists, + AnnotationIndex *annotation_counts, + ContributionIndex + *max_contributionsp, + struct obstack + *annotations_obstackp); + +/** + * \pre + * - <tt>self != NULL</tt>. + * - \c nitems is the number of kernel items in the LR(0) state that every + * node in the list \c self annotates. + * \post + * - A textual representation of all nodes in the list \c self was printed to + * stderr. \c spaces spaces were printed before each line of the text. + */ +void AnnotationList__debug (AnnotationList const *self, size_t nitems, + int spaces); + +/** + * \pre + * - <tt>self != NULL</tt>. + * - \c nitems is the number of kernel items in the LR(0) state that \c self + * annotates. + * - The number of rows in \c lookahead_filter is at least \c nitems, and the + * number of columns is \c ::ntokens. + * \post + * - <tt>lookahead_filter[i][j]</tt> is set iff some annotation in the list + * \c self lists token \c j in kernel item \c i as a contributor. + */ +void AnnotationList__computeLookaheadFilter (AnnotationList const *self, + size_t nitems, + bitsetv lookahead_filter); + +/** + * \pre + * - <tt>self != NULL</tt>. + * - \c nitems is the number of kernel items in the LR(0) state that \c self + * annotates. + * - \c lookaheads describes the lookahead sets on the kernel items of some + * isocore of the LR(0) state that \c self annotates. Either: + * - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel + * item is empty. + * - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> is either: + * - \c NULL only if the lookahead set on kernel item \c i is empty. + * - The (possibly empty) lookahead set on kernel item \c i. + * \post + * - If <tt>require_split_stable = false</tt>, \c result = either: + * - \c ContributionIndex__none iff the state described by \c lookaheads + * makes none of the contributions in \c self. + * - The index of the dominating contribution in \c self that is made by + * that state. + * - \c ContributionIndex__error_action to indicate that the inadequacy + * manifests as a conflict and that a syntax error action (because of a + * %nonassoc) dominates instead. + * - Otherwise, \c result is the same as if <tt>require_split_stable = + * false</tt> except that it is also \c ContributionIndex__none if there + * are contributions made by the state but the dominating contribution is + * not split-stable. By split-stable, we mean that the dominating + * contribution cannot change due to loss of one or more potential + * contributions due to loss of lookaheads due to splitting of the state. + * - After determining which contributions are actually made by the state, + * the algorithm for determining which contribution dominates in the + * conflict is intended to choose exactly the same action as conflicts.c + * would choose... no matter how crazy conflicts.c's choice is. + */ +ContributionIndex +AnnotationList__computeDominantContribution (AnnotationList const *self, + size_t nitems, bitset *lookaheads, + bool require_split_stable); + +#endif /* !ANNOTATION_LIST_H_ */ |