Parser/acceler.c

   1 /***********************************************************
   2 Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
   3 Amsterdam, 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 "token.h"
  39 #include "parser.h"
  40
  41 /* Forward references */
  42 static void fixdfa PROTO((grammar *, dfa *));
  43 static void fixstate PROTO((grammar *, state *));
  44
  45 void
  46 addaccelerators(g)
  47         grammar *g;
  48 {
  49         dfa *d;
  50         int i;
  51 #ifdef DEBUG
  52         fprintf(stderr, "Adding parser accelerators ...\n");
  53 #endif
  54         d = g->g_dfa;
  55         for (i = g->g_ndfas; --i >= 0; d++)
  56                 fixdfa(g, d);
  57         g->g_accel = 1;
  58 #ifdef DEBUG
  59         fprintf(stderr, "Done.\n");
  60 #endif
  61 }
  62
  63 static void
  64 fixdfa(g, d)
  65         grammar *g;
  66         dfa *d;
  67 {
  68         state *s;
  69         int j;
  70         s = d->d_state;
  71         for (j = 0; j < d->d_nstates; j++, s++)
  72                 fixstate(g, s);
  73 }
  74
  75 static void
  76 fixstate(g, s)
  77         grammar *g;
  78         state *s;
  79 {
  80         arc *a;
  81         int k;
  82         int *accel;
  83         int nl = g->g_ll.ll_nlabels;
  84         s->s_accept = 0;
  85         accel = NEW(int, nl);
  86         for (k = 0; k < nl; k++)
  87                 accel[k] = -1;
  88         a = s->s_arc;
  89         for (k = s->s_narcs; --k >= 0; a++) {
  90                 int lbl = a->a_lbl;
  91                 label *l = &g->g_ll.ll_label[lbl];
  92                 int type = l->lb_type;
  93                 if (a->a_arrow >= (1 << 7)) {
  94                         printf("XXX too many states!\n");
  95                         continue;
  96                 }
  97                 if (ISNONTERMINAL(type)) {
  98                         dfa *d1 = finddfa(g, type);
  99                         int ibit;
 100                         if (type - NT_OFFSET >= (1 << 7)) {
 101                                 printf("XXX too high nonterminal number!\n");
 102                                 continue;
 103                         }
 104                         for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
 105                                 if (testbit(d1->d_first, ibit)) {
 106 #ifdef applec
 107 #define MPW_881_bug                     /* Undefine if bug below is fixed */
 108 #endif
 109 #ifdef MPW_881_BUG
 110                                         /* In 881 mode MPW 3.1 has a code
 111                                            generation bug which seems to
 112                                            set the upper bits; fix this by
 113                                            explicitly masking them off */
 114                                         int temp;
 115 #endif
 116                                         if (accel[ibit] != -1)
 117                                                 printf("XXX ambiguity!\n");
 118 #ifdef MPW_881_BUG
 119                                         temp = 0xFFFF &
 120                                                 (a->a_arrow | (1 << 7) |
 121                                                  ((type - NT_OFFSET) << 8));
 122                                         accel[ibit] = temp;
 123 #else
 124                                         accel[ibit] = a->a_arrow | (1 << 7) |
 125                                                 ((type - NT_OFFSET) << 8);
 126 #endif
 127                                 }
 128                         }
 129                 }
 130                 else if (lbl == EMPTY)
 131                         s->s_accept = 1;
 132                 else if (lbl >= 0 && lbl < nl)
 133                         accel[lbl] = a->a_arrow;
 134         }
 135         while (nl > 0 && accel[nl-1] == -1)
 136                 nl--;
 137         for (k = 0; k < nl && accel[k] == -1;)
 138                 k++;
 139         if (k < nl) {
 140                 int i;
 141                 s->s_accel = NEW(int, nl-k);
 142                 if (s->s_accel == NULL) {
 143                         fprintf(stderr, "no mem to add parser accelerators\n");
 144                         exit(1);
 145                 }
 146                 s->s_lower = k;
 147                 s->s_upper = nl;
 148                 for (i = 0; k < nl; i++, k++)
 149                         s->s_accel[i] = accel[k];
 150         }
 151         DEL(accel);
 152 }