105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Compute lookahead criteria for Bison. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 1984, 1986, 1989, 2000-2012 Free Software Foundation, 405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 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 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program 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 1005436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation, either version 3 of the License, or 1105436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1305436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program 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 1905436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 2205436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Find which rules need lookahead in each state, and which lookahead 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tokens they accept. */ 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <config.h> 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "system.h" 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <bitset.h> 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <bitsetv.h> 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "LR0.h" 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "complain.h" 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "derives.h" 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "getargs.h" 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "gram.h" 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "lalr.h" 3705436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "muscle-tab.h" 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "nullable.h" 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "reader.h" 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "relation.h" 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "symtab.h" 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectgoto_number *goto_map; 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wanggoto_number ngotos; 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_number *from_state; 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstate_number *to_state; 4705436638acc7c010349a69c3395f1a57c642dc62Ying Wangbitsetv goto_follows = NULL; 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Linked list of goto numbers. */ 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef struct goto_list 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct goto_list *next; 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number value; 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} goto_list; 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* LA is an NLA by NTOKENS matrix of bits. LA[l, i] is 1 if the rule 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LArule[l] is applicable in the appropriate state when the next 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project token is symbol i. If LA[l, i] and LA[l, j] are both 1 for i != j, 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project it is a conflict. */ 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bitsetv LA = NULL; 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t nLA; 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic goto_number **includes; 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic goto_list **lookback; 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 7205436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectset_goto_map (void) 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number s; 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number *temp_map; 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_map = xcalloc (nvars + 1, sizeof *goto_map); 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project temp_map = xnmalloc (nvars + 1, sizeof *temp_map); 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ngotos = 0; 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (s = 0; s < nstates; ++s) 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project transitions *sp = states[s]->transitions; 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i) 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ngotos++; 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Abort if (ngotos + 1) would overflow. */ 9105436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (ngotos != GOTO_NUMBER_MAXIMUM); 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++; 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number k = 0; 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = ntokens; i < nsyms; i++) 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project temp_map[i - ntokens] = k; 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project k += goto_map[i - ntokens]; 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = ntokens; i < nsyms; i++) 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_map[i - ntokens] = temp_map[i - ntokens]; 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_map[nsyms - ntokens] = ngotos; 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project temp_map[nsyms - ntokens] = ngotos; 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project from_state = xcalloc (ngotos, sizeof *from_state); 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project to_state = xcalloc (ngotos, sizeof *to_state); 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (s = 0; s < nstates; ++s) 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project transitions *sp = states[s]->transitions; 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i) 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++; 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project from_state[k] = s; 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project to_state[k] = sp->states[i]->number; 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (temp_map); 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 13205436638acc7c010349a69c3395f1a57c642dc62Ying Wanggoto_number 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectmap_goto (state_number s0, symbol_number sym) 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number high; 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number low; 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number middle; 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number s; 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project low = goto_map[sym - ntokens]; 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project high = goto_map[sym - ntokens + 1] - 1; 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (;;) 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 14505436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (low <= high); 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project middle = (low + high) / 2; 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s = from_state[middle]; 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (s == s0) 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return middle; 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (s < s0) 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project low = middle + 1; 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project high = middle - 1; 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectinitialize_F (void) 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number **reads = xnmalloc (ngotos, sizeof *reads); 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge); 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number nedges = 0; 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number i; 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 16705436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_follows = bitsetv_create (ngotos, ntokens, BITSET_FIXED); 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < ngotos; i++) 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number stateno = to_state[i]; 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project transitions *sp = states[stateno]->transitions; 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int j; 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project FOR_EACH_SHIFT (sp, j) 17605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set (goto_follows[i], TRANSITION_SYMBOL (sp, j)); 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; j < sp->num; j++) 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number sym = TRANSITION_SYMBOL (sp, j); 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (nullable[sym - ntokens]) 182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project edge[nedges++] = map_goto (stateno, sym); 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (nedges == 0) 186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reads[i] = NULL; 187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]); 190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project memcpy (reads[i], edge, nedges * sizeof edge[0]); 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reads[i][nedges] = END_NODE; 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nedges = 0; 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 19605436638acc7c010349a69c3395f1a57c642dc62Ying Wang relation_digraph (reads, ngotos, &goto_follows); 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < ngotos; i++) 199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (reads[i]); 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (reads); 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (edge); 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectadd_lookback_edge (state *s, rule *r, goto_number gotono) 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int ri = state_reduction_find (s, r); 210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_list *sp = xmalloc (sizeof *sp); 21105436638acc7c010349a69c3395f1a57c642dc62Ying Wang sp->next = lookback[(s->reductions->lookahead_tokens - LA) + ri]; 212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sp->value = gotono; 21305436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookback[(s->reductions->lookahead_tokens - LA) + ri] = sp; 214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbuild_relations (void) 220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge); 222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number *states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof *states1); 223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number i; 224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project includes = xnmalloc (ngotos, sizeof *includes); 226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < ngotos; i++) 228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int nedges = 0; 230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number symbol1 = states[to_state[i]]->accessing_symbol; 231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule **rulep; 232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++) 234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool done; 236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int length = 1; 237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number const *rp; 238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *s = states[from_state[i]]; 239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project states1[0] = s->number; 240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++) 242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s = transitions_to (s->transitions, 244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number_as_symbol_number (*rp)); 245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project states1[length++] = s->number; 246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!s->consistent) 249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project add_lookback_edge (s, *rulep, i); 250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project length--; 252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project done = false; 253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (!done) 254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project done = true; 25605436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Each rhs ends in a rule number, and there is a 25705436638acc7c010349a69c3395f1a57c642dc62Ying Wang sentinel (ritem[-1]=0) before the first rhs, so it is safe to 258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project decrement RP here. */ 259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rp--; 260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (ISVAR (*rp)) 261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Downcasting from item_number to symbol_number. */ 263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project edge[nedges++] = map_goto (states1[--length], 264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number_as_symbol_number (*rp)); 265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (nullable[*rp - ntokens]) 266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project done = false; 267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (nedges == 0) 272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project includes[i] = NULL; 273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int j; 276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]); 277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; j < nedges; j++) 278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project includes[i][j] = edge[j]; 279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project includes[i][nedges] = END_NODE; 280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (edge); 284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (states1); 285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project relation_transpose (&includes, ngotos); 287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectcompute_FOLLOWS (void) 293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_number i; 295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 29605436638acc7c010349a69c3395f1a57c642dc62Ying Wang relation_digraph (includes, ngotos, &goto_follows); 297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < ngotos; i++) 299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (includes[i]); 300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (includes); 302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 303cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 304cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 305cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 30605436638acc7c010349a69c3395f1a57c642dc62Ying Wangcompute_lookahead_tokens (void) 307cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 308cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t i; 309cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto_list *sp; 310cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 311cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nLA; i++) 312cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (sp = lookback[i]; sp; sp = sp->next) 31305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_or (LA[i], LA[i], goto_follows[sp->value]); 314cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 315cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Free LOOKBACK. */ 316cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nLA; i++) 317cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project LIST_FREE (goto_list, lookback[i]); 318cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 319cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (lookback); 320cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 321cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 322cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 32305436638acc7c010349a69c3395f1a57c642dc62Ying Wang/*----------------------------------------------------. 32405436638acc7c010349a69c3395f1a57c642dc62Ying Wang| Count the number of lookahead tokens required for S | 32505436638acc7c010349a69c3395f1a57c642dc62Ying Wang| (N_LOOKAHEAD_TOKENS member). | 32605436638acc7c010349a69c3395f1a57c642dc62Ying Wang`----------------------------------------------------*/ 327cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 328cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic int 32905436638acc7c010349a69c3395f1a57c642dc62Ying Wangstate_lookahead_tokens_count (state *s, bool default_reduction_only_for_accept) 330cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 33105436638acc7c010349a69c3395f1a57c642dc62Ying Wang int n_lookahead_tokens = 0; 332cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reductions *rp = s->reductions; 333cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project transitions *sp = s->transitions; 334cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 33505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Transitions are only disabled during conflict resolution, and that 33605436638acc7c010349a69c3395f1a57c642dc62Ying Wang hasn't happened yet, so there should be no need to check that 33705436638acc7c010349a69c3395f1a57c642dc62Ying Wang transition 0 hasn't been disabled before checking if it is a shift. 33805436638acc7c010349a69c3395f1a57c642dc62Ying Wang However, this check was performed at one time, so we leave it as an 33905436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver. */ 34005436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (sp->num == 0 || !TRANSITION_IS_DISABLED (sp, 0)); 34105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 34205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* We need a lookahead either to distinguish different reductions 34305436638acc7c010349a69c3395f1a57c642dc62Ying Wang (i.e., there are two or more), or to distinguish a reduction from a 34405436638acc7c010349a69c3395f1a57c642dc62Ying Wang shift. Otherwise, it is straightforward, and the state is 34505436638acc7c010349a69c3395f1a57c642dc62Ying Wang `consistent'. However, do not treat a state with any reductions as 34605436638acc7c010349a69c3395f1a57c642dc62Ying Wang consistent unless it is the accepting state (because there is never 34705436638acc7c010349a69c3395f1a57c642dc62Ying Wang a lookahead token that makes sense there, and so no lookahead token 34805436638acc7c010349a69c3395f1a57c642dc62Ying Wang should be read) if the user has otherwise disabled default 34905436638acc7c010349a69c3395f1a57c642dc62Ying Wang reductions. */ 350cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rp->num > 1 35105436638acc7c010349a69c3395f1a57c642dc62Ying Wang || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0)) 35205436638acc7c010349a69c3395f1a57c642dc62Ying Wang || (rp->num == 1 && rp->rules[0]->number != 0 35305436638acc7c010349a69c3395f1a57c642dc62Ying Wang && default_reduction_only_for_accept)) 35405436638acc7c010349a69c3395f1a57c642dc62Ying Wang n_lookahead_tokens += rp->num; 355cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 356cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s->consistent = 1; 357cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 35805436638acc7c010349a69c3395f1a57c642dc62Ying Wang return n_lookahead_tokens; 359cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 360cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 361cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 36205436638acc7c010349a69c3395f1a57c642dc62Ying Wang/*----------------------------------------------------. 36305436638acc7c010349a69c3395f1a57c642dc62Ying Wang| Compute LA, NLA, and the lookahead_tokens members. | 36405436638acc7c010349a69c3395f1a57c642dc62Ying Wang`----------------------------------------------------*/ 365cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 36605436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 367cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectinitialize_LA (void) 368cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 369cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number i; 370cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitsetv pLA; 37105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool default_reduction_only_for_accept; 37205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 37305436638acc7c010349a69c3395f1a57c642dc62Ying Wang char *default_reductions = 37405436638acc7c010349a69c3395f1a57c642dc62Ying Wang muscle_percent_define_get ("lr.default-reductions"); 37505436638acc7c010349a69c3395f1a57c642dc62Ying Wang default_reduction_only_for_accept = 37605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 0 == strcmp (default_reductions, "accepting"); 37705436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (default_reductions); 37805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 379cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 38005436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Compute the total number of reductions requiring a lookahead. */ 381cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nLA = 0; 382cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nstates; i++) 38305436638acc7c010349a69c3395f1a57c642dc62Ying Wang nLA += 38405436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_lookahead_tokens_count (states[i], 38505436638acc7c010349a69c3395f1a57c642dc62Ying Wang default_reduction_only_for_accept); 386cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Avoid having to special case 0. */ 387cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!nLA) 388cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nLA = 1; 389cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 390cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED); 391cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 39205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Initialize the members LOOKAHEAD_TOKENS for each state whose reductions 39305436638acc7c010349a69c3395f1a57c642dc62Ying Wang require lookahead tokens. */ 394cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nstates; i++) 395cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 39605436638acc7c010349a69c3395f1a57c642dc62Ying Wang int count = 39705436638acc7c010349a69c3395f1a57c642dc62Ying Wang state_lookahead_tokens_count (states[i], 39805436638acc7c010349a69c3395f1a57c642dc62Ying Wang default_reduction_only_for_accept); 399cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (count) 400cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 40105436638acc7c010349a69c3395f1a57c642dc62Ying Wang states[i]->reductions->lookahead_tokens = pLA; 402cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project pLA += count; 403cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 404cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 405cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 406cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 407cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 40805436638acc7c010349a69c3395f1a57c642dc62Ying Wang/*---------------------------------------------. 40905436638acc7c010349a69c3395f1a57c642dc62Ying Wang| Output the lookahead tokens for each state. | 41005436638acc7c010349a69c3395f1a57c642dc62Ying Wang`---------------------------------------------*/ 411cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 412cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 41305436638acc7c010349a69c3395f1a57c642dc62Ying Wanglookahead_tokens_print (FILE *out) 414cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 415cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number i; 416cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int j, k; 41705436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (out, "Lookahead tokens: BEGIN\n"); 418cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nstates; ++i) 419cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 420cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reductions *reds = states[i]->reductions; 421cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitset_iterator iter; 42205436638acc7c010349a69c3395f1a57c642dc62Ying Wang int n_lookahead_tokens = 0; 423cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 42405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (reds->lookahead_tokens) 425cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (k = 0; k < reds->num; ++k) 42605436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (reds->lookahead_tokens[k]) 42705436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++n_lookahead_tokens; 428cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 42905436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (out, "State %d: %d lookahead tokens\n", 43005436638acc7c010349a69c3395f1a57c642dc62Ying Wang i, n_lookahead_tokens); 431cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 43205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (reds->lookahead_tokens) 433cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (j = 0; j < reds->num; ++j) 43405436638acc7c010349a69c3395f1a57c642dc62Ying Wang BITSET_FOR_EACH (iter, reds->lookahead_tokens[j], k, 0) 435cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 436cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (out, " on %d (%s) -> rule %d\n", 437cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project k, symbols[k]->tag, 438cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reds->rules[j]->number); 439cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project }; 440cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 44105436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (out, "Lookahead tokens: END\n"); 442cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 443cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 444cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 445cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlalr (void) 446cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 447cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project initialize_LA (); 448cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project set_goto_map (); 449cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project initialize_F (); 45005436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookback = xcalloc (nLA, sizeof *lookback); 451cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project build_relations (); 452cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project compute_FOLLOWS (); 45305436638acc7c010349a69c3395f1a57c642dc62Ying Wang compute_lookahead_tokens (); 454cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 455cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_sets) 45605436638acc7c010349a69c3395f1a57c642dc62Ying Wang lookahead_tokens_print (stderr); 45705436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 45805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 45905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 46005436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 46105436638acc7c010349a69c3395f1a57c642dc62Ying Wanglalr_update_state_numbers (state_number old_to_new[], state_number nstates_old) 46205436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 46305436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number ngotos_reachable = 0; 46405436638acc7c010349a69c3395f1a57c642dc62Ying Wang symbol_number nonterminal = 0; 46505436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (nsyms == nvars + ntokens); 46605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 46705436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_number i; 46805436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < ngotos; ++i) 46905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 47005436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (i == goto_map[nonterminal]) 47105436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_map[nonterminal++] = ngotos_reachable; 47205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If old_to_new[from_state[i]] = nstates_old, remove this goto 47305436638acc7c010349a69c3395f1a57c642dc62Ying Wang entry. */ 47405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (old_to_new[from_state[i]] != nstates_old) 47505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 47605436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* from_state[i] is not removed, so it and thus to_state[i] are 47705436638acc7c010349a69c3395f1a57c642dc62Ying Wang reachable, so to_state[i] != nstates_old. */ 47805436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (old_to_new[to_state[i]] != nstates_old); 47905436638acc7c010349a69c3395f1a57c642dc62Ying Wang from_state[ngotos_reachable] = old_to_new[from_state[i]]; 48005436638acc7c010349a69c3395f1a57c642dc62Ying Wang to_state[ngotos_reachable] = old_to_new[to_state[i]]; 48105436638acc7c010349a69c3395f1a57c642dc62Ying Wang ++ngotos_reachable; 48205436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 48305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 48405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 48505436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (nonterminal <= nvars) 48605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 48705436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (ngotos == goto_map[nonterminal]); 48805436638acc7c010349a69c3395f1a57c642dc62Ying Wang goto_map[nonterminal++] = ngotos_reachable; 48905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 49005436638acc7c010349a69c3395f1a57c642dc62Ying Wang ngotos = ngotos_reachable; 491cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 492cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 493cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 494cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 495cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectlalr_free (void) 496cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 497cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number s; 498cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (s = 0; s < nstates; ++s) 49905436638acc7c010349a69c3395f1a57c642dc62Ying Wang states[s]->reductions->lookahead_tokens = NULL; 500cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bitsetv_free (LA); 501cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 502