diff options
Diffstat (limited to 'AppPkg/Applications/Python/Python-2.7.10/Parser/acceler.c')
-rw-r--r-- | AppPkg/Applications/Python/Python-2.7.10/Parser/acceler.c | 125 |
1 files changed, 125 insertions, 0 deletions
diff --git a/AppPkg/Applications/Python/Python-2.7.10/Parser/acceler.c b/AppPkg/Applications/Python/Python-2.7.10/Parser/acceler.c new file mode 100644 index 0000000000..f6036d9739 --- /dev/null +++ b/AppPkg/Applications/Python/Python-2.7.10/Parser/acceler.c @@ -0,0 +1,125 @@ +
+/* Parser accelerator module */
+
+/* The parser as originally conceived had disappointing performance.
+ This module does some precomputation that speeds up the selection
+ of a DFA based upon a token, turning a search through an array
+ into a simple indexing operation. The parser now cannot work
+ without the accelerators installed. Note that the accelerators
+ are installed dynamically when the parser is initialized, they
+ are not part of the static data structure written on graminit.[ch]
+ by the parser generator. */
+
+#include "pgenheaders.h"
+#include "grammar.h"
+#include "node.h"
+#include "token.h"
+#include "parser.h"
+
+/* Forward references */
+static void fixdfa(grammar *, dfa *);
+static void fixstate(grammar *, state *);
+
+void
+PyGrammar_AddAccelerators(grammar *g)
+{
+ dfa *d;
+ int i;
+ d = g->g_dfa;
+ for (i = g->g_ndfas; --i >= 0; d++)
+ fixdfa(g, d);
+ g->g_accel = 1;
+}
+
+void
+PyGrammar_RemoveAccelerators(grammar *g)
+{
+ dfa *d;
+ int i;
+ g->g_accel = 0;
+ d = g->g_dfa;
+ for (i = g->g_ndfas; --i >= 0; d++) {
+ state *s;
+ int j;
+ s = d->d_state;
+ for (j = 0; j < d->d_nstates; j++, s++) {
+ if (s->s_accel)
+ PyObject_FREE(s->s_accel);
+ s->s_accel = NULL;
+ }
+ }
+}
+
+static void
+fixdfa(grammar *g, dfa *d)
+{
+ state *s;
+ int j;
+ s = d->d_state;
+ for (j = 0; j < d->d_nstates; j++, s++)
+ fixstate(g, s);
+}
+
+static void
+fixstate(grammar *g, state *s)
+{
+ arc *a;
+ int k;
+ int *accel;
+ int nl = g->g_ll.ll_nlabels;
+ s->s_accept = 0;
+ accel = (int *) PyObject_MALLOC(nl * sizeof(int));
+ if (accel == NULL) {
+ fprintf(stderr, "no mem to build parser accelerators\n");
+ exit(1);
+ }
+ for (k = 0; k < nl; k++)
+ accel[k] = -1;
+ a = s->s_arc;
+ for (k = s->s_narcs; --k >= 0; a++) {
+ int lbl = a->a_lbl;
+ label *l = &g->g_ll.ll_label[lbl];
+ int type = l->lb_type;
+ if (a->a_arrow >= (1 << 7)) {
+ printf("XXX too many states!\n");
+ continue;
+ }
+ if (ISNONTERMINAL(type)) {
+ dfa *d1 = PyGrammar_FindDFA(g, type);
+ int ibit;
+ if (type - NT_OFFSET >= (1 << 7)) {
+ printf("XXX too high nonterminal number!\n");
+ continue;
+ }
+ for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
+ if (testbit(d1->d_first, ibit)) {
+ if (accel[ibit] != -1)
+ printf("XXX ambiguity!\n");
+ accel[ibit] = a->a_arrow | (1 << 7) |
+ ((type - NT_OFFSET) << 8);
+ }
+ }
+ }
+ else if (lbl == EMPTY)
+ s->s_accept = 1;
+ else if (lbl >= 0 && lbl < nl)
+ accel[lbl] = a->a_arrow;
+ }
+ while (nl > 0 && accel[nl-1] == -1)
+ nl--;
+ for (k = 0; k < nl && accel[k] == -1;)
+ k++;
+ if (k < nl) {
+ int i;
+ s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
+ if (s->s_accel == NULL) {
+ fprintf(stderr, "no mem to add parser accelerators\n");
+ exit(1);
+ }
+ s->s_lower = k;
+ s->s_upper = nl;
+ for (i = 0; k < nl; i++, k++)
+ s->s_accel[i] = accel[k];
+ }
+ PyObject_FREE(accel);
+}
|