blob: 9b14263b461ace5d22b40a80d9bc2942978e81af [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002/* Parser accelerator module */
3
Guido van Rossum3f5da241990-12-20 15:06:42 +00004/* 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. */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000012
Guido van Rossum3f5da241990-12-20 15:06:42 +000013#include "pgenheaders.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000014#include "grammar.h"
Guido van Rossum1d5735e1994-08-30 08:27:36 +000015#include "node.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000016#include "token.h"
Guido van Rossum3f5da241990-12-20 15:06:42 +000017#include "parser.h"
18
19/* Forward references */
Tim Petersdbd9ba62000-07-09 03:09:57 +000020static void fixdfa(grammar *, dfa *);
21static void fixstate(grammar *, state *);
Guido van Rossum3f5da241990-12-20 15:06:42 +000022
23void
Thomas Wouters23c9e002000-07-22 19:20:54 +000024PyGrammar_AddAccelerators(grammar *g)
Guido van Rossum3f5da241990-12-20 15:06:42 +000025{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000026 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;
Guido van Rossum3f5da241990-12-20 15:06:42 +000032}
33
Guido van Rossumaee094c1997-08-02 03:02:27 +000034void
Thomas Wouters23c9e002000-07-22 19:20:54 +000035PyGrammar_RemoveAccelerators(grammar *g)
Guido van Rossumaee094c1997-08-02 03:02:27 +000036{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000037 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 }
Guido van Rossumaee094c1997-08-02 03:02:27 +000051}
52
Guido van Rossum3f5da241990-12-20 15:06:42 +000053static void
Thomas Wouters23c9e002000-07-22 19:20:54 +000054fixdfa(grammar *g, dfa *d)
Guido van Rossum3f5da241990-12-20 15:06:42 +000055{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000056 state *s;
57 int j;
58 s = d->d_state;
59 for (j = 0; j < d->d_nstates; j++, s++)
60 fixstate(g, s);
Guido van Rossum3f5da241990-12-20 15:06:42 +000061}
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000062
63static void
Thomas Wouters23c9e002000-07-22 19:20:54 +000064fixstate(grammar *g, state *s)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000065{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000066 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);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000125}