Guido van Rossum | f70e43a | 1991-02-19 12:39:46 +0000 | [diff] [blame] | 1 | /*********************************************************** |
Guido van Rossum | fd71b9e | 2000-06-30 23:50:40 +0000 | [diff] [blame] | 2 | Copyright (c) 2000, BeOpen.com. |
| 3 | Copyright (c) 1995-2000, Corporation for National Research Initiatives. |
| 4 | Copyright (c) 1990-1995, Stichting Mathematisch Centrum. |
| 5 | All rights reserved. |
Guido van Rossum | f70e43a | 1991-02-19 12:39:46 +0000 | [diff] [blame] | 6 | |
Guido van Rossum | fd71b9e | 2000-06-30 23:50:40 +0000 | [diff] [blame] | 7 | See the file "Misc/COPYRIGHT" for information on usage and |
| 8 | redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
Guido van Rossum | f70e43a | 1991-02-19 12:39:46 +0000 | [diff] [blame] | 9 | ******************************************************************/ |
| 10 | |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 11 | /* Parser accelerator module */ |
| 12 | |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 13 | /* The parser as originally conceived had disappointing performance. |
| 14 | This module does some precomputation that speeds up the selection |
| 15 | of a DFA based upon a token, turning a search through an array |
| 16 | into a simple indexing operation. The parser now cannot work |
| 17 | without the accelerators installed. Note that the accelerators |
| 18 | are installed dynamically when the parser is initialized, they |
| 19 | are not part of the static data structure written on graminit.[ch] |
| 20 | by the parser generator. */ |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 21 | |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 22 | #include "pgenheaders.h" |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 23 | #include "grammar.h" |
Guido van Rossum | 1d5735e | 1994-08-30 08:27:36 +0000 | [diff] [blame] | 24 | #include "node.h" |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 25 | #include "token.h" |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 26 | #include "parser.h" |
| 27 | |
| 28 | /* Forward references */ |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 29 | static void fixdfa(grammar *, dfa *); |
| 30 | static void fixstate(grammar *, state *); |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 31 | |
| 32 | void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 33 | PyGrammar_AddAccelerators(grammar *g) |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 34 | { |
| 35 | dfa *d; |
| 36 | int i; |
Guido van Rossum | 408027e | 1996-12-30 16:17:54 +0000 | [diff] [blame] | 37 | #ifdef Py_DEBUG |
Guido van Rossum | 888d205 | 1992-09-03 20:45:24 +0000 | [diff] [blame] | 38 | fprintf(stderr, "Adding parser accelerators ...\n"); |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 39 | #endif |
| 40 | d = g->g_dfa; |
| 41 | for (i = g->g_ndfas; --i >= 0; d++) |
| 42 | fixdfa(g, d); |
| 43 | g->g_accel = 1; |
Guido van Rossum | 408027e | 1996-12-30 16:17:54 +0000 | [diff] [blame] | 44 | #ifdef Py_DEBUG |
Guido van Rossum | 888d205 | 1992-09-03 20:45:24 +0000 | [diff] [blame] | 45 | fprintf(stderr, "Done.\n"); |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 46 | #endif |
| 47 | } |
| 48 | |
Guido van Rossum | aee094c | 1997-08-02 03:02:27 +0000 | [diff] [blame] | 49 | void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 50 | PyGrammar_RemoveAccelerators(grammar *g) |
Guido van Rossum | aee094c | 1997-08-02 03:02:27 +0000 | [diff] [blame] | 51 | { |
| 52 | dfa *d; |
| 53 | int i; |
| 54 | g->g_accel = 0; |
| 55 | d = g->g_dfa; |
| 56 | for (i = g->g_ndfas; --i >= 0; d++) { |
| 57 | state *s; |
| 58 | int j; |
| 59 | s = d->d_state; |
| 60 | for (j = 0; j < d->d_nstates; j++, s++) { |
| 61 | if (s->s_accel) |
| 62 | PyMem_DEL(s->s_accel); |
| 63 | s->s_accel = NULL; |
| 64 | } |
| 65 | } |
| 66 | } |
| 67 | |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 68 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 69 | fixdfa(grammar *g, dfa *d) |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 70 | { |
| 71 | state *s; |
| 72 | int j; |
| 73 | s = d->d_state; |
| 74 | for (j = 0; j < d->d_nstates; j++, s++) |
Guido van Rossum | 9abc539 | 1992-03-27 17:24:37 +0000 | [diff] [blame] | 75 | fixstate(g, s); |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 76 | } |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 77 | |
| 78 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 79 | fixstate(grammar *g, state *s) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 80 | { |
| 81 | arc *a; |
| 82 | int k; |
| 83 | int *accel; |
| 84 | int nl = g->g_ll.ll_nlabels; |
| 85 | s->s_accept = 0; |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 86 | accel = PyMem_NEW(int, nl); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 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)) { |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 99 | dfa *d1 = PyGrammar_FindDFA(g, type); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 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)) { |
Guido van Rossum | 7d8b509 | 1991-09-10 14:53:39 +0000 | [diff] [blame] | 107 | #ifdef applec |
Guido van Rossum | 1d5735e | 1994-08-30 08:27:36 +0000 | [diff] [blame] | 108 | #define MPW_881_BUG /* Undefine if bug below is fixed */ |
Guido van Rossum | 7d8b509 | 1991-09-10 14:53:39 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 117 | if (accel[ibit] != -1) |
| 118 | printf("XXX ambiguity!\n"); |
Guido van Rossum | 7d8b509 | 1991-09-10 14:53:39 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 125 | accel[ibit] = a->a_arrow | (1 << 7) | |
| 126 | ((type - NT_OFFSET) << 8); |
Guido van Rossum | 7d8b509 | 1991-09-10 14:53:39 +0000 | [diff] [blame] | 127 | #endif |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 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; |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 142 | s->s_accel = PyMem_NEW(int, nl-k); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 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 | } |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 152 | PyMem_DEL(accel); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 153 | } |