|
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 } |