acceler.c revision d266eb460e20ded087d01a29da0a230e235afc40
1/*********************************************************** 2Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam, 3The Netherlands. 4 5 All Rights Reserved 6 7Permission to use, copy, modify, and distribute this software and its 8documentation for any purpose and without fee is hereby granted, 9provided that the above copyright notice appear in all copies and that 10both that copyright notice and this permission notice appear in 11supporting documentation, and that the names of Stichting Mathematisch 12Centrum or CWI or Corporation for National Research Initiatives or 13CNRI not be used in advertising or publicity pertaining to 14distribution of the software without specific, written prior 15permission. 16 17While CWI is the initial source for this software, a modified version 18is made available by the Corporation for National Research Initiatives 19(CNRI) at the Internet address ftp://ftp.python.org. 20 21STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH 22REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF 23MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH 24CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 25DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 26PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER 27TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 28PERFORMANCE OF THIS SOFTWARE. 29 30******************************************************************/ 31 32/* Parser accelerator module */ 33 34/* The parser as originally conceived had disappointing performance. 35 This module does some precomputation that speeds up the selection 36 of a DFA based upon a token, turning a search through an array 37 into a simple indexing operation. The parser now cannot work 38 without the accelerators installed. Note that the accelerators 39 are installed dynamically when the parser is initialized, they 40 are not part of the static data structure written on graminit.[ch] 41 by the parser generator. */ 42 43#include "pgenheaders.h" 44#include "grammar.h" 45#include "node.h" 46#include "token.h" 47#include "parser.h" 48 49/* Forward references */ 50static void fixdfa PROTO((grammar *, dfa *)); 51static void fixstate PROTO((grammar *, state *)); 52 53void 54addaccelerators(g) 55 grammar *g; 56{ 57 dfa *d; 58 int i; 59#ifdef DEBUG 60 fprintf(stderr, "Adding parser accelerators ...\n"); 61#endif 62 d = g->g_dfa; 63 for (i = g->g_ndfas; --i >= 0; d++) 64 fixdfa(g, d); 65 g->g_accel = 1; 66#ifdef DEBUG 67 fprintf(stderr, "Done.\n"); 68#endif 69} 70 71static void 72fixdfa(g, d) 73 grammar *g; 74 dfa *d; 75{ 76 state *s; 77 int j; 78 s = d->d_state; 79 for (j = 0; j < d->d_nstates; j++, s++) 80 fixstate(g, s); 81} 82 83static void 84fixstate(g, s) 85 grammar *g; 86 state *s; 87{ 88 arc *a; 89 int k; 90 int *accel; 91 int nl = g->g_ll.ll_nlabels; 92 s->s_accept = 0; 93 accel = NEW(int, nl); 94 for (k = 0; k < nl; k++) 95 accel[k] = -1; 96 a = s->s_arc; 97 for (k = s->s_narcs; --k >= 0; a++) { 98 int lbl = a->a_lbl; 99 label *l = &g->g_ll.ll_label[lbl]; 100 int type = l->lb_type; 101 if (a->a_arrow >= (1 << 7)) { 102 printf("XXX too many states!\n"); 103 continue; 104 } 105 if (ISNONTERMINAL(type)) { 106 dfa *d1 = finddfa(g, type); 107 int ibit; 108 if (type - NT_OFFSET >= (1 << 7)) { 109 printf("XXX too high nonterminal number!\n"); 110 continue; 111 } 112 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { 113 if (testbit(d1->d_first, ibit)) { 114#ifdef applec 115#define MPW_881_BUG /* Undefine if bug below is fixed */ 116#endif 117#ifdef MPW_881_BUG 118 /* In 881 mode MPW 3.1 has a code 119 generation bug which seems to 120 set the upper bits; fix this by 121 explicitly masking them off */ 122 int temp; 123#endif 124 if (accel[ibit] != -1) 125 printf("XXX ambiguity!\n"); 126#ifdef MPW_881_BUG 127 temp = 0xFFFF & 128 (a->a_arrow | (1 << 7) | 129 ((type - NT_OFFSET) << 8)); 130 accel[ibit] = temp; 131#else 132 accel[ibit] = a->a_arrow | (1 << 7) | 133 ((type - NT_OFFSET) << 8); 134#endif 135 } 136 } 137 } 138 else if (lbl == EMPTY) 139 s->s_accept = 1; 140 else if (lbl >= 0 && lbl < nl) 141 accel[lbl] = a->a_arrow; 142 } 143 while (nl > 0 && accel[nl-1] == -1) 144 nl--; 145 for (k = 0; k < nl && accel[k] == -1;) 146 k++; 147 if (k < nl) { 148 int i; 149 s->s_accel = NEW(int, nl-k); 150 if (s->s_accel == NULL) { 151 fprintf(stderr, "no mem to add parser accelerators\n"); 152 exit(1); 153 } 154 s->s_lower = k; 155 s->s_upper = nl; 156 for (i = 0; k < nl; i++, k++) 157 s->s_accel[i] = accel[k]; 158 } 159 DEL(accel); 160} 161