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