Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 1 | /* Parser accelerator module */ |
| 2 | |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame^] | 3 | /* The parser as originally conceived had disappointing performance. |
| 4 | This module does some precomputation that speeds up the selection |
| 5 | of a DFA based upon a token, turning a search through an array |
| 6 | into a simple indexing operation. The parser now cannot work |
| 7 | without the accelerators installed. Note that the accelerators |
| 8 | are installed dynamically when the parser is initialized, they |
| 9 | are not part of the static data structure written on graminit.[ch] |
| 10 | by the parser generator. */ |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 11 | |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame^] | 12 | #include "pgenheaders.h" |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 13 | #include "grammar.h" |
| 14 | #include "token.h" |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame^] | 15 | #include "parser.h" |
| 16 | |
| 17 | /* Forward references */ |
| 18 | static void fixdfa PROTO((grammar *, dfa *)); |
| 19 | static void fixstate PROTO((grammar *, dfa *, state *)); |
| 20 | |
| 21 | void |
| 22 | addaccelerators(g) |
| 23 | grammar *g; |
| 24 | { |
| 25 | dfa *d; |
| 26 | int i; |
| 27 | #ifdef DEBUG |
| 28 | printf("Adding parser accellerators ...\n"); |
| 29 | #endif |
| 30 | d = g->g_dfa; |
| 31 | for (i = g->g_ndfas; --i >= 0; d++) |
| 32 | fixdfa(g, d); |
| 33 | g->g_accel = 1; |
| 34 | #ifdef DEBUG |
| 35 | printf("Done.\n"); |
| 36 | #endif |
| 37 | } |
| 38 | |
| 39 | static void |
| 40 | fixdfa(g, d) |
| 41 | grammar *g; |
| 42 | dfa *d; |
| 43 | { |
| 44 | state *s; |
| 45 | int j; |
| 46 | s = d->d_state; |
| 47 | for (j = 0; j < d->d_nstates; j++, s++) |
| 48 | fixstate(g, d, s); |
| 49 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 50 | |
| 51 | static void |
| 52 | fixstate(g, d, s) |
| 53 | grammar *g; |
| 54 | dfa *d; |
| 55 | state *s; |
| 56 | { |
| 57 | arc *a; |
| 58 | int k; |
| 59 | int *accel; |
| 60 | int nl = g->g_ll.ll_nlabels; |
| 61 | s->s_accept = 0; |
| 62 | accel = NEW(int, nl); |
| 63 | for (k = 0; k < nl; k++) |
| 64 | accel[k] = -1; |
| 65 | a = s->s_arc; |
| 66 | for (k = s->s_narcs; --k >= 0; a++) { |
| 67 | int lbl = a->a_lbl; |
| 68 | label *l = &g->g_ll.ll_label[lbl]; |
| 69 | int type = l->lb_type; |
| 70 | if (a->a_arrow >= (1 << 7)) { |
| 71 | printf("XXX too many states!\n"); |
| 72 | continue; |
| 73 | } |
| 74 | if (ISNONTERMINAL(type)) { |
| 75 | dfa *d1 = finddfa(g, type); |
| 76 | int ibit; |
| 77 | if (type - NT_OFFSET >= (1 << 7)) { |
| 78 | printf("XXX too high nonterminal number!\n"); |
| 79 | continue; |
| 80 | } |
| 81 | for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { |
| 82 | if (testbit(d1->d_first, ibit)) { |
| 83 | if (accel[ibit] != -1) |
| 84 | printf("XXX ambiguity!\n"); |
| 85 | accel[ibit] = a->a_arrow | (1 << 7) | |
| 86 | ((type - NT_OFFSET) << 8); |
| 87 | } |
| 88 | } |
| 89 | } |
| 90 | else if (lbl == EMPTY) |
| 91 | s->s_accept = 1; |
| 92 | else if (lbl >= 0 && lbl < nl) |
| 93 | accel[lbl] = a->a_arrow; |
| 94 | } |
| 95 | while (nl > 0 && accel[nl-1] == -1) |
| 96 | nl--; |
| 97 | for (k = 0; k < nl && accel[k] == -1;) |
| 98 | k++; |
| 99 | if (k < nl) { |
| 100 | int i; |
| 101 | s->s_accel = NEW(int, nl-k); |
| 102 | if (s->s_accel == NULL) { |
| 103 | fprintf(stderr, "no mem to add parser accelerators\n"); |
| 104 | exit(1); |
| 105 | } |
| 106 | s->s_lower = k; |
| 107 | s->s_upper = nl; |
| 108 | for (i = 0; k < nl; i++, k++) |
| 109 | s->s_accel[i] = accel[k]; |
| 110 | } |
| 111 | DEL(accel); |
| 112 | } |