1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Generate the nondeterministic finite state machine for Bison. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 3cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005 Free 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Software Foundation, Inc. 5cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 6cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This file is part of Bison, the GNU Compiler Compiler. 7cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 8cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Bison is free software; you can redistribute it and/or modify 9cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project it under the terms of the GNU General Public License as published by 10cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the Free Software Foundation; either version 2, or (at your option) 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project any later version. 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Bison is distributed in the hope that it will be useful, 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project GNU General Public License for more details. 17cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 18cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project You should have received a copy of the GNU General Public License 19cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project along with Bison; see the file COPYING. If not, write to 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Boston, MA 02110-1301, USA. */ 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* See comments in state.h for the data structures that represent it. 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project The entry point is generate_states. */ 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <config.h> 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "system.h" 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <bitset.h> 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <quotearg.h> 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "LR0.h" 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "closure.h" 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "complain.h" 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "getargs.h" 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "gram.h" 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "gram.h" 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "lalr.h" 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "reader.h" 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "reduce.h" 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "state.h" 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "symtab.h" 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef struct state_list 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct state_list *next; 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *state; 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} state_list; 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic state_list *first_state = NULL; 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic state_list *last_state = NULL; 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*------------------------------------------------------------------. 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| A state was just discovered from another state. Queue it for | 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| later examination, in order to find its transitions. Return it. | 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`------------------------------------------------------------------*/ 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic state * 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_list_append (symbol_number sym, size_t core_size, item_number *core) 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_list *node = xmalloc (sizeof *node); 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *s = state_new (sym, core_size, core); 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_automaton) 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n", 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nstates, sym, symbols[sym]->tag); 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project node->next = NULL; 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project node->state = s; 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!first_state) 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project first_state = node; 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (last_state) 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project last_state->next = node; 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project last_state = node; 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return s; 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic int nshifts; 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic symbol_number *shift_symbol; 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic rule **redset; 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic state **shiftset; 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic item_number **kernel_base; 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic int *kernel_size; 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic item_number *kernel_items; 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectallocate_itemsets (void) 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number i; 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_number r; 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number *rhsp; 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Count the number of occurrences of all the symbols in RITEMS. 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Note that useless productions (hence useless nonterminals) are 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project browsed too, hence we need to allocate room for _all_ the 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbols. */ 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t count = 0; 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t *symbol_count = xcalloc (nsyms + nuseless_nonterminals, 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sizeof *symbol_count); 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (r = 0; r < nrules; ++r) 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp) 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project count++; 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_count[*rhsp]++; 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* See comments before new_itemsets. All the vectors of items 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project live inside KERNEL_ITEMS. The number of active items after 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project some symbol S cannot be more than the number of times that S 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project appears as an item, which is SYMBOL_COUNT[S]. 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project We allocate that much space for each symbol. */ 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project kernel_base = xnmalloc (nsyms, sizeof *kernel_base); 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project kernel_items = xnmalloc (count, sizeof *kernel_items); 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project count = 0; 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nsyms; i++) 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project kernel_base[i] = kernel_items + count; 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project count += symbol_count[i]; 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (symbol_count); 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project kernel_size = xnmalloc (nsyms, sizeof *kernel_size); 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectallocate_storage (void) 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project allocate_itemsets (); 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project shiftset = xnmalloc (nsyms, sizeof *shiftset); 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project redset = xnmalloc (nrules, sizeof *redset); 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_hash_new (); 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project shift_symbol = xnmalloc (nsyms, sizeof *shift_symbol); 145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectfree_storage (void) 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (shift_symbol); 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (redset); 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (shiftset); 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (kernel_base); 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (kernel_size); 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (kernel_items); 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_hash_free (); 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------------------------------------------. 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Find which symbols can be shifted in S, and for each one | 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| record which items would be active after that shift. Uses the | 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| contents of itemset. | 167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| | 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| shift_symbol is set to a vector of the symbols that can be | 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| shifted. For each symbol in the grammar, kernel_base[symbol] | 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| points to a vector of item numbers activated if that symbol is | 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| shifted, and kernel_size[symbol] is their numbers. | 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------------------------------------------*/ 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnew_itemsets (state *s) 176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t i; 178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_automaton) 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "Entering new_itemsets, state = %d\n", s->number); 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memset (kernel_size, 0, nsyms * sizeof *kernel_size); 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nshifts = 0; 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nritemset; ++i) 187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (ritem[itemset[i]] >= 0) 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number sym = item_number_as_symbol_number (ritem[itemset[i]]); 190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!kernel_size[sym]) 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project shift_symbol[nshifts] = sym; 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nshifts++; 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project kernel_base[sym][kernel_size[sym]] = itemset[i] + 1; 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project kernel_size[sym]++; 198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*--------------------------------------------------------------. 204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Find the state we would get to (from the current state) by | 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| shifting SYM. Create a new state if no equivalent one exists | 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| already. Used by append_states. | 207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`--------------------------------------------------------------*/ 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic state * 210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectget_state (symbol_number sym, size_t core_size, item_number *core) 211cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *s; 213cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_automaton) 215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "Entering get_state, symbol = %d (%s)\n", 216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sym, symbols[sym]->tag); 217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s = state_hash_lookup (core_size, core); 219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!s) 220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s = state_list_append (sym, core_size, core); 221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_automaton) 223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "Exiting get_state => %d\n", s->number); 224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return s; 226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------------------------------------------. 229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Use the information computed by new_itemsets to find the state | 230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| numbers reached by each shift transition from S. | 231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| | 232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| SHIFTSET is set up as a vector of those states. | 233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------------------------------------------*/ 234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectappend_states (state *s) 237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_automaton) 241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "Entering append_states, state = %d\n", s->number); 242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* First sort shift_symbol into increasing order. */ 244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 1; i < nshifts; i++) 246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number sym = shift_symbol[i]; 248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int j; 249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = i; 0 < j && sym < shift_symbol[j - 1]; j--) 250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project shift_symbol[j] = shift_symbol[j - 1]; 251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project shift_symbol[j] = sym; 252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nshifts; i++) 255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 256cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number sym = shift_symbol[i]; 257cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project shiftset[i] = get_state (sym, kernel_size[sym], kernel_base[sym]); 258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*----------------------------------------------------------------. 263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Find which rules can be used for reduction transitions from the | 264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| current state and make a reductions structure for the state to | 265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| record their rule numbers. | 266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`----------------------------------------------------------------*/ 267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsave_reductions (state *s) 270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int count = 0; 272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t i; 273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Find and count the active items that represent ends of rules. */ 275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nritemset; ++i) 276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number item = ritem[itemset[i]]; 278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (item_number_is_rule_number (item)) 279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_number r = item_number_as_rule_number (item); 281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project redset[count++] = &rules[r]; 282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (r == 0) 283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This is "reduce 0", i.e., accept. */ 285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project assert (!final_state); 286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project final_state = s; 287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Make a reductions structure and copy the data into it. */ 292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_reductions_set (s, count, redset); 293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 296cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------. 297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Build STATES. | 298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------*/ 299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectset_states (void) 302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 303cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project states = xcalloc (nstates, sizeof *states); 304cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 305cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (first_state) 306cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 307cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_list *this = first_state; 308cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 309cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Pessimization, but simplification of the code: make sure all 310cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the states have valid transitions and reductions members, 311cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project even if reduced to 0. It is too soon for errs, which are 312cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project computed later, but set_conflicts. */ 313cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *s = this->state; 314cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!s->transitions) 315cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_transitions_set (s, 0, 0); 316cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!s->reductions) 317cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_reductions_set (s, 0, 0); 318cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 319cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project states[s->number] = s; 320cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 321cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project first_state = this->next; 322cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (this); 323cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 324cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project first_state = NULL; 325cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project last_state = NULL; 326cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 327cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 328cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 329cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*-------------------------------------------------------------------. 330cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Compute the nondeterministic finite state machine (see state.h for | 331cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| details) from the grammar. | 332cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`-------------------------------------------------------------------*/ 333cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 334cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 335cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectgenerate_states (void) 336cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 337cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number initial_core = 0; 338cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_list *list = NULL; 339cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project allocate_storage (); 340cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_closure (nritems); 341cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 342cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Create the initial state. The 0 at the lhs is the index of the 343cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item of this initial rule. */ 344cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_list_append (0, 1, &initial_core); 345cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 346cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* States are queued when they are created; process them all. */ 347cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (list = first_state; list; list = list->next) 348cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 349cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *s = list->state; 350cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_automaton) 351cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stderr, "Processing state %d (reached by %s)\n", 352cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s->number, 353cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbols[s->accessing_symbol]->tag); 354cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Set up ruleset and itemset for the transitions out of this 355cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state. ruleset gets a 1 bit for each rule that could reduce 356cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project now. itemset gets a vector of all the items that could be 357cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project accepted next. */ 358cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project closure (s->items, s->nitems); 359cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Record the reductions allowed out of this state. */ 360cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project save_reductions (s); 361cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Find the itemsets of the states that shifts can reach. */ 362cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_itemsets (s); 363cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Find or create the core structures for those states. */ 364cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project append_states (s); 365cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 366cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Create the shifts structures for the shifts to those states, 367cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project now that the state numbers transitioning to are known. */ 368cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_transitions_set (s, nshifts, shiftset); 369cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 370cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 371cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* discard various storage */ 372cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free_closure (); 373cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free_storage (); 374cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 375cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Set up STATES. */ 376cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project set_states (); 377cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 378