1 /* IELR's inadequacy annotation list. 2 3 Copyright (C) 2009-2012 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 <http://www.gnu.org/licenses/>. */ 19 20 #ifndef ANNOTATION_LIST_H_ 21 # define ANNOTATION_LIST_H_ 22 23 #include <bitsetv.h> 24 #include "Sbitset.h" 25 #include "InadequacyList.h" 26 #include "state.h" 27 28 typedef unsigned int AnnotationIndex; 29 30 /** 31 * A node in a list of annotations on a particular LR(0) state. Each 32 * annotation records how isocores of that LR(0) state might contribute to an 33 * individual inadequacy, which might manifest in a different state. Don't 34 * break encapsulation by modifying the fields directly. Use the provided 35 * interface functions. 36 */ 37 typedef struct AnnotationList 38 { 39 /** The next node in the list or \c NULL if none. */ 40 struct AnnotationList *next; 41 /** The \c InadequacyList node describing how this inadequacy manifests. */ 42 InadequacyList *inadequacyNode; 43 /** 44 * List of how the "always", "never", and potential contributions of the 45 * inadequacy might be made by isocores of the annotated LR(0) state: 46 * - The number of rows is the number of contributions. That is, 47 * <tt>AnnotationList::inadequacyNode->contributionCount</tt>. 48 * - The token associated with contribution \c i is 49 * <tt>InadequacyList__getContributionToken (AnnotationList::inadequacyNode, i)</tt>. 50 * - Iff <tt>AnnotationList::contributions[i] = NULL</tt>, contribution 51 * \c i is an "always" contribution. That is, for every isocore of the 52 * annotated LR(0) state, its core or the core of one its eventual 53 * successors will definitely make this contribution to the inadequacy. 54 * It may contribute by either: 55 * - Creating a shift of contribution <tt>i</tt>'s token in the state 56 * that can manifest the inadequacy. 57 * - Propagating that token to the lookahead set of contribution 58 * <tt>i</tt>'s reduction in the state that can manifest the 59 * inadequacy. 60 * - Otherwise: 61 * - The number of columns in <tt>AnnotationList::contributions[i]</tt> 62 * is the number of kernel items in any isocore of the annotated LR(0) 63 * state. 64 * - Iff <tt>AnnotationList::contributions[i]</tt> is empty, contribution 65 * \c i is a "never" contribution. That is, no isocore of the 66 * annotated LR(0) state can make this contribution to the inadequacy. 67 * - Otherwise, for each bit \c j that is set in 68 * <tt>AnnotationList::contributions[i]</tt>, if the token associated 69 * with contribution \c i is present in the lookahead set of kernel 70 * item \c j of an isocore of the annotated LR(0) state, that isocore 71 * will make contribution \c i to the inadequacy by propagating the 72 * contribution's token to the lookahead set of the contribution's 73 * reduction in the state that can manifest the inadequacy. 74 */ 75 Sbitset contributions[1]; 76 } AnnotationList; 77 78 /** 79 * \pre 80 * - <tt>s != NULL</tt>. 81 * - \c follow_kernel_items, \c always_follows, and \c predecessors were 82 * computed by \c ielr_compute_auxiliary_tables. 83 * - The size of each of \c annotation_lists and \c annotation_counts is 84 * \c ::nstates. 85 * - If no \c InadequacyList nodes are currently allocated for the 86 * parser tables to which \c s belongs, then it is best if 87 * <tt>*inadequacy_list_node_count</tt> is zero to avoid overflow. 88 * Otherwise, <tt>*inadequacy_list_node_count</tt> has not been 89 * modified by any function except 90 * \c AnnotationList__compute_from_inadequacies since the invocation 91 * of \c AnnotationList__compute_from_inadequacies that constructed 92 * the first of the \c InadequacyList nodes currently allocated for 93 * those parser tables. 94 * \post 95 * - <tt>inadequacy_lists[s->number]</tt> now describes all inadequacies that 96 * manifest in \c s. 97 * - For every state <tt>states[i]</tt>, <tt>annotation_lists[i]</tt> now 98 * contains all annotations associated with all inadequacies that manifest 99 * in \c s. 100 * - <tt>annotation_counts[i]</tt> was incremented by the number of new 101 * annotations added to <tt>states[i]</tt>. 102 * - <tt>*max_contributionsp</tt> is the higher of: 103 * - The maximum number of contributions computed per annotation. 104 * - <tt>*max_contributionsp \@pre</tt>. 105 * - All memory for all new annotations was allocated on 106 * \c annotations_obstackp. 107 */ 108 void 109 AnnotationList__compute_from_inadequacies ( 110 state *s, bitsetv follow_kernel_items, bitsetv always_follows, 111 state ***predecessors, bitset **item_lookahead_sets, 112 InadequacyList **inadequacy_lists, AnnotationList **annotation_lists, 113 AnnotationIndex *annotation_counts, 114 ContributionIndex *max_contributionsp, 115 struct obstack *annotations_obstackp, 116 InadequacyListNodeCount *inadequacy_list_node_count); 117 118 /** 119 * \pre 120 * - <tt>self != NULL</tt>. 121 * - \c nitems is the number of kernel items in the LR(0) state that every 122 * node in the list \c self annotates. 123 * \post 124 * - A textual representation of all nodes in the list \c self was printed to 125 * stderr. \c spaces spaces were printed before each line of the text. 126 */ 127 void AnnotationList__debug (AnnotationList const *self, size_t nitems, 128 int spaces); 129 130 /** 131 * \pre 132 * - <tt>self != NULL</tt>. 133 * - \c nitems is the number of kernel items in the LR(0) state that \c self 134 * annotates. 135 * - The number of rows in \c lookahead_filter is at least \c nitems, and the 136 * number of columns is \c ::ntokens. 137 * \post 138 * - <tt>lookahead_filter[i][j]</tt> is set iff some annotation in the list 139 * \c self lists token \c j in kernel item \c i as a contributor. 140 */ 141 void AnnotationList__computeLookaheadFilter (AnnotationList const *self, 142 size_t nitems, 143 bitsetv lookahead_filter); 144 145 /** 146 * \pre 147 * - <tt>self != NULL</tt>. 148 * - \c nitems is the number of kernel items in the LR(0) state that \c self 149 * annotates. 150 * - \c lookaheads describes the lookahead sets on the kernel items of some 151 * isocore of the LR(0) state that \c self annotates. Either: 152 * - <tt>lookaheads = NULL</tt> only if the lookahead set on every kernel 153 * item is empty. 154 * - For any <tt>0 <= i < nitems</tt>, <tt>lookaheads[i]</tt> is either: 155 * - \c NULL only if the lookahead set on kernel item \c i is empty. 156 * - The (possibly empty) lookahead set on kernel item \c i. 157 * \post 158 * - If <tt>require_split_stable = false</tt>, \c result = either: 159 * - \c ContributionIndex__none iff the state described by \c lookaheads 160 * makes none of the contributions in \c self. 161 * - The index of the dominating contribution in \c self that is made by 162 * that state. 163 * - \c ContributionIndex__error_action to indicate that the inadequacy 164 * manifests as a conflict and that a syntax error action (because of a 165 * %nonassoc) dominates instead. 166 * - Otherwise, \c result is the same as if <tt>require_split_stable = 167 * false</tt> except that it is also \c ContributionIndex__none if there 168 * are contributions made by the state but the dominating contribution is 169 * not split-stable. By split-stable, we mean that the dominating 170 * contribution cannot change due to loss of one or more potential 171 * contributions due to loss of lookaheads due to splitting of the state. 172 * - After determining which contributions are actually made by the state, 173 * the algorithm for determining which contribution dominates in the 174 * conflict is intended to choose exactly the same action as conflicts.c 175 * would choose... no matter how crazy conflicts.c's choice is. 176 */ 177 ContributionIndex 178 AnnotationList__computeDominantContribution (AnnotationList const *self, 179 size_t nitems, bitset *lookaheads, 180 bool require_split_stable); 181 182 #endif /* !ANNOTATION_LIST_H_ */ 183