]>
Commit | Line | Data |
---|---|---|
c8042e10 DM |
1 | \r |
2 | /* Parser accelerator module */\r | |
3 | \r | |
4 | /* The parser as originally conceived had disappointing performance.\r | |
5 | This module does some precomputation that speeds up the selection\r | |
6 | of a DFA based upon a token, turning a search through an array\r | |
7 | into a simple indexing operation. The parser now cannot work\r | |
8 | without the accelerators installed. Note that the accelerators\r | |
9 | are installed dynamically when the parser is initialized, they\r | |
10 | are not part of the static data structure written on graminit.[ch]\r | |
11 | by the parser generator. */\r | |
12 | \r | |
13 | #include "pgenheaders.h"\r | |
14 | #include "grammar.h"\r | |
15 | #include "node.h"\r | |
16 | #include "token.h"\r | |
17 | #include "parser.h"\r | |
18 | \r | |
19 | /* Forward references */\r | |
20 | static void fixdfa(grammar *, dfa *);\r | |
21 | static void fixstate(grammar *, state *);\r | |
22 | \r | |
23 | void\r | |
24 | PyGrammar_AddAccelerators(grammar *g)\r | |
25 | {\r | |
26 | dfa *d;\r | |
27 | int i;\r | |
28 | d = g->g_dfa;\r | |
29 | for (i = g->g_ndfas; --i >= 0; d++)\r | |
30 | fixdfa(g, d);\r | |
31 | g->g_accel = 1;\r | |
32 | }\r | |
33 | \r | |
34 | void\r | |
35 | PyGrammar_RemoveAccelerators(grammar *g)\r | |
36 | {\r | |
37 | dfa *d;\r | |
38 | int i;\r | |
39 | g->g_accel = 0;\r | |
40 | d = g->g_dfa;\r | |
41 | for (i = g->g_ndfas; --i >= 0; d++) {\r | |
42 | state *s;\r | |
43 | int j;\r | |
44 | s = d->d_state;\r | |
45 | for (j = 0; j < d->d_nstates; j++, s++) {\r | |
46 | if (s->s_accel)\r | |
47 | PyObject_FREE(s->s_accel);\r | |
48 | s->s_accel = NULL;\r | |
49 | }\r | |
50 | }\r | |
51 | }\r | |
52 | \r | |
53 | static void\r | |
54 | fixdfa(grammar *g, dfa *d)\r | |
55 | {\r | |
56 | state *s;\r | |
57 | int j;\r | |
58 | s = d->d_state;\r | |
59 | for (j = 0; j < d->d_nstates; j++, s++)\r | |
60 | fixstate(g, s);\r | |
61 | }\r | |
62 | \r | |
63 | static void\r | |
64 | fixstate(grammar *g, state *s)\r | |
65 | {\r | |
66 | arc *a;\r | |
67 | int k;\r | |
68 | int *accel;\r | |
69 | int nl = g->g_ll.ll_nlabels;\r | |
70 | s->s_accept = 0;\r | |
71 | accel = (int *) PyObject_MALLOC(nl * sizeof(int));\r | |
72 | if (accel == NULL) {\r | |
73 | fprintf(stderr, "no mem to build parser accelerators\n");\r | |
74 | exit(1);\r | |
75 | }\r | |
76 | for (k = 0; k < nl; k++)\r | |
77 | accel[k] = -1;\r | |
78 | a = s->s_arc;\r | |
79 | for (k = s->s_narcs; --k >= 0; a++) {\r | |
80 | int lbl = a->a_lbl;\r | |
81 | label *l = &g->g_ll.ll_label[lbl];\r | |
82 | int type = l->lb_type;\r | |
83 | if (a->a_arrow >= (1 << 7)) {\r | |
84 | printf("XXX too many states!\n");\r | |
85 | continue;\r | |
86 | }\r | |
87 | if (ISNONTERMINAL(type)) {\r | |
88 | dfa *d1 = PyGrammar_FindDFA(g, type);\r | |
89 | int ibit;\r | |
90 | if (type - NT_OFFSET >= (1 << 7)) {\r | |
91 | printf("XXX too high nonterminal number!\n");\r | |
92 | continue;\r | |
93 | }\r | |
94 | for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {\r | |
95 | if (testbit(d1->d_first, ibit)) {\r | |
96 | if (accel[ibit] != -1)\r | |
97 | printf("XXX ambiguity!\n");\r | |
98 | accel[ibit] = a->a_arrow | (1 << 7) |\r | |
99 | ((type - NT_OFFSET) << 8);\r | |
100 | }\r | |
101 | }\r | |
102 | }\r | |
103 | else if (lbl == EMPTY)\r | |
104 | s->s_accept = 1;\r | |
105 | else if (lbl >= 0 && lbl < nl)\r | |
106 | accel[lbl] = a->a_arrow;\r | |
107 | }\r | |
108 | while (nl > 0 && accel[nl-1] == -1)\r | |
109 | nl--;\r | |
110 | for (k = 0; k < nl && accel[k] == -1;)\r | |
111 | k++;\r | |
112 | if (k < nl) {\r | |
113 | int i;\r | |
114 | s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));\r | |
115 | if (s->s_accel == NULL) {\r | |
116 | fprintf(stderr, "no mem to add parser accelerators\n");\r | |
117 | exit(1);\r | |
118 | }\r | |
119 | s->s_lower = k;\r | |
120 | s->s_upper = nl;\r | |
121 | for (i = 0; k < nl; i++, k++)\r | |
122 | s->s_accel[i] = accel[k];\r | |
123 | }\r | |
124 | PyObject_FREE(accel);\r | |
125 | }\r |