1f70e43a073b36c6f6e9894c01025243a77a452d4Guido van Rossum 285a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum/* Parser accelerator module */ 385a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum 43f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum/* The parser as originally conceived had disappointing performance. 53f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum This module does some precomputation that speeds up the selection 63f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum of a DFA based upon a token, turning a search through an array 73f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum into a simple indexing operation. The parser now cannot work 83f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum without the accelerators installed. Note that the accelerators 93f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum are installed dynamically when the parser is initialized, they 103f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum are not part of the static data structure written on graminit.[ch] 113f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum by the parser generator. */ 1285a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum 133f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum#include "pgenheaders.h" 1485a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum#include "grammar.h" 151d5735e84621a7fe68d361fa0e289fa2c3310836Guido van Rossum#include "node.h" 1685a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum#include "token.h" 173f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum#include "parser.h" 183f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum 193f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum/* Forward references */ 20dbd9ba6a6c19c3d06f5684b3384a934f740038dbTim Petersstatic void fixdfa(grammar *, dfa *); 21dbd9ba6a6c19c3d06f5684b3384a934f740038dbTim Petersstatic void fixstate(grammar *, state *); 223f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum 233f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossumvoid 2423c9e0024af99379ae517b016b874d57127e9a97Thomas WoutersPyGrammar_AddAccelerators(grammar *g) 253f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum{ 26c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou dfa *d; 27c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 28c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou d = g->g_dfa; 29c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = g->g_ndfas; --i >= 0; d++) 30c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fixdfa(g, d); 31c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou g->g_accel = 1; 323f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum} 333f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum 34aee094cc60b4b05e28cfd9e1a2add1b97ededbb6Guido van Rossumvoid 3523c9e0024af99379ae517b016b874d57127e9a97Thomas WoutersPyGrammar_RemoveAccelerators(grammar *g) 36aee094cc60b4b05e28cfd9e1a2add1b97ededbb6Guido van Rossum{ 37c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou dfa *d; 38c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 39c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou g->g_accel = 0; 40c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou d = g->g_dfa; 41c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = g->g_ndfas; --i >= 0; d++) { 42c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou state *s; 43c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int j; 44c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s = d->d_state; 45c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (j = 0; j < d->d_nstates; j++, s++) { 46c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (s->s_accel) 47c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_FREE(s->s_accel); 48c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s->s_accel = NULL; 49c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 50c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 51aee094cc60b4b05e28cfd9e1a2add1b97ededbb6Guido van Rossum} 52aee094cc60b4b05e28cfd9e1a2add1b97ededbb6Guido van Rossum 533f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossumstatic void 5423c9e0024af99379ae517b016b874d57127e9a97Thomas Woutersfixdfa(grammar *g, dfa *d) 553f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum{ 56c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou state *s; 57c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int j; 58c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s = d->d_state; 59c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (j = 0; j < d->d_nstates; j++, s++) 60c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fixstate(g, s); 613f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum} 6285a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum 6385a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossumstatic void 6423c9e0024af99379ae517b016b874d57127e9a97Thomas Woutersfixstate(grammar *g, state *s) 6585a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum{ 66c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou arc *a; 67c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int k; 68c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int *accel; 69c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int nl = g->g_ll.ll_nlabels; 70c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s->s_accept = 0; 71c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou accel = (int *) PyObject_MALLOC(nl * sizeof(int)); 72c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (accel == NULL) { 73c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "no mem to build parser accelerators\n"); 74c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou exit(1); 75c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 76c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (k = 0; k < nl; k++) 77c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou accel[k] = -1; 78c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou a = s->s_arc; 79c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (k = s->s_narcs; --k >= 0; a++) { 80c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int lbl = a->a_lbl; 81c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou label *l = &g->g_ll.ll_label[lbl]; 82c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int type = l->lb_type; 83c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (a->a_arrow >= (1 << 7)) { 84c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou printf("XXX too many states!\n"); 85c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 86c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 87c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (ISNONTERMINAL(type)) { 88c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou dfa *d1 = PyGrammar_FindDFA(g, type); 89c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int ibit; 90c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (type - NT_OFFSET >= (1 << 7)) { 91c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou printf("XXX too high nonterminal number!\n"); 92c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou continue; 93c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 94c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { 95c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (testbit(d1->d_first, ibit)) { 96c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (accel[ibit] != -1) 97c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou printf("XXX ambiguity!\n"); 98c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou accel[ibit] = a->a_arrow | (1 << 7) | 99c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou ((type - NT_OFFSET) << 8); 100c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 101c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 102c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 103c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else if (lbl == EMPTY) 104c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s->s_accept = 1; 105c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else if (lbl >= 0 && lbl < nl) 106c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou accel[lbl] = a->a_arrow; 107c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 108c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (nl > 0 && accel[nl-1] == -1) 109c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou nl--; 110c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (k = 0; k < nl && accel[k] == -1;) 111c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou k++; 112c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (k < nl) { 113c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 114c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int)); 115c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (s->s_accel == NULL) { 116c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fprintf(stderr, "no mem to add parser accelerators\n"); 117c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou exit(1); 118c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 119c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s->s_lower = k; 120c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s->s_upper = nl; 121c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = 0; k < nl; i++, k++) 122c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou s->s_accel[i] = accel[k]; 123c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 124c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_FREE(accel); 12585a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum} 126