Mercurial > cpython-lru_cache-weakref
annotate Parser/acceler.c @ 28646:193b8aec00ce legacy-trunk
Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to
work. This includes some more code that used to be part of pgen in
the main parser; I'm okay with that. I'll see if the Windows build
needs work next.
| author | Guido van Rossum <guido@python.org> |
|---|---|
| date | Thu, 17 Apr 2003 14:55:42 +0000 |
| parents | 3444005b6527 |
| children | b6c139544c16 |
| rev | line source |
|---|---|
| 145 | 1 |
| 6 | 2 /* Parser accelerator module */ |
| 3 | |
| 86 | 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. */ | |
| 6 | 12 |
| 86 | 13 #include "pgenheaders.h" |
| 6 | 14 #include "grammar.h" |
|
1848
b724599401ff
Merge back to main trunk
Guido van Rossum <guido@python.org>
parents:
1257
diff
changeset
|
15 #include "node.h" |
| 6 | 16 #include "token.h" |
| 86 | 17 #include "parser.h" |
| 18 | |
| 19 /* Forward references */ | |
|
13447
a89f7f268de4
Nuke all remaining occurrences of Py_PROTO and Py_FPROTO.
Tim Peters <tim.peters@gmail.com>
parents:
13256
diff
changeset
|
20 static void fixdfa(grammar *, dfa *); |
|
a89f7f268de4
Nuke all remaining occurrences of Py_PROTO and Py_FPROTO.
Tim Peters <tim.peters@gmail.com>
parents:
13256
diff
changeset
|
21 static void fixstate(grammar *, state *); |
| 86 | 22 |
| 23 void | |
| 13659 | 24 PyGrammar_AddAccelerators(grammar *g) |
| 86 | 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 | |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
34 void |
| 13659 | 35 PyGrammar_RemoveAccelerators(grammar *g) |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
36 { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
37 dfa *d; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
38 int i; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
39 g->g_accel = 0; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
40 d = g->g_dfa; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
41 for (i = g->g_ndfas; --i >= 0; d++) { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
42 state *s; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
43 int j; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
44 s = d->d_state; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
45 for (j = 0; j < d->d_nstates; j++, s++) { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
46 if (s->s_accel) |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
47 PyObject_FREE(s->s_accel); |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
48 s->s_accel = NULL; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
49 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
50 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
51 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
52 |
| 86 | 53 static void |
| 13659 | 54 fixdfa(grammar *g, dfa *d) |
| 86 | 55 { |
| 56 state *s; | |
| 57 int j; | |
| 58 s = d->d_state; | |
| 59 for (j = 0; j < d->d_nstates; j++, s++) | |
| 737 | 60 fixstate(g, s); |
| 86 | 61 } |
| 6 | 62 |
| 63 static void | |
| 13659 | 64 fixstate(grammar *g, state *s) |
| 6 | 65 { |
| 66 arc *a; | |
| 67 int k; | |
| 68 int *accel; | |
| 69 int nl = g->g_ll.ll_nlabels; | |
| 70 s->s_accept = 0; | |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
71 accel = (int *) PyObject_MALLOC(nl * sizeof(int)); |
| 6 | 72 for (k = 0; k < nl; k++) |
| 73 accel[k] = -1; | |
| 74 a = s->s_arc; | |
| 75 for (k = s->s_narcs; --k >= 0; a++) { | |
| 76 int lbl = a->a_lbl; | |
| 77 label *l = &g->g_ll.ll_label[lbl]; | |
| 78 int type = l->lb_type; | |
| 79 if (a->a_arrow >= (1 << 7)) { | |
| 80 printf("XXX too many states!\n"); | |
| 81 continue; | |
| 82 } | |
| 83 if (ISNONTERMINAL(type)) { | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
84 dfa *d1 = PyGrammar_FindDFA(g, type); |
| 6 | 85 int ibit; |
| 86 if (type - NT_OFFSET >= (1 << 7)) { | |
| 87 printf("XXX too high nonterminal number!\n"); | |
| 88 continue; | |
| 89 } | |
| 90 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { | |
| 91 if (testbit(d1->d_first, ibit)) { | |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
92 #ifdef applec |
|
1848
b724599401ff
Merge back to main trunk
Guido van Rossum <guido@python.org>
parents:
1257
diff
changeset
|
93 #define MPW_881_BUG /* Undefine if bug below is fixed */ |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
94 #endif |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
95 #ifdef MPW_881_BUG |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
96 /* In 881 mode MPW 3.1 has a code |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
97 generation bug which seems to |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
98 set the upper bits; fix this by |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
99 explicitly masking them off */ |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
100 int temp; |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
101 #endif |
| 6 | 102 if (accel[ibit] != -1) |
| 103 printf("XXX ambiguity!\n"); | |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
104 #ifdef MPW_881_BUG |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
105 temp = 0xFFFF & |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
106 (a->a_arrow | (1 << 7) | |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
107 ((type - NT_OFFSET) << 8)); |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
108 accel[ibit] = temp; |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
109 #else |
| 6 | 110 accel[ibit] = a->a_arrow | (1 << 7) | |
| 111 ((type - NT_OFFSET) << 8); | |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
112 #endif |
| 6 | 113 } |
| 114 } | |
| 115 } | |
| 116 else if (lbl == EMPTY) | |
| 117 s->s_accept = 1; | |
| 118 else if (lbl >= 0 && lbl < nl) | |
| 119 accel[lbl] = a->a_arrow; | |
| 120 } | |
| 121 while (nl > 0 && accel[nl-1] == -1) | |
| 122 nl--; | |
| 123 for (k = 0; k < nl && accel[k] == -1;) | |
| 124 k++; | |
| 125 if (k < nl) { | |
| 126 int i; | |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
127 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int)); |
| 6 | 128 if (s->s_accel == NULL) { |
| 129 fprintf(stderr, "no mem to add parser accelerators\n"); | |
| 130 exit(1); | |
| 131 } | |
| 132 s->s_lower = k; | |
| 133 s->s_upper = nl; | |
| 134 for (i = 0; k < nl; i++, k++) | |
| 135 s->s_accel[i] = accel[k]; | |
| 136 } | |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
137 PyObject_FREE(accel); |
| 6 | 138 } |