Mercurial > cpython-lru_cache-weakref
annotate Parser/acceler.c @ 5817:48b94de85bf3 legacy-trunk
Extensive changes by AMK.
| author | Guido van Rossum <guido@python.org> |
|---|---|
| date | Thu, 17 Jul 1997 16:29:42 +0000 |
| parents | 1c9a84e0981d |
| children | 08b1e9d847e6 |
| rev | line source |
|---|---|
| 145 | 1 /*********************************************************** |
|
2060
146890653a57
Added 1995 to copyright message.
Guido van Rossum <guido@python.org>
parents:
1848
diff
changeset
|
2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam, |
|
146890653a57
Added 1995 to copyright message.
Guido van Rossum <guido@python.org>
parents:
1848
diff
changeset
|
3 The Netherlands. |
| 145 | 4 |
| 5 All Rights Reserved | |
| 6 | |
|
4503
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
7 Permission to use, copy, modify, and distribute this software and its |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
8 documentation for any purpose and without fee is hereby granted, |
| 145 | 9 provided that the above copyright notice appear in all copies and that |
|
4503
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
10 both that copyright notice and this permission notice appear in |
| 145 | 11 supporting documentation, and that the names of Stichting Mathematisch |
|
4503
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
12 Centrum or CWI or Corporation for National Research Initiatives or |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
13 CNRI not be used in advertising or publicity pertaining to |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
14 distribution of the software without specific, written prior |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
15 permission. |
| 145 | 16 |
|
4503
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
17 While CWI is the initial source for this software, a modified version |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
18 is made available by the Corporation for National Research Initiatives |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
19 (CNRI) at the Internet address ftp://ftp.python.org. |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
20 |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR |
|
65d2d8e67da3
New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents:
2060
diff
changeset
|
28 PERFORMANCE OF THIS SOFTWARE. |
| 145 | 29 |
| 30 ******************************************************************/ | |
| 31 | |
| 6 | 32 /* Parser accelerator module */ |
| 33 | |
| 86 | 34 /* The parser as originally conceived had disappointing performance. |
| 35 This module does some precomputation that speeds up the selection | |
| 36 of a DFA based upon a token, turning a search through an array | |
| 37 into a simple indexing operation. The parser now cannot work | |
| 38 without the accelerators installed. Note that the accelerators | |
| 39 are installed dynamically when the parser is initialized, they | |
| 40 are not part of the static data structure written on graminit.[ch] | |
| 41 by the parser generator. */ | |
| 6 | 42 |
| 86 | 43 #include "pgenheaders.h" |
| 6 | 44 #include "grammar.h" |
|
1848
b724599401ff
Merge back to main trunk
Guido van Rossum <guido@python.org>
parents:
1257
diff
changeset
|
45 #include "node.h" |
| 6 | 46 #include "token.h" |
| 86 | 47 #include "parser.h" |
| 48 | |
| 49 /* Forward references */ | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
50 static void fixdfa Py_PROTO((grammar *, dfa *)); |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
51 static void fixstate Py_PROTO((grammar *, state *)); |
| 86 | 52 |
| 53 void | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
54 PyGrammar_AddAccelerators(g) |
| 86 | 55 grammar *g; |
| 56 { | |
| 57 dfa *d; | |
| 58 int i; | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
59 #ifdef Py_DEBUG |
|
1025
f993197c3a47
Print warnings to stderr and correct spelling
Guido van Rossum <guido@python.org>
parents:
795
diff
changeset
|
60 fprintf(stderr, "Adding parser accelerators ...\n"); |
| 86 | 61 #endif |
| 62 d = g->g_dfa; | |
| 63 for (i = g->g_ndfas; --i >= 0; d++) | |
| 64 fixdfa(g, d); | |
| 65 g->g_accel = 1; | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
66 #ifdef Py_DEBUG |
|
1025
f993197c3a47
Print warnings to stderr and correct spelling
Guido van Rossum <guido@python.org>
parents:
795
diff
changeset
|
67 fprintf(stderr, "Done.\n"); |
| 86 | 68 #endif |
| 69 } | |
| 70 | |
| 71 static void | |
| 72 fixdfa(g, d) | |
| 73 grammar *g; | |
| 74 dfa *d; | |
| 75 { | |
| 76 state *s; | |
| 77 int j; | |
| 78 s = d->d_state; | |
| 79 for (j = 0; j < d->d_nstates; j++, s++) | |
| 737 | 80 fixstate(g, s); |
| 86 | 81 } |
| 6 | 82 |
| 83 static void | |
| 737 | 84 fixstate(g, s) |
| 6 | 85 grammar *g; |
| 86 state *s; | |
| 87 { | |
| 88 arc *a; | |
| 89 int k; | |
| 90 int *accel; | |
| 91 int nl = g->g_ll.ll_nlabels; | |
| 92 s->s_accept = 0; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
93 accel = PyMem_NEW(int, nl); |
| 6 | 94 for (k = 0; k < nl; k++) |
| 95 accel[k] = -1; | |
| 96 a = s->s_arc; | |
| 97 for (k = s->s_narcs; --k >= 0; a++) { | |
| 98 int lbl = a->a_lbl; | |
| 99 label *l = &g->g_ll.ll_label[lbl]; | |
| 100 int type = l->lb_type; | |
| 101 if (a->a_arrow >= (1 << 7)) { | |
| 102 printf("XXX too many states!\n"); | |
| 103 continue; | |
| 104 } | |
| 105 if (ISNONTERMINAL(type)) { | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
106 dfa *d1 = PyGrammar_FindDFA(g, type); |
| 6 | 107 int ibit; |
| 108 if (type - NT_OFFSET >= (1 << 7)) { | |
| 109 printf("XXX too high nonterminal number!\n"); | |
| 110 continue; | |
| 111 } | |
| 112 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { | |
| 113 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
|
114 #ifdef applec |
|
1848
b724599401ff
Merge back to main trunk
Guido van Rossum <guido@python.org>
parents:
1257
diff
changeset
|
115 #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
|
116 #endif |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
117 #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
|
118 /* 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
|
119 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
|
120 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
|
121 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
|
122 int temp; |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
123 #endif |
| 6 | 124 if (accel[ibit] != -1) |
| 125 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
|
126 #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
|
127 temp = 0xFFFF & |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
128 (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
|
129 ((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
|
130 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
|
131 #else |
| 6 | 132 accel[ibit] = a->a_arrow | (1 << 7) | |
| 133 ((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
|
134 #endif |
| 6 | 135 } |
| 136 } | |
| 137 } | |
| 138 else if (lbl == EMPTY) | |
| 139 s->s_accept = 1; | |
| 140 else if (lbl >= 0 && lbl < nl) | |
| 141 accel[lbl] = a->a_arrow; | |
| 142 } | |
| 143 while (nl > 0 && accel[nl-1] == -1) | |
| 144 nl--; | |
| 145 for (k = 0; k < nl && accel[k] == -1;) | |
| 146 k++; | |
| 147 if (k < nl) { | |
| 148 int i; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
149 s->s_accel = PyMem_NEW(int, nl-k); |
| 6 | 150 if (s->s_accel == NULL) { |
| 151 fprintf(stderr, "no mem to add parser accelerators\n"); | |
| 152 exit(1); | |
| 153 } | |
| 154 s->s_lower = k; | |
| 155 s->s_upper = nl; | |
| 156 for (i = 0; k < nl; i++, k++) | |
| 157 s->s_accel[i] = accel[k]; | |
| 158 } | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
159 PyMem_DEL(accel); |
| 6 | 160 } |