1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Type definitions for nondeterministic finite state machine for Bison. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 3cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Free Software 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 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#include <config.h> 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "system.h" 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <hash.h> 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "complain.h" 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "gram.h" 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "state.h" 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /*-------------------. 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project | Shifts and Gotos. | 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project `-------------------*/ 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*-----------------------------------------. 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Create a new array of NUM shifts/gotos. | 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`-----------------------------------------*/ 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic transitions * 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttransitions_new (int num, state **the_states) 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t states_size = num * sizeof *the_states; 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project transitions *res = xmalloc (offsetof (transitions, states) + states_size); 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->num = num; 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (res->states, the_states, states_size); 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return res; 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*-------------------------------------------------------. 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Return the state such that SHIFTS contain a shift/goto | 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| to it on SYM. Abort if none found. | 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`-------------------------------------------------------*/ 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate * 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttransitions_to (transitions *shifts, symbol_number sym) 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int j; 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; ; j++) 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project assert (j < shifts->num); 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (TRANSITION_SYMBOL (shifts, j) == sym) 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return shifts->states[j]; 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /*--------------------. 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project | Error transitions. | 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project `--------------------*/ 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------------. 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Create a new array of NUM errs. | 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------------*/ 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecterrs * 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecterrs_new (int num, symbol **tokens) 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t symbols_size = num * sizeof *tokens; 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project errs *res = xmalloc (offsetof (errs, symbols) + symbols_size); 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->num = num; 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (res->symbols, tokens, symbols_size); 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return res; 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /*-------------. 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project | Reductions. | 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project `-------------*/ 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------------------. 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Create a new array of NUM reductions. | 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------------------*/ 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic reductions * 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectreductions_new (int num, rule **reds) 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t rules_size = num * sizeof *reds; 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reductions *res = xmalloc (offsetof (reductions, rules) + rules_size); 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->num = num; 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->look_ahead_tokens = NULL; 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (res->rules, reds, rules_size); 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return res; 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /*---------. 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project | States. | 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project `---------*/ 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_number nstates = 0; 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* FINAL_STATE is properly set by new_state when it recognizes its 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project accessing symbol: $end. */ 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate *final_state = NULL; 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*------------------------------------------------------------------. 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Create a new state with ACCESSING_SYMBOL, for those items. Store | 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| it in the state hash table. | 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`------------------------------------------------------------------*/ 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate * 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_new (symbol_number accessing_symbol, 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t nitems, item_number *core) 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *res; 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t items_size = nitems * sizeof *core; 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project assert (nstates < STATE_NUMBER_MAXIMUM); 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res = xmalloc (offsetof (state, items) + items_size); 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->number = nstates++; 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->accessing_symbol = accessing_symbol; 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->transitions = NULL; 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->reductions = NULL; 145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->errs = NULL; 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->consistent = 0; 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->solved_conflicts = NULL; 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project res->nitems = nitems; 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (res->items, core, items_size); 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_hash_insert (res); 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return res; 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------. 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Free S. | 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------*/ 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_free (state *s) 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (s->transitions); 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (s->reductions); 167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (s->errs); 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (s); 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------. 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Set the transitions of S. | 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------*/ 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_transitions_set (state *s, int num, state **trans) 178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project assert (!s->transitions); 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s->transitions = transitions_new (num, trans); 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*--------------------------. 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Set the reductions of S. | 186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`--------------------------*/ 187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_reductions_set (state *s, int num, rule **reds) 190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project assert (!s->reductions); 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s->reductions = reductions_new (num, reds); 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectint 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_reduction_find (state *s, rule *r) 198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reductions *reds = s->reductions; 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < reds->num; ++i) 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (reds->rules[i] == r) 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return i; 204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return -1; 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*--------------------. 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Set the errs of S. | 210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`--------------------*/ 211cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 213cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_errs_set (state *s, int num, symbol **tokens) 214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project assert (!s->errs); 216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s->errs = errs_new (num, tokens); 217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------------------------------. 222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Print on OUT all the look-ahead tokens such that S | 223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| wants to reduce R. | 224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------------------------------*/ 225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out) 228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Find the reduction we are handling. */ 230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reductions *reds = s->reductions; 231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int red = state_reduction_find (s, r); 232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Print them if there are. */ 234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (reds->look_ahead_tokens && red != -1) 235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_iterator biter; 237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int k; 238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project char const *sep = ""; 239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (out, " ["); 240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project BITSET_FOR_EACH (biter, reds->look_ahead_tokens[red], k, 0) 241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (out, "%s%s", sep, symbols[k]->tag); 243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sep = ", "; 244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (out, "]"); 246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------. 251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| A state hash table. | 252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------*/ 253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Initial capacity of states hash table. */ 255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define HT_INITIAL_CAPACITY 257 256cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 257cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic struct hash_table *state_table = NULL; 258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Two states are equal if they have the same core items. */ 260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline bool 261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_compare (state const *s1, state const *s2) 262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t i; 264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (s1->nitems != s2->nitems) 266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < s1->nitems; ++i) 269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (s1->items[i] != s2->items[i]) 270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_comparator (void const *s1, void const *s2) 277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return state_compare (s1, s2); 279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic inline size_t 282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_hash (state const *s, size_t tablesize) 283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Add up the state's item numbers to get a hash key. */ 285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t key = 0; 286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t i; 287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < s->nitems; ++i) 288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project key += s->items[i]; 289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return key % tablesize; 290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic size_t 293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_hasher (void const *s, size_t tablesize) 294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return state_hash (s, tablesize); 296cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*-------------------------------. 300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Create the states hash table. | 301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`-------------------------------*/ 302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 303cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 304cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_hash_new (void) 305cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 306cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_table = hash_initialize (HT_INITIAL_CAPACITY, 307cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project NULL, 308cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_hasher, 309cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_comparator, 310cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project NULL); 311cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 312cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 313cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 314cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------------------------. 315cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Free the states hash table, not the states. | 316cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------------------------*/ 317cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 318cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 319cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_hash_free (void) 320cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 321cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project hash_free (state_table); 322cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 323cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 324cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 325cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*-----------------------------------. 326cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Insert S in the state hash table. | 327cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`-----------------------------------*/ 328cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 329cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 330cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_hash_insert (state *s) 331cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 332cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project hash_insert (state_table, s); 333cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 334cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 335cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 336cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*------------------------------------------------------------------. 337cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Find the state associated to the CORE, and return it. If it does | 338cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| not exist yet, return NULL. | 339cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`------------------------------------------------------------------*/ 340cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 341cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate * 342cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_hash_lookup (size_t nitems, item_number *core) 343cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 344cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t items_size = nitems * sizeof *core; 345cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *probe = xmalloc (offsetof (state, items) + items_size); 346cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *entry; 347cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 348cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project probe->nitems = nitems; 349cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (probe->items, core, items_size); 350cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry = hash_lookup (state_table, probe); 351cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (probe); 352cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return entry; 353cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 354cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 355cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* All the decorated states, indexed by the state number. */ 356cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate **states = NULL; 357cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 358cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 359cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*----------------------. 360cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Free all the states. | 361cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`----------------------*/ 362cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 363cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 364cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstates_free (void) 365cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 366cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number i; 367cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nstates; ++i) 368cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_free (states[i]); 369cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (states); 370cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 371