OLD | NEW |
1 | 1 |
2 /* Parser accelerator module */ | 2 /* Parser accelerator module */ |
3 | 3 |
4 /* The parser as originally conceived had disappointing performance. | 4 /* The parser as originally conceived had disappointing performance. |
5 This module does some precomputation that speeds up the selection | 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 | 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 | 7 into a simple indexing operation. The parser now cannot work |
8 without the accelerators installed. Note that the accelerators | 8 without the accelerators installed. Note that the accelerators |
9 are installed dynamically when the parser is initialized, they | 9 are installed dynamically when the parser is initialized, they |
10 are not part of the static data structure written on graminit.[ch] | 10 are not part of the static data structure written on graminit.[ch] |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
77 accel[k] = -1; | 77 accel[k] = -1; |
78 a = s->s_arc; | 78 a = s->s_arc; |
79 for (k = s->s_narcs; --k >= 0; a++) { | 79 for (k = s->s_narcs; --k >= 0; a++) { |
80 int lbl = a->a_lbl; | 80 int lbl = a->a_lbl; |
81 label *l = &g->g_ll.ll_label[lbl]; | 81 label *l = &g->g_ll.ll_label[lbl]; |
82 int type = l->lb_type; | 82 int type = l->lb_type; |
83 if (a->a_arrow >= (1 << 7)) { | 83 if (a->a_arrow >= (1 << 7)) { |
84 printf("XXX too many states!\n"); | 84 printf("XXX too many states!\n"); |
85 continue; | 85 continue; |
86 } | 86 } |
87 if (ISNONTERMINAL(type)) { | 87 if (PYTOK_ISNONTERMINAL(type)) { |
88 dfa *d1 = PyGrammar_FindDFA(g, type); | 88 dfa *d1 = PyGrammar_FindDFA(g, type); |
89 int ibit; | 89 int ibit; |
90 if (type - NT_OFFSET >= (1 << 7)) { | 90 if (type - PYTOK_NT_OFFSET >= (1 << 7)) { |
91 printf("XXX too high nonterminal number!\n"); | 91 printf("XXX too high nonterminal number!\n"); |
92 continue; | 92 continue; |
93 } | 93 } |
94 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { | 94 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { |
95 if (testbit(d1->d_first, ibit)) { | 95 if (testbit(d1->d_first, ibit)) { |
96 if (accel[ibit] != -1) | 96 if (accel[ibit] != -1) |
97 printf("XXX ambiguity!\n"); | 97 printf("XXX ambiguity!\n"); |
98 accel[ibit] = a->a_arrow | (1 << 7) | | 98 accel[ibit] = a->a_arrow | (1 << 7) | |
99 ((type - NT_OFFSET) << 8); | 99 ((type - PYTOK_NT_OFFSET) << 8); |
100 } | 100 } |
101 } | 101 } |
102 } | 102 } |
103 else if (lbl == EMPTY) | 103 else if (lbl == EMPTY) |
104 s->s_accept = 1; | 104 s->s_accept = 1; |
105 else if (lbl >= 0 && lbl < nl) | 105 else if (lbl >= 0 && lbl < nl) |
106 accel[lbl] = a->a_arrow; | 106 accel[lbl] = a->a_arrow; |
107 } | 107 } |
108 while (nl > 0 && accel[nl-1] == -1) | 108 while (nl > 0 && accel[nl-1] == -1) |
109 nl--; | 109 nl--; |
110 for (k = 0; k < nl && accel[k] == -1;) | 110 for (k = 0; k < nl && accel[k] == -1;) |
111 k++; | 111 k++; |
112 if (k < nl) { | 112 if (k < nl) { |
113 int i; | 113 int i; |
114 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int)); | 114 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int)); |
115 if (s->s_accel == NULL) { | 115 if (s->s_accel == NULL) { |
116 fprintf(stderr, "no mem to add parser accelerators\n"); | 116 fprintf(stderr, "no mem to add parser accelerators\n"); |
117 exit(1); | 117 exit(1); |
118 } | 118 } |
119 s->s_lower = k; | 119 s->s_lower = k; |
120 s->s_upper = nl; | 120 s->s_upper = nl; |
121 for (i = 0; k < nl; i++, k++) | 121 for (i = 0; k < nl; i++, k++) |
122 s->s_accel[i] = accel[k]; | 122 s->s_accel[i] = accel[k]; |
123 } | 123 } |
124 PyObject_FREE(accel); | 124 PyObject_FREE(accel); |
125 } | 125 } |
OLD | NEW |