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