105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* IELR main implementation. 205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 2009-2012 Free Software Foundation, Inc. 405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 505436638acc7c010349a69c3395f1a57c642dc62Ying Wang This file is part of Bison, the GNU Compiler Compiler. 605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 705436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is free software: you can redistribute it and/or modify 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang it under the terms of the GNU General Public License as published by 905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation, either version 3 of the License, or 1005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 1105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1205436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is distributed in the hope that it will be useful, 1305436638acc7c010349a69c3395f1a57c642dc62Ying Wang but WITHOUT ANY WARRANTY; without even the implied warranty of 1405436638acc7c010349a69c3395f1a57c642dc62Ying Wang MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1505436638acc7c010349a69c3395f1a57c642dc62Ying Wang GNU General Public License for more details. 1605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1705436638acc7c010349a69c3395f1a57c642dc62Ying Wang You should have received a copy of the GNU General Public License 1805436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 1905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <config.h> 2105436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "system.h" 2205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2305436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "ielr.h" 2405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2505436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <bitset.h> 2605436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <timevar.h> 2705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2805436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "AnnotationList.h" 2905436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "derives.h" 3005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "getargs.h" 3105436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "lalr.h" 3205436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "muscle-tab.h" 3305436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "nullable.h" 3405436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "relation.h" 3505436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "state.h" 3605436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "symtab.h" 3705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3805436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** Records the value of the \%define variable lr.type. */ 3905436638acc7c010349a69c3395f1a57c642dc62Ying Wangtypedef enum { LR_TYPE__LALR, LR_TYPE__IELR, LR_TYPE__CANONICAL_LR } LrType; 4005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 4105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 4205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post: 4305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c result = a new \c bitset of size \c ::nritems such that any bit \c i 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * is set iff <tt>ritem[i]</tt> is a nonterminal after which all ritems in 4505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * the same RHS are nullable nonterminals. In other words, the follows of 4605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * a goto on <tt>ritem[i]</tt> include the lookahead set of the item. 4705436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 4805436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic bitset 4905436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_ritem_sees_lookahead_set (void) 5005436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 5105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset result = bitset_create (nritems, BITSET_FIXED); 5205436638acc7c010349a69c3395f1a57c642dc62Ying Wang unsigned int i = nritems-1; 5305436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (i>0) 5405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 5505436638acc7c010349a69c3395f1a57c642dc62Ying Wang --i; 5605436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (!item_number_is_rule_number (ritem[i]) 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang && ISVAR (ritem[i]) 5805436638acc7c010349a69c3395f1a57c642dc62Ying Wang && nullable [item_number_as_symbol_number (ritem[i]) - ntokens]) 5905436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set (result, i--); 6005436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!item_number_is_rule_number (ritem[i]) && ISVAR (ritem[i])) 6105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set (result, i--); 6205436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (!item_number_is_rule_number (ritem[i]) && i>0) 6305436638acc7c010349a69c3395f1a57c642dc62Ying Wang --i; 6405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 6505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (trace_flag & trace_ielr) 6605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 6705436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "ritem_sees_lookahead_set:\n"); 6805436638acc7c010349a69c3395f1a57c642dc62Ying Wang debug_bitset (result); 6905436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "\n"); 7005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 7105436638acc7c010349a69c3395f1a57c642dc62Ying Wang return result; 7205436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 7305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 7405436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 7505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre: 7605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c ritem_sees_lookahead_set was computed by 7705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_ritem_sees_lookahead_set. 7805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post: 7905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Each of \c *edgesp and \c *edge_countsp is a new array of size 8005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ::ngotos. 8105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>(*edgesp)[i]</tt> points to a \c goto_number array of size 8205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>(*edge_countsp)[i]+1</tt>. 8305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - In such a \c goto_number array, the last element is \c ::END_NODE. 8405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - All remaining elements are the indices of the gotos to which there is an 8505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * internal follow edge from goto \c i. 8605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - There is an internal follow edge from goto \c i to goto \c j iff both: 8705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The from states of gotos \c i and \c j are the same. 8805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The transition nonterminal for goto \c i appears as the first RHS 8905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * symbol of at least one production for which both: 9005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The LHS is the transition symbol of goto \c j. 9105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - All other RHS symbols are nullable nonterminals. 9205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - In other words, the follows of goto \c i include the follows of 9305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * goto \c j and it's an internal edge because the from states are the 9405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * same. 9505436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 9605436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 9705436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_internal_follow_edges (bitset ritem_sees_lookahead_set, 9805436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number ***edgesp, int **edge_countsp) 9905436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 10005436638acc7c010349a69c3395f1a57c642dc62Ying Wang *edgesp = xnmalloc (ngotos, sizeof **edgesp); 10105436638acc7c010349a69c3395f1a57c642dc62Ying Wang *edge_countsp = xnmalloc (ngotos, sizeof **edge_countsp); 10205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 10305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset sources = bitset_create (ngotos, BITSET_FIXED); 10405436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number i; 10505436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < ngotos; ++i) 10605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*edge_countsp)[i] = 0; 10705436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < ngotos; ++i) 10805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 10905436638acc7c010349a69c3395f1a57c642dc62Ying Wang int nsources = 0; 11005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 11105436638acc7c010349a69c3395f1a57c642dc62Ying Wang rule **rulep; 11205436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (rulep = derives[states[to_state[i]]->accessing_symbol 11305436638acc7c010349a69c3395f1a57c642dc62Ying Wang - ntokens]; 11405436638acc7c010349a69c3395f1a57c642dc62Ying Wang *rulep; 11505436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++rulep) 11605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 11705436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If there is at least one RHS symbol, if the first RHS symbol 11805436638acc7c010349a69c3395f1a57c642dc62Ying Wang is a nonterminal, and if all remaining RHS symbols (if any) 11905436638acc7c010349a69c3395f1a57c642dc62Ying Wang are nullable nonterminals, create an edge from the LHS 12005436638acc7c010349a69c3395f1a57c642dc62Ying Wang symbol's goto to the first RHS symbol's goto such that the RHS 12105436638acc7c010349a69c3395f1a57c642dc62Ying Wang symbol's goto will be the source of the edge after the 12205436638acc7c010349a69c3395f1a57c642dc62Ying Wang eventual relation_transpose below. 12305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 12405436638acc7c010349a69c3395f1a57c642dc62Ying Wang Unlike in ielr_compute_always_follows, I use a bitset for 12505436638acc7c010349a69c3395f1a57c642dc62Ying Wang edges rather than an array because it is possible that 12605436638acc7c010349a69c3395f1a57c642dc62Ying Wang multiple RHS's with the same first symbol could fit and thus 12705436638acc7c010349a69c3395f1a57c642dc62Ying Wang that we could end up with redundant edges. With the 12805436638acc7c010349a69c3395f1a57c642dc62Ying Wang possibility of redundant edges, it's hard to know ahead of 12905436638acc7c010349a69c3395f1a57c642dc62Ying Wang time how large to make such an array. Another possible 13005436638acc7c010349a69c3395f1a57c642dc62Ying Wang redundancy is that source and destination might be the same 13105436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto. Eliminating all these possible redundancies now might 13205436638acc7c010349a69c3395f1a57c642dc62Ying Wang possibly help performance a little. I have not proven any of 13305436638acc7c010349a69c3395f1a57c642dc62Ying Wang this, but I'm guessing the bitset shouldn't entail much of a 13405436638acc7c010349a69c3395f1a57c642dc62Ying Wang performance penalty, if any. */ 13505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (bitset_test (ritem_sees_lookahead_set, 13605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*rulep)->rhs - ritem)) 13705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 13805436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number source = 13905436638acc7c010349a69c3395f1a57c642dc62Ying Wang map_goto (from_state[i], 14005436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_number_as_symbol_number (*(*rulep)->rhs)); 14105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (i != source && !bitset_test (sources, source)) 14205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 14305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set (sources, source); 14405436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++nsources; 14505436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++(*edge_countsp)[source]; 14605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 14705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 14805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 14905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 15005436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (nsources == 0) 15105436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*edgesp)[i] = NULL; 15205436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 15305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 15405436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*edgesp)[i] = xnmalloc (nsources + 1, sizeof *(*edgesp)[i]); 15505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 15605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_iterator biter_source; 15705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_bindex source; 15805436638acc7c010349a69c3395f1a57c642dc62Ying Wang int j = 0; 15905436638acc7c010349a69c3395f1a57c642dc62Ying Wang BITSET_FOR_EACH (biter_source, sources, source, 0) 16005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*edgesp)[i][j++] = source; 16105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 16205436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*edgesp)[i][nsources] = END_NODE; 16305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 16405436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_zero (sources); 16505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 16605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_free (sources); 16705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 16805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 16905436638acc7c010349a69c3395f1a57c642dc62Ying Wang relation_transpose (edgesp, ngotos); 17005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 17105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (trace_flag & trace_ielr) 17205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 17305436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "internal_follow_edges:\n"); 17405436638acc7c010349a69c3395f1a57c642dc62Ying Wang relation_print (*edgesp, ngotos, stderr); 17505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 17605436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 17705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 17805436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 17905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre: 18005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c ritem_sees_lookahead_set was computed by 18105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_ritem_sees_lookahead_set. 18205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c internal_follow_edges was computed by 18305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_internal_follow_edges. 18405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post: 18505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c *follow_kernel_itemsp is a new \c bitsetv in which the number of rows 18605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * is \c ngotos and the number of columns is maximum number of kernel items 18705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * in any state. 18805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>(*follow_kernel_itemsp)[i][j]</tt> is set iff the follows of goto 18905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c i include the lookahead set of item \c j in the from state of goto 19005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c i. 19105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Thus, <tt>(*follow_kernel_itemsp)[i][j]</tt> is always unset if there is 19205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * no item \c j in the from state of goto \c i. 19305436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 19405436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 19505436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_follow_kernel_items (bitset ritem_sees_lookahead_set, 19605436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number **internal_follow_edges, 19705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv *follow_kernel_itemsp) 19805436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 19905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 20005436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t max_nitems = 0; 20105436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number i; 20205436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 20305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (states[i]->nitems > max_nitems) 20405436638acc7c010349a69c3395f1a57c642dc62Ying Wang max_nitems = states[i]->nitems; 20505436638acc7c010349a69c3395f1a57c642dc62Ying Wang *follow_kernel_itemsp = bitsetv_create (ngotos, max_nitems, BITSET_FIXED); 20605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 20705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 20805436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number i; 20905436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < ngotos; ++i) 21005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 21105436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t nitems = states[from_state[i]]->nitems; 21205436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_number *items = states[from_state[i]]->items; 21305436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t j; 21405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (j = 0; j < nitems; ++j) 21505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If this item has this goto and if all subsequent symbols in this 21605436638acc7c010349a69c3395f1a57c642dc62Ying Wang RHS (if any) are nullable nonterminals, then record this item as 21705436638acc7c010349a69c3395f1a57c642dc62Ying Wang one whose lookahead set is included in this goto's follows. */ 21805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (item_number_is_symbol_number (ritem[items[j]]) 21905436638acc7c010349a69c3395f1a57c642dc62Ying Wang && item_number_as_symbol_number (ritem[items[j]]) 22005436638acc7c010349a69c3395f1a57c642dc62Ying Wang == states[to_state[i]]->accessing_symbol 22105436638acc7c010349a69c3395f1a57c642dc62Ying Wang && bitset_test (ritem_sees_lookahead_set, items[j])) 22205436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set ((*follow_kernel_itemsp)[i], j); 22305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 22405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 22505436638acc7c010349a69c3395f1a57c642dc62Ying Wang relation_digraph (internal_follow_edges, ngotos, follow_kernel_itemsp); 22605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 22705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (trace_flag & trace_ielr) 22805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 22905436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "follow_kernel_items:\n"); 23005436638acc7c010349a69c3395f1a57c642dc62Ying Wang debug_bitsetv (*follow_kernel_itemsp); 23105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 23205436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 23305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 23405436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 23505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 23605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c *edgesp and \c edge_counts were computed by 23705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_internal_follow_edges. 23805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 23905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c *always_followsp is a new \c bitsetv with \c ngotos rows and 24005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ntokens columns. 24105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>(*always_followsp)[i][j]</tt> is set iff token \c j is an always 24205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * follow (that is, it's computed by internal and successor edges) of goto 24305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c i. 24405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Rows of \c *edgesp have been realloc'ed and extended to include 24505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * successor follow edges. \c edge_counts has not been updated. 24605436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 24705436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 24805436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_always_follows (goto_number ***edgesp, 24905436638acc7c010349a69c3395f1a57c642dc62Ying Wang int const edge_counts[], 25005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv *always_followsp) 25105436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 25205436638acc7c010349a69c3395f1a57c642dc62Ying Wang *always_followsp = bitsetv_create (ngotos, ntokens, BITSET_FIXED); 25305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 25405436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number *edge_array = xnmalloc (ngotos, sizeof *edge_array); 25505436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number i; 25605436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < ngotos; ++i) 25705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 25805436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number nedges = edge_counts[i]; 25905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 26005436638acc7c010349a69c3395f1a57c642dc62Ying Wang int j; 26105436638acc7c010349a69c3395f1a57c642dc62Ying Wang transitions *trans = states[to_state[i]]->transitions; 26205436638acc7c010349a69c3395f1a57c642dc62Ying Wang FOR_EACH_SHIFT (trans, j) 26305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set ((*always_followsp)[i], TRANSITION_SYMBOL (trans, j)); 26405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (; j < trans->num; ++j) 26505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 26605436638acc7c010349a69c3395f1a57c642dc62Ying Wang symbol_number sym = TRANSITION_SYMBOL (trans, j); 26705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (nullable[sym - ntokens]) 26805436638acc7c010349a69c3395f1a57c642dc62Ying Wang edge_array[nedges++] = map_goto (to_state[i], sym); 26905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 27005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 27105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (nedges - edge_counts[i]) 27205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 27305436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*edgesp)[i] = 27405436638acc7c010349a69c3395f1a57c642dc62Ying Wang xnrealloc ((*edgesp)[i], nedges + 1, sizeof *(*edgesp)[i]); 27505436638acc7c010349a69c3395f1a57c642dc62Ying Wang memcpy ((*edgesp)[i] + edge_counts[i], edge_array + edge_counts[i], 27605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (nedges - edge_counts[i]) * sizeof *(*edgesp)[i]); 27705436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*edgesp)[i][nedges] = END_NODE; 27805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 27905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 28005436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (edge_array); 28105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 28205436638acc7c010349a69c3395f1a57c642dc62Ying Wang relation_digraph (*edgesp, ngotos, always_followsp); 28305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 28405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (trace_flag & trace_ielr) 28505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 28605436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "always follow edges:\n"); 28705436638acc7c010349a69c3395f1a57c642dc62Ying Wang relation_print (*edgesp, ngotos, stderr); 28805436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "always_follows:\n"); 28905436638acc7c010349a69c3395f1a57c642dc62Ying Wang debug_bitsetv (*always_followsp); 29005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 29105436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 29205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 29305436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 29405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 29505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c result is a new array of size \c ::nstates. 29605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>result[i]</tt> is an array of pointers to the predecessor 29705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>state</tt>'s of state \c i. 29805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The last element of such an array is \c NULL. 29905436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 30005436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic state *** 30105436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_predecessors (void) 30205436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 30305436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number i; 30405436638acc7c010349a69c3395f1a57c642dc62Ying Wang int *predecessor_counts = xnmalloc (nstates, sizeof *predecessor_counts); 30505436638acc7c010349a69c3395f1a57c642dc62Ying Wang state ***result = xnmalloc (nstates, sizeof *result); 30605436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 30705436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessor_counts[i] = 0; 30805436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 30905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 31005436638acc7c010349a69c3395f1a57c642dc62Ying Wang int j; 31105436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (j = 0; j < states[i]->transitions->num; ++j) 31205436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++predecessor_counts[states[i]->transitions->states[j]->number]; 31305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 31405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 31505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 31605436638acc7c010349a69c3395f1a57c642dc62Ying Wang result[i] = xnmalloc (predecessor_counts[i]+1, sizeof *result[i]); 31705436638acc7c010349a69c3395f1a57c642dc62Ying Wang result[i][predecessor_counts[i]] = NULL; 31805436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessor_counts[i] = 0; 31905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 32005436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 32105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 32205436638acc7c010349a69c3395f1a57c642dc62Ying Wang int j; 32305436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (j = 0; j < states[i]->transitions->num; ++j) 32405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 32505436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number k = states[i]->transitions->states[j]->number; 32605436638acc7c010349a69c3395f1a57c642dc62Ying Wang result[k][predecessor_counts[k]++] = states[i]; 32705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 32805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 32905436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (predecessor_counts); 33005436638acc7c010349a69c3395f1a57c642dc62Ying Wang return result; 33105436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 33205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 33305436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 33405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 33505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c *follow_kernel_itemsp and \c *always_followsp were computed by 33605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_follow_kernel_items and 33705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_always_follows. 33805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Iff <tt>predecessorsp != NULL</tt>, then \c *predecessorsp was computed 33905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * by \c ielr_compute_predecessors. 34005436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 34105436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 34205436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_auxiliary_tables (bitsetv *follow_kernel_itemsp, 34305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv *always_followsp, 34405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state ****predecessorsp) 34505436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 34605436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number **edges; 34705436638acc7c010349a69c3395f1a57c642dc62Ying Wang int *edge_counts; 34805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 34905436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset ritem_sees_lookahead_set = ielr_compute_ritem_sees_lookahead_set (); 35005436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_internal_follow_edges (ritem_sees_lookahead_set, 35105436638acc7c010349a69c3395f1a57c642dc62Ying Wang &edges, &edge_counts); 35205436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_follow_kernel_items (ritem_sees_lookahead_set, edges, 35305436638acc7c010349a69c3395f1a57c642dc62Ying Wang follow_kernel_itemsp); 35405436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_free (ritem_sees_lookahead_set); 35505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 35605436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_always_follows (&edges, edge_counts, always_followsp); 35705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 35805436638acc7c010349a69c3395f1a57c642dc62Ying Wang int i; 35905436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < ngotos; ++i) 36005436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (edges[i]); 36105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 36205436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (edges); 36305436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (edge_counts); 36405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (predecessorsp) 36505436638acc7c010349a69c3395f1a57c642dc62Ying Wang *predecessorsp = ielr_compute_predecessors (); 36605436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 36705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 36805436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 36905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \note 37005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - FIXME: It might be an interesting experiment to compare the space and 37105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * time efficiency of computing \c item_lookahead_sets either: 37205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Fully up front. 37305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Just-in-time, as implemented below. 37405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Not at all. That is, just let annotations continue even when 37505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * unnecessary. 37605436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 37705436638acc7c010349a69c3395f1a57c642dc62Ying Wangbool 37805436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_item_has_lookahead (state *s, symbol_number lhs, size_t item, 37905436638acc7c010349a69c3395f1a57c642dc62Ying Wang symbol_number lookahead, state ***predecessors, 38005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset **item_lookahead_sets) 38105436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 38205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!item_lookahead_sets[s->number]) 38305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 38405436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 38505436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets[s->number] = 38605436638acc7c010349a69c3395f1a57c642dc62Ying Wang xnmalloc (s->nitems, sizeof item_lookahead_sets[s->number][0]); 38705436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < s->nitems; ++i) 38805436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets[s->number][i] = NULL; 38905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 39005436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!item_lookahead_sets[s->number][item]) 39105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 39205436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets[s->number][item] = 39305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_create (ntokens, BITSET_FIXED); 39405436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If this kernel item is the beginning of a RHS, it must be the kernel 39505436638acc7c010349a69c3395f1a57c642dc62Ying Wang item in the start state, and so its LHS has no follows and no goto to 39605436638acc7c010349a69c3395f1a57c642dc62Ying Wang check. If, instead, this kernel item is the successor of the start 39705436638acc7c010349a69c3395f1a57c642dc62Ying Wang state's kernel item, there are still no follows and no goto. This 39805436638acc7c010349a69c3395f1a57c642dc62Ying Wang situation is fortunate because we want to avoid the - 2 below in both 39905436638acc7c010349a69c3395f1a57c642dc62Ying Wang cases. 40005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 40105436638acc7c010349a69c3395f1a57c642dc62Ying Wang Actually, IELR(1) should never invoke this function for either of 40205436638acc7c010349a69c3395f1a57c642dc62Ying Wang those cases because (1) follow_kernel_items will never reference a 40305436638acc7c010349a69c3395f1a57c642dc62Ying Wang kernel item for this RHS because the end token blocks sight of the 40405436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookahead set from the RHS's only nonterminal, and (2) no reduction 40505436638acc7c010349a69c3395f1a57c642dc62Ying Wang has a lookback dependency on this lookahead set. Nevertheless, I 40605436638acc7c010349a69c3395f1a57c642dc62Ying Wang didn't change this test to an aver just in case the usage of this 40705436638acc7c010349a69c3395f1a57c642dc62Ying Wang function evolves to need those two cases. In both cases, the current 40805436638acc7c010349a69c3395f1a57c642dc62Ying Wang implementation returns the right result. */ 40905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (s->items[item] > 1) 41005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 41105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If the LHS symbol of this item isn't known (because this is a 41205436638acc7c010349a69c3395f1a57c642dc62Ying Wang top-level invocation), go get it. */ 41305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!lhs) 41405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 41505436638acc7c010349a69c3395f1a57c642dc62Ying Wang unsigned int i; 41605436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = s->items[item]; 41705436638acc7c010349a69c3395f1a57c642dc62Ying Wang !item_number_is_rule_number (ritem[i]); 41805436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++i) 41905436638acc7c010349a69c3395f1a57c642dc62Ying Wang ; 42005436638acc7c010349a69c3395f1a57c642dc62Ying Wang lhs = rules[item_number_as_rule_number (ritem[i])].lhs->number; 42105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 42205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If this kernel item is next to the beginning of the RHS, then 42305436638acc7c010349a69c3395f1a57c642dc62Ying Wang check all predecessors' goto follows for the LHS. */ 42405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (item_number_is_rule_number (ritem[s->items[item] - 2])) 42505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 42605436638acc7c010349a69c3395f1a57c642dc62Ying Wang state **predecessor; 42705436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (lhs != accept->number); 42805436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (predecessor = predecessors[s->number]; 42905436638acc7c010349a69c3395f1a57c642dc62Ying Wang *predecessor; 43005436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++predecessor) 43105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_or (item_lookahead_sets[s->number][item], 43205436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets[s->number][item], 43305436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_follows[map_goto ((*predecessor)->number, 43405436638acc7c010349a69c3395f1a57c642dc62Ying Wang lhs)]); 43505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 43605436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If this kernel item is later in the RHS, then check all 43705436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessor items' lookahead sets. */ 43805436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 43905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 44005436638acc7c010349a69c3395f1a57c642dc62Ying Wang state **predecessor; 44105436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (predecessor = predecessors[s->number]; 44205436638acc7c010349a69c3395f1a57c642dc62Ying Wang *predecessor; 44305436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++predecessor) 44405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 44505436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t predecessor_item; 44605436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (predecessor_item = 0; 44705436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessor_item < (*predecessor)->nitems; 44805436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++predecessor_item) 44905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if ((*predecessor)->items[predecessor_item] 45005436638acc7c010349a69c3395f1a57c642dc62Ying Wang == s->items[item] - 1) 45105436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 45205436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (predecessor_item != (*predecessor)->nitems); 45305436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_item_has_lookahead (*predecessor, lhs, 45405436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessor_item, 0 /*irrelevant*/, 45505436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessors, item_lookahead_sets); 45605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_or (item_lookahead_sets[s->number][item], 45705436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets[s->number][item], 45805436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets[(*predecessor)->number] 45905436638acc7c010349a69c3395f1a57c642dc62Ying Wang [predecessor_item]); 46005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 46105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 46205436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 46305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 46405436638acc7c010349a69c3395f1a57c642dc62Ying Wang return bitset_test (item_lookahead_sets[s->number][item], lookahead); 46505436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 46605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 46705436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 46805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 46905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c follow_kernel_items, \c always_follows, and \c predecessors 47005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * were computed by \c ielr_compute_auxiliary_tables. 47105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 47205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Each of <tt>*inadequacy_listsp</tt> and <tt>*annotation_listsp</tt> 47305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * points to a new array of size \c ::nstates. 47405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - For <tt>0 <= i < ::nstates</tt>: 47505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>(*inadequacy_listsp)[i]</tt> contains the \c InadequacyList head 47605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * node for <tt>states[i]</tt>. 47705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>(*annotation_listsp)[i]</tt> contains the \c AnnotationList head 47805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * node for <tt>states[i]</tt>. 47905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>*max_annotationsp</tt> is the maximum number of annotations per 48005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * state. 48105436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 48205436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 48305436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_annotation_lists (bitsetv follow_kernel_items, 48405436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv always_follows, state ***predecessors, 48505436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationIndex *max_annotationsp, 48605436638acc7c010349a69c3395f1a57c642dc62Ying Wang InadequacyList ***inadequacy_listsp, 48705436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList ***annotation_listsp, 48805436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct obstack *annotations_obstackp) 48905436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 49005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset **item_lookahead_sets = 49105436638acc7c010349a69c3395f1a57c642dc62Ying Wang xnmalloc (nstates, sizeof *item_lookahead_sets); 49205436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationIndex *annotation_counts = 49305436638acc7c010349a69c3395f1a57c642dc62Ying Wang xnmalloc (nstates, sizeof *annotation_counts); 49405436638acc7c010349a69c3395f1a57c642dc62Ying Wang ContributionIndex max_contributions = 0; 49505436638acc7c010349a69c3395f1a57c642dc62Ying Wang unsigned int total_annotations = 0; 49605436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number i; 49705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 49805436638acc7c010349a69c3395f1a57c642dc62Ying Wang *inadequacy_listsp = xnmalloc (nstates, sizeof **inadequacy_listsp); 49905436638acc7c010349a69c3395f1a57c642dc62Ying Wang *annotation_listsp = xnmalloc (nstates, sizeof **annotation_listsp); 50005436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 50105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 50205436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets[i] = NULL; 50305436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*inadequacy_listsp)[i] = NULL; 50405436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*annotation_listsp)[i] = NULL; 50505436638acc7c010349a69c3395f1a57c642dc62Ying Wang annotation_counts[i] = 0; 50605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 50705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 50805436638acc7c010349a69c3395f1a57c642dc62Ying Wang InadequacyListNodeCount inadequacy_list_node_count = 0; 50905436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 51005436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList__compute_from_inadequacies ( 51105436638acc7c010349a69c3395f1a57c642dc62Ying Wang states[i], follow_kernel_items, always_follows, predecessors, 51205436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_lookahead_sets, *inadequacy_listsp, *annotation_listsp, 51305436638acc7c010349a69c3395f1a57c642dc62Ying Wang annotation_counts, &max_contributions, annotations_obstackp, 51405436638acc7c010349a69c3395f1a57c642dc62Ying Wang &inadequacy_list_node_count); 51505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 51605436638acc7c010349a69c3395f1a57c642dc62Ying Wang *max_annotationsp = 0; 51705436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 51805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 51905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (annotation_counts[i] > *max_annotationsp) 52005436638acc7c010349a69c3395f1a57c642dc62Ying Wang *max_annotationsp = annotation_counts[i]; 52105436638acc7c010349a69c3395f1a57c642dc62Ying Wang total_annotations += annotation_counts[i]; 52205436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 52305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (trace_flag & trace_ielr) 52405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 52505436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 52605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 52705436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "Inadequacy annotations for state %d:\n", i); 52805436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList__debug ((*annotation_listsp)[i], 52905436638acc7c010349a69c3395f1a57c642dc62Ying Wang states[i]->nitems, 2); 53005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 53105436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "Number of LR(0)/LALR(1) states: %d\n", nstates); 53205436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "Average number of annotations per state: %f\n", 53305436638acc7c010349a69c3395f1a57c642dc62Ying Wang (float)total_annotations/nstates); 53405436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "Max number of annotations per state: %d\n", 53505436638acc7c010349a69c3395f1a57c642dc62Ying Wang *max_annotationsp); 53605436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (stderr, "Max number of contributions per annotation: %d\n", 53705436638acc7c010349a69c3395f1a57c642dc62Ying Wang max_contributions); 53805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 53905436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 54005436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (item_lookahead_sets[i]) 54105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 54205436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t j; 54305436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (j = 0; j < states[i]->nitems; ++j) 54405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (item_lookahead_sets[i][j]) 54505436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_free (item_lookahead_sets[i][j]); 54605436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (item_lookahead_sets[i]); 54705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 54805436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (item_lookahead_sets); 54905436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (annotation_counts); 55005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 55105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 55205436638acc7c010349a69c3395f1a57c642dc62Ying Wangtypedef struct state_list { 55305436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct state_list *next; 55405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state *state; 55505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /** Has this state been recomputed as a successor of another state? */ 55605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool recomputedAsSuccessor; 55705436638acc7c010349a69c3395f1a57c642dc62Ying Wang /** 55805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c NULL iff all lookahead sets are empty. <tt>lookaheads[i] = NULL</tt> 55905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * iff the lookahead set on item \c i is empty. 56005436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 56105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset *lookaheads; 56205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /** 56305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * nextIsocore is the next state in a circularly linked-list of all states 56405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * with the same core. The one originally computed by generate_states in 56505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * LR0.c is lr0Isocore. 56605436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 56705436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct state_list *lr0Isocore; 56805436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct state_list *nextIsocore; 56905436638acc7c010349a69c3395f1a57c642dc62Ying Wang} state_list; 57005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 57105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 57205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 57305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c follow_kernel_items and \c always_follows were computed by 57405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_auxiliary_tables. 57505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>n->class = nterm_sym</tt>. 57605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 57705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c follow_set contains the follow set for the goto on nonterminal \c n 57805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * in state \c s based on the lookaheads stored in <tt>s->lookaheads</tt>. 57905436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 58005436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 58105436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_goto_follow_set (bitsetv follow_kernel_items, 58205436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv always_follows, state_list *s, 58305436638acc7c010349a69c3395f1a57c642dc62Ying Wang symbol *n, bitset follow_set) 58405436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 58505436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number n_goto = map_goto (s->lr0Isocore->state->number, n->number); 58605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_copy (follow_set, always_follows[n_goto]); 58705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (s->lookaheads) 58805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 58905436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_iterator biter_item; 59005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_bindex item; 59105436638acc7c010349a69c3395f1a57c642dc62Ying Wang BITSET_FOR_EACH (biter_item, follow_kernel_items[n_goto], item, 0) 59205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (s->lookaheads[item]) 59305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_or (follow_set, follow_set, s->lookaheads[item]); 59405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 59505436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 59605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 59705436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 59805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 59905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c follow_kernel_items and \c always_follows were computed by 60005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_auxiliary_tables. 60105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c lookahead_filter was computed by 60205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c AnnotationList__computeLookaheadFilter for the original LR(0) isocore 60305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * of \c t. 60405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The number of rows in \c lookaheads is at least the number of items in 60505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c t, and the number of columns is \c ::ntokens. 60605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 60705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>lookaheads[i][j]</tt> is set iff both: 60805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>lookahead_filter[i][j]</tt> is set. 60905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The isocore of \c t that will be the transition successor of \c s will 61005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * inherit from \c s token \c j into the lookahead set of item \c i. 61105436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 61205436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 61305436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_lookaheads (bitsetv follow_kernel_items, bitsetv always_follows, 61405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *s, state *t, bitsetv lookahead_filter, 61505436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv lookaheads) 61605436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 61705436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t s_item = 0; 61805436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t t_item; 61905436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_zero (lookaheads); 62005436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (t_item = 0; t_item < t->nitems; ++t_item) 62105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 62205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If this kernel item is the beginning of a RHS, it must be the 62305436638acc7c010349a69c3395f1a57c642dc62Ying Wang kernel item in the start state, but t is supposed to be a successor 62405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state. If, instead, this kernel item is the successor of the start 62505436638acc7c010349a69c3395f1a57c642dc62Ying Wang state's kernel item, the lookahead set is empty. This second case is 62605436638acc7c010349a69c3395f1a57c642dc62Ying Wang a special case to avoid the - 2 below, but the next successor can be 62705436638acc7c010349a69c3395f1a57c642dc62Ying Wang handled fine without special casing it. */ 62805436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (t->items[t_item] != 0); 62905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (t->items[t_item] > 1 63005436638acc7c010349a69c3395f1a57c642dc62Ying Wang && !bitset_empty_p (lookahead_filter[t_item])) 63105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 63205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (item_number_is_rule_number (ritem[t->items[t_item] - 2])) 63305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 63405436638acc7c010349a69c3395f1a57c642dc62Ying Wang unsigned int rule_item; 63505436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (rule_item = t->items[t_item]; 63605436638acc7c010349a69c3395f1a57c642dc62Ying Wang !item_number_is_rule_number (ritem[rule_item]); 63705436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++rule_item) 63805436638acc7c010349a69c3395f1a57c642dc62Ying Wang ; 63905436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_goto_follow_set ( 64005436638acc7c010349a69c3395f1a57c642dc62Ying Wang follow_kernel_items, always_follows, s, 64105436638acc7c010349a69c3395f1a57c642dc62Ying Wang rules[item_number_as_rule_number (ritem[rule_item])].lhs, 64205436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads[t_item]); 64305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 64405436638acc7c010349a69c3395f1a57c642dc62Ying Wang else if (s->lookaheads) 64505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 64605436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* We don't have to start the s item search at the beginning 64705436638acc7c010349a69c3395f1a57c642dc62Ying Wang every time because items from both states are sorted by their 64805436638acc7c010349a69c3395f1a57c642dc62Ying Wang indices in ritem. */ 64905436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (; s_item < s->state->nitems; ++s_item) 65005436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (s->state->items[s_item] == t->items[t_item] - 1) 65105436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 65205436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (s_item != s->state->nitems); 65305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (s->lookaheads[s_item]) 65405436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_copy (lookaheads[t_item], s->lookaheads[s_item]); 65505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 65605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_and (lookaheads[t_item], 65705436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads[t_item], lookahead_filter[t_item]); 65805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 65905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 66005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 66105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 66205436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 66305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 66405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c follow_kernel_items and \c always_follows were computed by 66505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_auxiliary_tables. 66605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Either: 66705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>annotation_lists = NULL</tt> and all bits in work2 are set. 66805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c annotation_lists was computed by \c ielr_compute_annotation_lists. 66905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The number of rows in each of \c lookaheads and \c work2 is the maximum 67005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * number of items in any state. The number of columns in each is 67105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ::ntokens. 67205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c lookaheads was computed by \c ielr_compute_lookaheads for \c t. 67305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c ::nstates is the total number of states, some not yet fully computed, 67405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * in the list ending at \c *last_statep. It is at least the number of 67505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * original LR(0) states. 67605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - The size of \c work1 is at least the number of annotations for the LR(0) 67705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * isocore of \c t. 67805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 67905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Either: 68005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - In the case that <tt>annotation_lists != NULL</tt>, 68105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>lookaheads \@pre</tt> was merged with some isocore of \c t if 68205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * permitted by the annotations for the original LR(0) isocore of \c t. 68305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * If this changed the lookaheads in that isocore, those changes were 68405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * propagated to all already computed transition successors recursively 68505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * possibly resulting in the splitting of some of those successors. 68605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - In the case that <tt>annotation_lists = NULL</tt>, 68705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>lookaheads \@pre</tt> was merged with some isocore of \c t if the 68805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * isocore's lookahead sets were identical to those specified by 68905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>lookaheads \@pre</tt>. 69005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - If no such merge was permitted, a new isocore of \c t containing 69105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>lookaheads \@pre</tt> was appended to the state list whose 69205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * previous tail was <tt>*last_statep \@pre</tt> and \c ::nstates was 69305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * incremented. It was also appended to \c t's isocore list. 69405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>*tp</tt> = the isocore of \c t into which 69505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>lookaheads \@pre</tt> was placed/merged. 69605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c lookaheads, \c work1, and \c work2 may have been altered. 69705436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 69805436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 69905436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_compute_state (bitsetv follow_kernel_items, bitsetv always_follows, 70005436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList **annotation_lists, state *t, 70105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv lookaheads, state_list **last_statep, 70205436638acc7c010349a69c3395f1a57c642dc62Ying Wang ContributionIndex work1[], bitsetv work2, state **tp) 70305436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 70405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *lr0_isocore = t->state_list->lr0Isocore; 70505436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list **this_isocorep; 70605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool has_lookaheads; 70705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 70805436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Determine whether there's an isocore of t with which these lookaheads can 70905436638acc7c010349a69c3395f1a57c642dc62Ying Wang be merged. */ 71005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 71105436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationIndex ai; 71205436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList *a; 71305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (annotation_lists) 71405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (ai = 0, a = annotation_lists[lr0_isocore->state->number]; 71505436638acc7c010349a69c3395f1a57c642dc62Ying Wang a; 71605436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++ai, a = a->next) 71705436638acc7c010349a69c3395f1a57c642dc62Ying Wang work1[ai] = 71805436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList__computeDominantContribution ( 71905436638acc7c010349a69c3395f1a57c642dc62Ying Wang a, lr0_isocore->state->nitems, lookaheads, false); 72005436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (this_isocorep = &t->state_list; 72105436638acc7c010349a69c3395f1a57c642dc62Ying Wang this_isocorep == &t->state_list || *this_isocorep != t->state_list; 72205436638acc7c010349a69c3395f1a57c642dc62Ying Wang this_isocorep = &(*this_isocorep)->nextIsocore) 72305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 72405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!(*this_isocorep)->recomputedAsSuccessor) 72505436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 72605436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (annotation_lists) 72705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 72805436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (ai = 0, a = annotation_lists[lr0_isocore->state->number]; 72905436638acc7c010349a69c3395f1a57c642dc62Ying Wang a; 73005436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++ai, a = a->next) 73105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 73205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (work1[ai] != ContributionIndex__none) 73305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 73405436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* This isocore compatibility test depends on the fact 73505436638acc7c010349a69c3395f1a57c642dc62Ying Wang that, if the dominant contributions are the same for the 73605436638acc7c010349a69c3395f1a57c642dc62Ying Wang two isocores, then merging their lookahead sets will not 73705436638acc7c010349a69c3395f1a57c642dc62Ying Wang produce a state with a different dominant contribution. 73805436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 73905436638acc7c010349a69c3395f1a57c642dc62Ying Wang ContributionIndex ci = 74005436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList__computeDominantContribution ( 74105436638acc7c010349a69c3395f1a57c642dc62Ying Wang a, lr0_isocore->state->nitems, 74205436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*this_isocorep)->lookaheads, false); 74305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (ci != ContributionIndex__none && work1[ai] != ci) 74405436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 74505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 74605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 74705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!a) 74805436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 74905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 75005436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 75105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 75205436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 75305436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < t->nitems; ++i) 75405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 75505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!(*this_isocorep)->lookaheads 75605436638acc7c010349a69c3395f1a57c642dc62Ying Wang || !(*this_isocorep)->lookaheads[i]) 75705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 75805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!bitset_empty_p (lookaheads[i])) 75905436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 76005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 76105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* bitset_equal_p uses the size of the first argument, 76205436638acc7c010349a69c3395f1a57c642dc62Ying Wang so lookaheads[i] must be the second argument. */ 76305436638acc7c010349a69c3395f1a57c642dc62Ying Wang else if (!bitset_equal_p ((*this_isocorep)->lookaheads[i], 76405436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads[i])) 76505436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 76605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 76705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (i == t->nitems) 76805436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 76905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 77005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 77105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 77205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 77305436638acc7c010349a69c3395f1a57c642dc62Ying Wang has_lookaheads = false; 77405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 77505436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 77605436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < lr0_isocore->state->nitems; ++i) 77705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!bitset_empty_p (lookaheads[i])) 77805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 77905436638acc7c010349a69c3395f1a57c642dc62Ying Wang has_lookaheads = true; 78005436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 78105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 78205436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 78305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 78405436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Merge with an existing isocore. */ 78505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (this_isocorep == &t->state_list || *this_isocorep != t->state_list) 78605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 78705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool new_lookaheads = false; 78805436638acc7c010349a69c3395f1a57c642dc62Ying Wang *tp = (*this_isocorep)->state; 78905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 79005436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Merge lookaheads into the state and record whether any of them are 79105436638acc7c010349a69c3395f1a57c642dc62Ying Wang actually new. */ 79205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (has_lookaheads) 79305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 79405436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 79505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!(*this_isocorep)->lookaheads) 79605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 79705436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*this_isocorep)->lookaheads = 79805436638acc7c010349a69c3395f1a57c642dc62Ying Wang xnmalloc (t->nitems, sizeof (*this_isocorep)->lookaheads); 79905436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < t->nitems; ++i) 80005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*this_isocorep)->lookaheads[i] = NULL; 80105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 80205436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < t->nitems; ++i) 80305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!bitset_empty_p (lookaheads[i])) 80405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 80505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!(*this_isocorep)->lookaheads[i]) 80605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*this_isocorep)->lookaheads[i] = 80705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_create (ntokens, BITSET_FIXED); 80805436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_andn (lookaheads[i], 80905436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads[i], (*this_isocorep)->lookaheads[i]); 81005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_or ((*this_isocorep)->lookaheads[i], 81105436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads[i], (*this_isocorep)->lookaheads[i]); 81205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!bitset_empty_p (lookaheads[i])) 81305436638acc7c010349a69c3395f1a57c642dc62Ying Wang new_lookaheads = true; 81405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 81505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 81605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 81705436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If new lookaheads were merged, propagate those lookaheads to the 81805436638acc7c010349a69c3395f1a57c642dc62Ying Wang successors, possibly splitting them. If *tp is being recomputed for 81905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the first time, this isn't necessary because the main 82005436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_split_states loop will handle the successors later. */ 82105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!(*this_isocorep)->recomputedAsSuccessor) 82205436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*this_isocorep)->recomputedAsSuccessor = true; 82305436638acc7c010349a69c3395f1a57c642dc62Ying Wang else if (new_lookaheads) 82405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 82505436638acc7c010349a69c3395f1a57c642dc62Ying Wang int i; 82605436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* When merging demands identical lookahead sets, it is impossible to 82705436638acc7c010349a69c3395f1a57c642dc62Ying Wang merge new lookaheads. */ 82805436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (annotation_lists); 82905436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < (*tp)->transitions->num; ++i) 83005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 83105436638acc7c010349a69c3395f1a57c642dc62Ying Wang state *t2 = (*tp)->transitions->states[i]; 83205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* At any time, there's at most one state for which we have so 83305436638acc7c010349a69c3395f1a57c642dc62Ying Wang far initially recomputed only some of its successors in the 83405436638acc7c010349a69c3395f1a57c642dc62Ying Wang main ielr_split_states loop. Because we recompute successors 83505436638acc7c010349a69c3395f1a57c642dc62Ying Wang in order, we can just stop at the first such successor. Of 83605436638acc7c010349a69c3395f1a57c642dc62Ying Wang course, *tp might be a state some of whose successors have 83705436638acc7c010349a69c3395f1a57c642dc62Ying Wang been recomputed as successors of other states rather than as 83805436638acc7c010349a69c3395f1a57c642dc62Ying Wang successors of *tp. It's fine if we go ahead and propagate to 83905436638acc7c010349a69c3395f1a57c642dc62Ying Wang some of those. We'll propagate to them again (but stop when 84005436638acc7c010349a69c3395f1a57c642dc62Ying Wang we see nothing changes) and to the others when we reach *tp in 84105436638acc7c010349a69c3395f1a57c642dc62Ying Wang the main ielr_split_states loop later. */ 84205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!t2->state_list->recomputedAsSuccessor) 84305436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 84405436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList__computeLookaheadFilter ( 84505436638acc7c010349a69c3395f1a57c642dc62Ying Wang annotation_lists[t2->state_list->lr0Isocore->state->number], 84605436638acc7c010349a69c3395f1a57c642dc62Ying Wang t2->nitems, work2); 84705436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_lookaheads (follow_kernel_items, always_follows, 84805436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*this_isocorep), t2, work2, 84905436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads); 85005436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* FIXME: If splitting t2 here, it's possible that lookaheads 85105436638acc7c010349a69c3395f1a57c642dc62Ying Wang that had already propagated from *tp to t2 will be left in t2 85205436638acc7c010349a69c3395f1a57c642dc62Ying Wang after *tp has been removed as t2's predecessor: 85305436638acc7c010349a69c3395f1a57c642dc62Ying Wang - We're going to recompute all lookaheads in phase 4, so these 85405436638acc7c010349a69c3395f1a57c642dc62Ying Wang extra lookaheads won't appear in the final parser table. 85505436638acc7c010349a69c3395f1a57c642dc62Ying Wang - If t2 has just one annotation, then these extra lookaheads 85605436638acc7c010349a69c3395f1a57c642dc62Ying Wang cannot alter the dominating contribution to the associated 85705436638acc7c010349a69c3395f1a57c642dc62Ying Wang inadequacy and thus cannot needlessly prevent a future merge 85805436638acc7c010349a69c3395f1a57c642dc62Ying Wang of some new state with t2. We can be sure of this because: 85905436638acc7c010349a69c3395f1a57c642dc62Ying Wang - The fact that we're splitting t2 now means that some 86005436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessors (at least one) other than *tp must be 86105436638acc7c010349a69c3395f1a57c642dc62Ying Wang propagating contributions to t2. 86205436638acc7c010349a69c3395f1a57c642dc62Ying Wang - The fact that t2 was merged in the first place means that, 86305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if *tp propagated any contributions, the dominating 86405436638acc7c010349a69c3395f1a57c642dc62Ying Wang contribution must be the same as that from those other 86505436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessors. 86605436638acc7c010349a69c3395f1a57c642dc62Ying Wang - Thus, if some new state to be merged with t2 in the future 86705436638acc7c010349a69c3395f1a57c642dc62Ying Wang proves to be compatible with the contributions propagated 86805436638acc7c010349a69c3395f1a57c642dc62Ying Wang by the other predecessors, it will also be compatible with 86905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the contributions made by the extra lookaheads left behind 87005436638acc7c010349a69c3395f1a57c642dc62Ying Wang by *tp. 87105436638acc7c010349a69c3395f1a57c642dc62Ying Wang - However, if t2 has more than one annotation and these extra 87205436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads contribute to one of their inadequacies, it's 87305436638acc7c010349a69c3395f1a57c642dc62Ying Wang possible these extra lookaheads may needlessly prevent a 87405436638acc7c010349a69c3395f1a57c642dc62Ying Wang future merge with t2. For example: 87505436638acc7c010349a69c3395f1a57c642dc62Ying Wang - Let's say there's an inadequacy A that makes the split 87605436638acc7c010349a69c3395f1a57c642dc62Ying Wang necessary as follows: 87705436638acc7c010349a69c3395f1a57c642dc62Ying Wang - There's currently just one other predecessor and it 87805436638acc7c010349a69c3395f1a57c642dc62Ying Wang propagates to t2 some contributions to inadequacy A. 87905436638acc7c010349a69c3395f1a57c642dc62Ying Wang - The new lookaheads that we were attempting to propagate 88005436638acc7c010349a69c3395f1a57c642dc62Ying Wang from *tp to t2 made contributions to inadequacy A with a 88105436638acc7c010349a69c3395f1a57c642dc62Ying Wang different dominating contribution than those from that 88205436638acc7c010349a69c3395f1a57c642dc62Ying Wang other predecessor. 88305436638acc7c010349a69c3395f1a57c642dc62Ying Wang - The extra lookaheads either make no contribution to 88405436638acc7c010349a69c3395f1a57c642dc62Ying Wang inadequacy A or have the same dominating contribution as 88505436638acc7c010349a69c3395f1a57c642dc62Ying Wang the contributions from the other predecessor. Either 88605436638acc7c010349a69c3395f1a57c642dc62Ying Wang way, as explained above, they can't prevent a future 88705436638acc7c010349a69c3395f1a57c642dc62Ying Wang merge. 88805436638acc7c010349a69c3395f1a57c642dc62Ying Wang - Let's say there's an inadequacy B that causes the trouble 88905436638acc7c010349a69c3395f1a57c642dc62Ying Wang with future merges as follows: 89005436638acc7c010349a69c3395f1a57c642dc62Ying Wang - The extra lookaheads make contributions to inadequacy B. 89105436638acc7c010349a69c3395f1a57c642dc62Ying Wang - Those extra contributions did not prevent the original 89205436638acc7c010349a69c3395f1a57c642dc62Ying Wang merge to create t2 because the other predecessor 89305436638acc7c010349a69c3395f1a57c642dc62Ying Wang propagates to t2 no contributions to inadequacy B. 89405436638acc7c010349a69c3395f1a57c642dc62Ying Wang - Thus, those extra contributions may prevent a future 89505436638acc7c010349a69c3395f1a57c642dc62Ying Wang merge with t2 even though the merge would be fine if *tp 89605436638acc7c010349a69c3395f1a57c642dc62Ying Wang had not left them behind. 89705436638acc7c010349a69c3395f1a57c642dc62Ying Wang - Is the latter case common enough to worry about? 89805436638acc7c010349a69c3395f1a57c642dc62Ying Wang - Perhaps we should track all predecessors and iterate them 89905436638acc7c010349a69c3395f1a57c642dc62Ying Wang now to recreate t2 without those extra lookaheads. */ 90005436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_state (follow_kernel_items, always_follows, 90105436638acc7c010349a69c3395f1a57c642dc62Ying Wang annotation_lists, t2, lookaheads, 90205436638acc7c010349a69c3395f1a57c642dc62Ying Wang last_statep, work1, work2, 90305436638acc7c010349a69c3395f1a57c642dc62Ying Wang &(*tp)->transitions->states[i]); 90405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 90505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 90605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 90705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 90805436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Create a new isocore. */ 90905436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 91005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 91105436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *old_isocore = *this_isocorep; 91205436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->next = *this_isocorep = xmalloc (sizeof **last_statep); 91305436638acc7c010349a69c3395f1a57c642dc62Ying Wang *last_statep = *this_isocorep; 91405436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->state = *tp = state_new_isocore (t); 91505436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*tp)->state_list = *last_statep; 91605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->recomputedAsSuccessor = true; 91705436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->next = NULL; 91805436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->lookaheads = NULL; 91905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (has_lookaheads) 92005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 92105436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 92205436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->lookaheads = 92305436638acc7c010349a69c3395f1a57c642dc62Ying Wang xnmalloc (t->nitems, sizeof (*last_statep)->lookaheads); 92405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < t->nitems; ++i) 92505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 92605436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (bitset_empty_p (lookaheads[i])) 92705436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->lookaheads[i] = NULL; 92805436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 92905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 93005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->lookaheads[i] = 93105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_create (ntokens, BITSET_FIXED); 93205436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_copy ((*last_statep)->lookaheads[i], lookaheads[i]); 93305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 93405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 93505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 93605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->lr0Isocore = lr0_isocore; 93705436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*last_statep)->nextIsocore = old_isocore; 93805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 93905436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 94005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 94105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/** 94205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \pre 94305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c follow_kernel_items and \c always_follows were computed by 94405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_auxiliary_tables. 94505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - Either: 94605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - <tt>annotation_lists = NULL</tt> and <tt>max_annotations=0</tt>. 94705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c annotation_lists and \c max_annotations were computed by 94805436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \c ielr_compute_annotation_lists. 94905436638acc7c010349a69c3395f1a57c642dc62Ying Wang * \post 95005436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - \c ::states is of size \c ::nstates (which might be greater than 95105436638acc7c010349a69c3395f1a57c642dc62Ying Wang * <tt>::nstates \@pre</tt>) and no longer contains any LR(1)-relative 95205436638acc7c010349a69c3395f1a57c642dc62Ying Wang * inadequacy. \c annotation_lists was used to determine state 95305436638acc7c010349a69c3395f1a57c642dc62Ying Wang * compatibility or, if <tt>annotation_lists = NULL</tt>, the canonical 95405436638acc7c010349a69c3395f1a57c642dc62Ying Wang * LR(1) state compatibility test was used. 95505436638acc7c010349a69c3395f1a57c642dc62Ying Wang * - If <tt>annotation_lists = NULL</tt>, reduction lookahead sets were 95605436638acc7c010349a69c3395f1a57c642dc62Ying Wang * computed in all states. TV_IELR_PHASE4 was pushed while they were 95705436638acc7c010349a69c3395f1a57c642dc62Ying Wang * computed from item lookahead sets. 95805436638acc7c010349a69c3395f1a57c642dc62Ying Wang */ 95905436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 96005436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr_split_states (bitsetv follow_kernel_items, bitsetv always_follows, 96105436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList **annotation_lists, 96205436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationIndex max_annotations) 96305436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 96405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *first_state; 96505436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *last_state; 96605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv lookahead_filter = NULL; 96705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv lookaheads; 96805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 96905436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Set up state list and some reusable bitsets. */ 97005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 97105436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t max_nitems = 0; 97205436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number i; 97305436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list **nodep = &first_state; 97405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 97505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 97605436638acc7c010349a69c3395f1a57c642dc62Ying Wang *nodep = states[i]->state_list = last_state = xmalloc (sizeof **nodep); 97705436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*nodep)->state = states[i]; 97805436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*nodep)->recomputedAsSuccessor = false; 97905436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*nodep)->lookaheads = NULL; 98005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*nodep)->lr0Isocore = *nodep; 98105436638acc7c010349a69c3395f1a57c642dc62Ying Wang (*nodep)->nextIsocore = *nodep; 98205436638acc7c010349a69c3395f1a57c642dc62Ying Wang nodep = &(*nodep)->next; 98305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (states[i]->nitems > max_nitems) 98405436638acc7c010349a69c3395f1a57c642dc62Ying Wang max_nitems = states[i]->nitems; 98505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 98605436638acc7c010349a69c3395f1a57c642dc62Ying Wang *nodep = NULL; 98705436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookahead_filter = bitsetv_create (max_nitems, ntokens, BITSET_FIXED); 98805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!annotation_lists) 98905436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_ones (lookahead_filter); 99005436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads = bitsetv_create (max_nitems, ntokens, BITSET_FIXED); 99105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 99205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 99305436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Recompute states. */ 99405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 99505436638acc7c010349a69c3395f1a57c642dc62Ying Wang ContributionIndex *work = xnmalloc (max_annotations, sizeof *work); 99605436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *this_state; 99705436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (this_state = first_state; this_state; this_state = this_state->next) 99805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 99905436638acc7c010349a69c3395f1a57c642dc62Ying Wang state *s = this_state->state; 100005436638acc7c010349a69c3395f1a57c642dc62Ying Wang int i; 100105436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < s->transitions->num; ++i) 100205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 100305436638acc7c010349a69c3395f1a57c642dc62Ying Wang state *t = s->transitions->states[i]; 100405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (annotation_lists) 100505436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList__computeLookaheadFilter ( 100605436638acc7c010349a69c3395f1a57c642dc62Ying Wang annotation_lists[t->state_list->lr0Isocore->state->number], 100705436638acc7c010349a69c3395f1a57c642dc62Ying Wang t->nitems, lookahead_filter); 100805436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_lookaheads (follow_kernel_items, always_follows, 100905436638acc7c010349a69c3395f1a57c642dc62Ying Wang this_state, t, lookahead_filter, 101005436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookaheads); 101105436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_state (follow_kernel_items, always_follows, 101205436638acc7c010349a69c3395f1a57c642dc62Ying Wang annotation_lists, t, lookaheads, &last_state, 101305436638acc7c010349a69c3395f1a57c642dc62Ying Wang work, lookahead_filter, 101405436638acc7c010349a69c3395f1a57c642dc62Ying Wang &s->transitions->states[i]); 101505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 101605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 101705436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (work); 101805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 101905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 102005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_free (lookahead_filter); 102105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_free (lookaheads); 102205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 102305436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Store states back in the states array. */ 102405436638acc7c010349a69c3395f1a57c642dc62Ying Wang states = xnrealloc (states, nstates, sizeof *states); 102505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 102605436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *node; 102705436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (node = first_state; node; node = node->next) 102805436638acc7c010349a69c3395f1a57c642dc62Ying Wang states[node->state->number] = node->state; 102905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 103005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 103105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* In the case of canonical LR(1), copy item lookahead sets to reduction 103205436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookahead sets. */ 103305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!annotation_lists) 103405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 103505436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_push (TV_IELR_PHASE4); 103605436638acc7c010349a69c3395f1a57c642dc62Ying Wang initialize_LA (); 103705436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *node; 103805436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (node = first_state; node; node = node->next) 103905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!node->state->consistent) 104005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 104105436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i = 0; 104205436638acc7c010349a69c3395f1a57c642dc62Ying Wang item_number *itemset = node->state->items; 104305436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t r; 104405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (r = 0; r < node->state->reductions->num; ++r) 104505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 104605436638acc7c010349a69c3395f1a57c642dc62Ying Wang rule *this_rule = node->state->reductions->rules[r]; 104705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset lookahead_set = 104805436638acc7c010349a69c3395f1a57c642dc62Ying Wang node->state->reductions->lookahead_tokens[r]; 104905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (item_number_is_rule_number (*this_rule->rhs)) 105005436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_goto_follow_set (follow_kernel_items, 105105436638acc7c010349a69c3395f1a57c642dc62Ying Wang always_follows, node, 105205436638acc7c010349a69c3395f1a57c642dc62Ying Wang this_rule->lhs, lookahead_set); 105305436638acc7c010349a69c3395f1a57c642dc62Ying Wang else if (node->lookaheads) 105405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 105505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* We don't need to start the kernel item search back at 105605436638acc7c010349a69c3395f1a57c642dc62Ying Wang i=0 because both items and reductions are sorted on rule 105705436638acc7c010349a69c3395f1a57c642dc62Ying Wang number. */ 105805436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (!item_number_is_rule_number (ritem[itemset[i]]) 105905436638acc7c010349a69c3395f1a57c642dc62Ying Wang || item_number_as_rule_number (ritem[itemset[i]]) 106005436638acc7c010349a69c3395f1a57c642dc62Ying Wang != this_rule->number) 106105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 106205436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++i; 106305436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (i < node->state->nitems); 106405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 106505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (node->lookaheads[i]) 106605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_copy (lookahead_set, node->lookaheads[i]); 106705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 106805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 106905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 107005436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_pop (TV_IELR_PHASE4); 107105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 107205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 107305436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Free state list. */ 107405436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (first_state) 107505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 107605436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_list *node = first_state; 107705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (node->lookaheads) 107805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 107905436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 108005436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < node->state->nitems; ++i) 108105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (node->lookaheads[i]) 108205436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_free (node->lookaheads[i]); 108305436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (node->lookaheads); 108405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 108505436638acc7c010349a69c3395f1a57c642dc62Ying Wang first_state = node->next; 108605436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (node); 108705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 108805436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 108905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 109005436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 109105436638acc7c010349a69c3395f1a57c642dc62Ying Wangielr (void) 109205436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 109305436638acc7c010349a69c3395f1a57c642dc62Ying Wang LrType lr_type; 109405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 109505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Examine user options. */ 109605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 109705436638acc7c010349a69c3395f1a57c642dc62Ying Wang char *type = muscle_percent_define_get ("lr.type"); 109805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (0 == strcmp (type, "lalr")) 109905436638acc7c010349a69c3395f1a57c642dc62Ying Wang lr_type = LR_TYPE__LALR; 110005436638acc7c010349a69c3395f1a57c642dc62Ying Wang else if (0 == strcmp (type, "ielr")) 110105436638acc7c010349a69c3395f1a57c642dc62Ying Wang lr_type = LR_TYPE__IELR; 110205436638acc7c010349a69c3395f1a57c642dc62Ying Wang else if (0 == strcmp (type, "canonical-lr")) 110305436638acc7c010349a69c3395f1a57c642dc62Ying Wang lr_type = LR_TYPE__CANONICAL_LR; 110405436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 110505436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (false); 110605436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (type); 110705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 110805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 110905436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Phase 0: LALR(1). */ 111005436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_push (TV_LALR); 111105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (lr_type == LR_TYPE__CANONICAL_LR) 111205436638acc7c010349a69c3395f1a57c642dc62Ying Wang set_goto_map (); 111305436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 111405436638acc7c010349a69c3395f1a57c642dc62Ying Wang lalr (); 111505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (lr_type == LR_TYPE__LALR) 111605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 111705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_free (goto_follows); 111805436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_pop (TV_LALR); 111905436638acc7c010349a69c3395f1a57c642dc62Ying Wang return; 112005436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 112105436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_pop (TV_LALR); 112205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 112305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 112405436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv follow_kernel_items; 112505436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv always_follows; 112605436638acc7c010349a69c3395f1a57c642dc62Ying Wang InadequacyList **inadequacy_lists = NULL; 112705436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationList **annotation_lists = NULL; 112805436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct obstack annotations_obstack; 112905436638acc7c010349a69c3395f1a57c642dc62Ying Wang AnnotationIndex max_annotations = 0; 113005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 113105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 113205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Phase 1: Compute Auxiliary Tables. */ 113305436638acc7c010349a69c3395f1a57c642dc62Ying Wang state ***predecessors; 113405436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_push (TV_IELR_PHASE1); 113505436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_auxiliary_tables ( 113605436638acc7c010349a69c3395f1a57c642dc62Ying Wang &follow_kernel_items, &always_follows, 113705436638acc7c010349a69c3395f1a57c642dc62Ying Wang lr_type == LR_TYPE__CANONICAL_LR ? NULL : &predecessors); 113805436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_pop (TV_IELR_PHASE1); 113905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 114005436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Phase 2: Compute Annotations. */ 114105436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_push (TV_IELR_PHASE2); 114205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (lr_type != LR_TYPE__CANONICAL_LR) 114305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 114405436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_init (&annotations_obstack); 114505436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_compute_annotation_lists (follow_kernel_items, always_follows, 114605436638acc7c010349a69c3395f1a57c642dc62Ying Wang predecessors, &max_annotations, 114705436638acc7c010349a69c3395f1a57c642dc62Ying Wang &inadequacy_lists, &annotation_lists, 114805436638acc7c010349a69c3395f1a57c642dc62Ying Wang &annotations_obstack); 114905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 115005436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number i; 115105436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates; ++i) 115205436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (predecessors[i]); 115305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 115405436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (predecessors); 115505436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_free (goto_follows); 115605436638acc7c010349a69c3395f1a57c642dc62Ying Wang lalr_free (); 115705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 115805436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_pop (TV_IELR_PHASE2); 115905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 116005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 116105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Phase 3: Split States. */ 116205436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_push (TV_IELR_PHASE3); 116305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 116405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number nstates_lr0 = nstates; 116505436638acc7c010349a69c3395f1a57c642dc62Ying Wang ielr_split_states (follow_kernel_items, always_follows, 116605436638acc7c010349a69c3395f1a57c642dc62Ying Wang annotation_lists, max_annotations); 116705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (inadequacy_lists) 116805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 116905436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_number i; 117005436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < nstates_lr0; ++i) 117105436638acc7c010349a69c3395f1a57c642dc62Ying Wang InadequacyList__delete (inadequacy_lists[i]); 117205436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 117305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 117405436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (inadequacy_lists); 117505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (annotation_lists) 117605436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_free (&annotations_obstack, NULL); 117705436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (annotation_lists); 117805436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_free (follow_kernel_items); 117905436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_free (always_follows); 118005436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_pop (TV_IELR_PHASE3); 118105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 118205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 118305436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Phase 4: Compute Reduction Lookaheads. */ 118405436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_push (TV_IELR_PHASE4); 118505436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (goto_map); 118605436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (from_state); 118705436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (to_state); 118805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (lr_type == LR_TYPE__CANONICAL_LR) 118905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 119005436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Reduction lookaheads are computed in ielr_split_states above 119105436638acc7c010349a69c3395f1a57c642dc62Ying Wang but are timed as part of phase 4. */ 119205436638acc7c010349a69c3395f1a57c642dc62Ying Wang set_goto_map (); 119305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 119405436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 119505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 119605436638acc7c010349a69c3395f1a57c642dc62Ying Wang lalr (); 119705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitsetv_free (goto_follows); 119805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 119905436638acc7c010349a69c3395f1a57c642dc62Ying Wang timevar_pop (TV_IELR_PHASE4); 120005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 1201