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