1 

     2 /* Parser accelerator module */

     3 

     4 /* The parser as originally conceived had disappointing performance.

     5    This module does some precomputation that speeds up the selection

     6    of a DFA based upon a token, turning a search through an array

     7    into a simple indexing operation.  The parser now cannot work

     8    without the accelerators installed.  Note that the accelerators

     9    are installed dynamically when the parser is initialized, they

    10    are not part of the static data structure written on graminit.[ch]

    11    by the parser generator. */

    12 

    13 #include "pgenheaders.h"

    14 #include "grammar.h"

    15 #include "node.h"

    16 #include "token.h"

    17 #include "parser.h"

    18 

    19 /* Forward references */

    20 static void fixdfa(grammar *, dfa *);

    21 static void fixstate(grammar *, state *);

    22 

    23 void

    24 PyGrammar_AddAccelerators(grammar *g)

    25 {

    26 	dfa *d;

    27 	int i;

    28 	d = g->g_dfa;

    29 	for (i = g->g_ndfas; --i >= 0; d++)

    30 		fixdfa(g, d);

    31 	g->g_accel = 1;

    32 }

    33 

    34 void

    35 PyGrammar_RemoveAccelerators(grammar *g)

    36 {

    37 	dfa *d;

    38 	int i;

    39 	g->g_accel = 0;

    40 	d = g->g_dfa;

    41 	for (i = g->g_ndfas; --i >= 0; d++) {

    42 		state *s;

    43 		int j;

    44 		s = d->d_state;

    45 		for (j = 0; j < d->d_nstates; j++, s++) {

    46 			if (s->s_accel)

    47 				PyObject_FREE(s->s_accel);

    48 			s->s_accel = NULL;

    49 		}

    50 	}

    51 }

    52 

    53 static void

    54 fixdfa(grammar *g, dfa *d)

    55 {

    56 	state *s;

    57 	int j;

    58 	s = d->d_state;

    59 	for (j = 0; j < d->d_nstates; j++, s++)

    60 		fixstate(g, s);

    61 }

    62 

    63 static void

    64 fixstate(grammar *g, state *s)

    65 {

    66 	arc *a;

    67 	int k;

    68 	int *accel;

    69 	int nl = g->g_ll.ll_nlabels;

    70 	s->s_accept = 0;

    71 	accel = (int *) PyObject_MALLOC(nl * sizeof(int));

    72 	if (accel == NULL) {

    73 		fprintf(stderr, "no mem to build parser accelerators\n");

    74 		exit(1);

    75 	}

    76 	for (k = 0; k < nl; k++)

    77 		accel[k] = -1;

    78 	a = s->s_arc;

    79 	for (k = s->s_narcs; --k >= 0; a++) {

    80 		int lbl = a->a_lbl;

    81 		label *l = &g->g_ll.ll_label[lbl];

    82 		int type = l->lb_type;

    83 		if (a->a_arrow >= (1 << 7)) {

    84 			printf("XXX too many states!\n");

    85 			continue;

    86 		}

    87 		if (ISNONTERMINAL(type)) {

    88 			dfa *d1 = PyGrammar_FindDFA(g, type);

    89 			int ibit;

    90 			if (type - NT_OFFSET >= (1 << 7)) {

    91 				printf("XXX too high nonterminal number!\n");

    92 				continue;

    93 			}

    94 			for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {

    95 				if (testbit(d1->d_first, ibit)) {

    96 					if (accel[ibit] != -1)

    97 						printf("XXX ambiguity!\n");

    98 					accel[ibit] = a->a_arrow | (1 << 7) |

    99 						((type - NT_OFFSET) << 8);

   100 				}

   101 			}

   102 		}

   103 		else if (lbl == EMPTY)

   104 			s->s_accept = 1;

   105 		else if (lbl >= 0 && lbl < nl)

   106 			accel[lbl] = a->a_arrow;

   107 	}

   108 	while (nl > 0 && accel[nl-1] == -1)

   109 		nl--;

   110 	for (k = 0; k < nl && accel[k] == -1;)

   111 		k++;

   112 	if (k < nl) {

   113 		int i;

   114 		s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));

   115 		if (s->s_accel == NULL) {

   116 			fprintf(stderr, "no mem to add parser accelerators\n");

   117 			exit(1);

   118 		}

   119 		s->s_lower = k;

   120 		s->s_upper = nl;

   121 		for (i = 0; k < nl; i++, k++)

   122 			s->s_accel[i] = accel[k];

   123 	}

   124 	PyObject_FREE(accel);

   125 }