Parser/acceler.c

   1 /***********************************************************
   2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
   3 The Netherlands.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the names of Stichting Mathematisch
  12 Centrum or CWI or Corporation for National Research Initiatives or
  13 CNRI not be used in advertising or publicity pertaining to
  14 distribution of the software without specific, written prior
  15 permission.
  16
  17 While CWI is the initial source for this software, a modified version
  18 is made available by the Corporation for National Research Initiatives
  19 (CNRI) at the Internet address ftp://ftp.python.org.
  20
  21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
  22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
  24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  28 PERFORMANCE 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 */
  50 static void fixdfa Py_PROTO((grammar *, dfa *));
  51 static void fixstate Py_PROTO((grammar *, state *));
  52
  53 void
  54 PyGrammar_AddAccelerators(g)
  55         grammar *g;
  56 {
  57         dfa *d;
  58         int i;
  59 #ifdef Py_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 Py_DEBUG
  67         fprintf(stderr, "Done.\n");
  68 #endif
  69 }
  70
  71 void
  72 PyGrammar_RemoveAccelerators(g)
  73         grammar *g;
  74 {
  75         dfa *d;
  76         int i;
  77         g->g_accel = 0;
  78         d = g->g_dfa;
  79         for (i = g->g_ndfas; --i >= 0; d++) {
  80                 state *s;
  81                 int j;
  82                 s = d->d_state;
  83                 for (j = 0; j < d->d_nstates; j++, s++) {
  84                         if (s->s_accel)
  85                                 PyMem_DEL(s->s_accel);
  86                         s->s_accel = NULL;
  87                 }
  88         }
  89 }
  90
  91 static void
  92 fixdfa(g, d)
  93         grammar *g;
  94         dfa *d;
  95 {
  96         state *s;
  97         int j;
  98         s = d->d_state;
  99         for (j = 0; j < d->d_nstates; j++, s++)
 100                 fixstate(g, s);
 101 }
 102
 103 static void
 104 fixstate(g, s)
 105         grammar *g;
 106         state *s;
 107 {
 108         arc *a;
 109         int k;
 110         int *accel;
 111         int nl = g->g_ll.ll_nlabels;
 112         s->s_accept = 0;
 113         accel = PyMem_NEW(int, nl);
 114         for (k = 0; k < nl; k++)
 115                 accel[k] = -1;
 116         a = s->s_arc;
 117         for (k = s->s_narcs; --k >= 0; a++) {
 118                 int lbl = a->a_lbl;
 119                 label *l = &g->g_ll.ll_label[lbl];
 120                 int type = l->lb_type;
 121                 if (a->a_arrow >= (1 << 7)) {
 122                         printf("XXX too many states!\n");
 123                         continue;
 124                 }
 125                 if (ISNONTERMINAL(type)) {
 126                         dfa *d1 = PyGrammar_FindDFA(g, type);
 127                         int ibit;
 128                         if (type - NT_OFFSET >= (1 << 7)) {
 129                                 printf("XXX too high nonterminal number!\n");
 130                                 continue;
 131                         }
 132                         for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
 133                                 if (testbit(d1->d_first, ibit)) {
 134 #ifdef applec
 135 #define MPW_881_BUG                     /* Undefine if bug below is fixed */
 136 #endif
 137 #ifdef MPW_881_BUG
 138                                         /* In 881 mode MPW 3.1 has a code
 139                                            generation bug which seems to
 140                                            set the upper bits; fix this by
 141                                            explicitly masking them off */
 142                                         int temp;
 143 #endif
 144                                         if (accel[ibit] != -1)
 145                                                 printf("XXX ambiguity!\n");
 146 #ifdef MPW_881_BUG
 147                                         temp = 0xFFFF &
 148                                                 (a->a_arrow | (1 << 7) |
 149                                                  ((type - NT_OFFSET) << 8));
 150                                         accel[ibit] = temp;
 151 #else
 152                                         accel[ibit] = a->a_arrow | (1 << 7) |
 153                                                 ((type - NT_OFFSET) << 8);
 154 #endif
 155                                 }
 156                         }
 157                 }
 158                 else if (lbl == EMPTY)
 159                         s->s_accept = 1;
 160                 else if (lbl >= 0 && lbl < nl)
 161                         accel[lbl] = a->a_arrow;
 162         }
 163         while (nl > 0 && accel[nl-1] == -1)
 164                 nl--;
 165         for (k = 0; k < nl && accel[k] == -1;)
 166                 k++;
 167         if (k < nl) {
 168                 int i;
 169                 s->s_accel = PyMem_NEW(int, nl-k);
 170                 if (s->s_accel == NULL) {
 171                         fprintf(stderr, "no mem to add parser accelerators\n");
 172                         exit(1);
 173                 }
 174                 s->s_lower = k;
 175                 s->s_upper = nl;
 176                 for (i = 0; k < nl; i++, k++)
 177                         s->s_accel[i] = accel[k];
 178         }
 179         PyMem_DEL(accel);
 180 }