Mercurial > cpython-lru_cache-weakref
annotate Parser/pgen.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 | 85e886db19b0 |
| rev | line source |
|---|---|
| 145 | 1 /*********************************************************** |
|
2060
146890653a57
Added 1995 to copyright message.
Guido van Rossum <guido@python.org>
parents:
2044
diff
changeset
|
2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam, |
|
146890653a57
Added 1995 to copyright message.
Guido van Rossum <guido@python.org>
parents:
2044
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 generator */ |
| 86 | 33 /* XXX This file is not yet fully PROTOized */ |
| 6 | 34 |
| 35 /* For a description, see the comments at end of this file */ | |
| 36 | |
| 86 | 37 #include "pgenheaders.h" |
| 6 | 38 #include "assert.h" |
| 39 #include "token.h" | |
| 40 #include "node.h" | |
| 41 #include "grammar.h" | |
| 42 #include "metagrammar.h" | |
| 43 #include "pgen.h" | |
| 44 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
45 extern int Py_DebugFlag; |
| 6 | 46 |
| 47 | |
| 48 /* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */ | |
| 49 | |
| 50 typedef struct _nfaarc { | |
| 51 int ar_label; | |
| 52 int ar_arrow; | |
| 53 } nfaarc; | |
| 54 | |
| 55 typedef struct _nfastate { | |
| 56 int st_narcs; | |
| 57 nfaarc *st_arc; | |
| 58 } nfastate; | |
| 59 | |
| 60 typedef struct _nfa { | |
| 61 int nf_type; | |
| 62 char *nf_name; | |
| 63 int nf_nstates; | |
| 64 nfastate *nf_state; | |
| 65 int nf_start, nf_finish; | |
| 66 } nfa; | |
| 67 | |
|
170
ee0a32fd4567
Added forward declarations.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
68 /* Forward */ |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
69 static void compile_rhs Py_PROTO((labellist *ll, |
| 4577 | 70 nfa *nf, node *n, int *pa, int *pb)); |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
71 static void compile_alt Py_PROTO((labellist *ll, |
| 4577 | 72 nfa *nf, node *n, int *pa, int *pb)); |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
73 static void compile_item Py_PROTO((labellist *ll, |
| 4577 | 74 nfa *nf, node *n, int *pa, int *pb)); |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
75 static void compile_atom Py_PROTO((labellist *ll, |
| 4577 | 76 nfa *nf, node *n, int *pa, int *pb)); |
|
170
ee0a32fd4567
Added forward declarations.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
77 |
| 6 | 78 static int |
| 79 addnfastate(nf) | |
| 80 nfa *nf; | |
| 81 { | |
| 82 nfastate *st; | |
| 83 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
84 PyMem_RESIZE(nf->nf_state, nfastate, nf->nf_nstates + 1); |
| 6 | 85 if (nf->nf_state == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
86 Py_FatalError("out of mem"); |
| 6 | 87 st = &nf->nf_state[nf->nf_nstates++]; |
| 88 st->st_narcs = 0; | |
| 89 st->st_arc = NULL; | |
| 90 return st - nf->nf_state; | |
| 91 } | |
| 92 | |
| 93 static void | |
| 94 addnfaarc(nf, from, to, lbl) | |
| 95 nfa *nf; | |
| 96 int from, to, lbl; | |
| 97 { | |
| 98 nfastate *st; | |
| 99 nfaarc *ar; | |
| 100 | |
| 101 st = &nf->nf_state[from]; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
102 PyMem_RESIZE(st->st_arc, nfaarc, st->st_narcs + 1); |
| 6 | 103 if (st->st_arc == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
104 Py_FatalError("out of mem"); |
| 6 | 105 ar = &st->st_arc[st->st_narcs++]; |
| 106 ar->ar_label = lbl; | |
| 107 ar->ar_arrow = to; | |
| 108 } | |
| 109 | |
| 110 static nfa * | |
| 111 newnfa(name) | |
| 112 char *name; | |
| 113 { | |
| 114 nfa *nf; | |
| 115 static type = NT_OFFSET; /* All types will be disjunct */ | |
| 116 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
117 nf = PyMem_NEW(nfa, 1); |
| 6 | 118 if (nf == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
119 Py_FatalError("no mem for new nfa"); |
| 6 | 120 nf->nf_type = type++; |
| 121 nf->nf_name = name; /* XXX strdup(name) ??? */ | |
| 122 nf->nf_nstates = 0; | |
| 123 nf->nf_state = NULL; | |
| 124 nf->nf_start = nf->nf_finish = -1; | |
| 125 return nf; | |
| 126 } | |
| 127 | |
| 128 typedef struct _nfagrammar { | |
| 129 int gr_nnfas; | |
| 130 nfa **gr_nfa; | |
| 131 labellist gr_ll; | |
| 132 } nfagrammar; | |
| 133 | |
|
170
ee0a32fd4567
Added forward declarations.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
134 /* Forward */ |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
135 static void compile_rule Py_PROTO((nfagrammar *gr, node *n)); |
|
170
ee0a32fd4567
Added forward declarations.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
136 |
| 6 | 137 static nfagrammar * |
| 138 newnfagrammar() | |
| 139 { | |
| 140 nfagrammar *gr; | |
| 141 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
142 gr = PyMem_NEW(nfagrammar, 1); |
| 6 | 143 if (gr == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
144 Py_FatalError("no mem for new nfa grammar"); |
| 6 | 145 gr->gr_nnfas = 0; |
| 146 gr->gr_nfa = NULL; | |
| 147 gr->gr_ll.ll_nlabels = 0; | |
| 148 gr->gr_ll.ll_label = NULL; | |
| 149 addlabel(&gr->gr_ll, ENDMARKER, "EMPTY"); | |
| 150 return gr; | |
| 151 } | |
| 152 | |
| 153 static nfa * | |
| 154 addnfa(gr, name) | |
| 155 nfagrammar *gr; | |
| 156 char *name; | |
| 157 { | |
| 158 nfa *nf; | |
| 159 | |
| 160 nf = newnfa(name); | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
161 PyMem_RESIZE(gr->gr_nfa, nfa *, gr->gr_nnfas + 1); |
| 6 | 162 if (gr->gr_nfa == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
163 Py_FatalError("out of mem"); |
| 6 | 164 gr->gr_nfa[gr->gr_nnfas++] = nf; |
| 165 addlabel(&gr->gr_ll, NAME, nf->nf_name); | |
| 166 return nf; | |
| 167 } | |
| 168 | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4577
diff
changeset
|
169 #ifdef Py_DEBUG |
| 6 | 170 |
| 171 static char REQNFMT[] = "metacompile: less than %d children\n"; | |
| 172 | |
| 173 #define REQN(i, count) \ | |
| 174 if (i < count) { \ | |
| 175 fprintf(stderr, REQNFMT, count); \ | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
176 Py_FatalError("REQN"); \ |
| 6 | 177 } else |
| 178 | |
| 179 #else | |
| 180 #define REQN(i, count) /* empty */ | |
| 181 #endif | |
| 182 | |
| 183 static nfagrammar * | |
| 184 metacompile(n) | |
| 185 node *n; | |
| 186 { | |
| 187 nfagrammar *gr; | |
| 188 int i; | |
| 189 | |
| 190 printf("Compiling (meta-) parse tree into NFA grammar\n"); | |
| 191 gr = newnfagrammar(); | |
| 192 REQ(n, MSTART); | |
| 193 i = n->n_nchildren - 1; /* Last child is ENDMARKER */ | |
| 194 n = n->n_child; | |
| 195 for (; --i >= 0; n++) { | |
| 196 if (n->n_type != NEWLINE) | |
| 197 compile_rule(gr, n); | |
| 198 } | |
| 199 return gr; | |
| 200 } | |
| 201 | |
| 4577 | 202 static void |
| 6 | 203 compile_rule(gr, n) |
| 204 nfagrammar *gr; | |
| 205 node *n; | |
| 206 { | |
| 207 nfa *nf; | |
| 208 | |
| 209 REQ(n, RULE); | |
| 210 REQN(n->n_nchildren, 4); | |
| 211 n = n->n_child; | |
| 212 REQ(n, NAME); | |
| 213 nf = addnfa(gr, n->n_str); | |
| 214 n++; | |
| 215 REQ(n, COLON); | |
| 216 n++; | |
| 217 REQ(n, RHS); | |
| 218 compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish); | |
| 219 n++; | |
| 220 REQ(n, NEWLINE); | |
| 221 } | |
| 222 | |
| 4577 | 223 static void |
| 6 | 224 compile_rhs(ll, nf, n, pa, pb) |
| 225 labellist *ll; | |
| 226 nfa *nf; | |
| 227 node *n; | |
| 228 int *pa, *pb; | |
| 229 { | |
| 230 int i; | |
| 231 int a, b; | |
| 232 | |
| 233 REQ(n, RHS); | |
| 234 i = n->n_nchildren; | |
| 235 REQN(i, 1); | |
| 236 n = n->n_child; | |
| 237 REQ(n, ALT); | |
| 238 compile_alt(ll, nf, n, pa, pb); | |
| 239 if (--i <= 0) | |
| 240 return; | |
| 241 n++; | |
| 242 a = *pa; | |
| 243 b = *pb; | |
| 244 *pa = addnfastate(nf); | |
| 245 *pb = addnfastate(nf); | |
| 246 addnfaarc(nf, *pa, a, EMPTY); | |
| 247 addnfaarc(nf, b, *pb, EMPTY); | |
| 248 for (; --i >= 0; n++) { | |
| 249 REQ(n, VBAR); | |
| 250 REQN(i, 1); | |
| 251 --i; | |
| 252 n++; | |
| 253 REQ(n, ALT); | |
| 254 compile_alt(ll, nf, n, &a, &b); | |
| 255 addnfaarc(nf, *pa, a, EMPTY); | |
| 256 addnfaarc(nf, b, *pb, EMPTY); | |
| 257 } | |
| 258 } | |
| 259 | |
| 4577 | 260 static void |
| 6 | 261 compile_alt(ll, nf, n, pa, pb) |
| 262 labellist *ll; | |
| 263 nfa *nf; | |
| 264 node *n; | |
| 265 int *pa, *pb; | |
| 266 { | |
| 267 int i; | |
| 268 int a, b; | |
| 269 | |
| 270 REQ(n, ALT); | |
| 271 i = n->n_nchildren; | |
| 272 REQN(i, 1); | |
| 273 n = n->n_child; | |
| 274 REQ(n, ITEM); | |
| 275 compile_item(ll, nf, n, pa, pb); | |
| 276 --i; | |
| 277 n++; | |
| 278 for (; --i >= 0; n++) { | |
| 279 if (n->n_type == COMMA) { /* XXX Temporary */ | |
| 280 REQN(i, 1); | |
| 281 --i; | |
| 282 n++; | |
| 283 } | |
| 284 REQ(n, ITEM); | |
| 285 compile_item(ll, nf, n, &a, &b); | |
| 286 addnfaarc(nf, *pb, a, EMPTY); | |
| 287 *pb = b; | |
| 288 } | |
| 289 } | |
| 290 | |
| 4577 | 291 static void |
| 6 | 292 compile_item(ll, nf, n, pa, pb) |
| 293 labellist *ll; | |
| 294 nfa *nf; | |
| 295 node *n; | |
| 296 int *pa, *pb; | |
| 297 { | |
| 298 int i; | |
| 299 int a, b; | |
| 300 | |
| 301 REQ(n, ITEM); | |
| 302 i = n->n_nchildren; | |
| 303 REQN(i, 1); | |
| 304 n = n->n_child; | |
| 305 if (n->n_type == LSQB) { | |
| 306 REQN(i, 3); | |
| 307 n++; | |
| 308 REQ(n, RHS); | |
| 309 *pa = addnfastate(nf); | |
| 310 *pb = addnfastate(nf); | |
| 311 addnfaarc(nf, *pa, *pb, EMPTY); | |
| 312 compile_rhs(ll, nf, n, &a, &b); | |
| 313 addnfaarc(nf, *pa, a, EMPTY); | |
| 314 addnfaarc(nf, b, *pb, EMPTY); | |
| 315 REQN(i, 1); | |
| 316 n++; | |
| 317 REQ(n, RSQB); | |
| 318 } | |
| 319 else { | |
| 320 compile_atom(ll, nf, n, pa, pb); | |
| 321 if (--i <= 0) | |
| 322 return; | |
| 323 n++; | |
| 324 addnfaarc(nf, *pb, *pa, EMPTY); | |
| 325 if (n->n_type == STAR) | |
| 326 *pb = *pa; | |
| 327 else | |
| 328 REQ(n, PLUS); | |
| 329 } | |
| 330 } | |
| 331 | |
| 4577 | 332 static void |
| 6 | 333 compile_atom(ll, nf, n, pa, pb) |
| 334 labellist *ll; | |
| 335 nfa *nf; | |
| 336 node *n; | |
| 337 int *pa, *pb; | |
| 338 { | |
| 339 int i; | |
| 340 | |
| 341 REQ(n, ATOM); | |
| 342 i = n->n_nchildren; | |
| 343 REQN(i, 1); | |
| 344 n = n->n_child; | |
| 345 if (n->n_type == LPAR) { | |
| 346 REQN(i, 3); | |
| 347 n++; | |
| 348 REQ(n, RHS); | |
| 349 compile_rhs(ll, nf, n, pa, pb); | |
| 350 n++; | |
| 351 REQ(n, RPAR); | |
| 352 } | |
| 353 else if (n->n_type == NAME || n->n_type == STRING) { | |
| 354 *pa = addnfastate(nf); | |
| 355 *pb = addnfastate(nf); | |
| 356 addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str)); | |
| 357 } | |
| 358 else | |
| 359 REQ(n, NAME); | |
| 360 } | |
| 361 | |
| 362 static void | |
| 363 dumpstate(ll, nf, istate) | |
| 364 labellist *ll; | |
| 365 nfa *nf; | |
| 366 int istate; | |
| 367 { | |
| 368 nfastate *st; | |
| 369 int i; | |
| 370 nfaarc *ar; | |
| 371 | |
| 372 printf("%c%2d%c", | |
| 373 istate == nf->nf_start ? '*' : ' ', | |
| 374 istate, | |
| 375 istate == nf->nf_finish ? '.' : ' '); | |
| 376 st = &nf->nf_state[istate]; | |
| 377 ar = st->st_arc; | |
| 378 for (i = 0; i < st->st_narcs; i++) { | |
| 379 if (i > 0) | |
| 380 printf("\n "); | |
| 381 printf("-> %2d %s", ar->ar_arrow, | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
382 PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label])); |
| 6 | 383 ar++; |
| 384 } | |
| 385 printf("\n"); | |
| 386 } | |
| 387 | |
| 388 static void | |
| 389 dumpnfa(ll, nf) | |
| 390 labellist *ll; | |
| 391 nfa *nf; | |
| 392 { | |
| 393 int i; | |
| 394 | |
| 395 printf("NFA '%s' has %d states; start %d, finish %d\n", | |
| 396 nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish); | |
| 397 for (i = 0; i < nf->nf_nstates; i++) | |
| 398 dumpstate(ll, nf, i); | |
| 399 } | |
| 400 | |
| 401 | |
| 402 /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */ | |
| 403 | |
|
2044
281e40652e23
Parser/tokenizer.c (tok_nextc): zap tok->buf after freeing;
Guido van Rossum <guido@python.org>
parents:
1848
diff
changeset
|
404 static void |
| 6 | 405 addclosure(ss, nf, istate) |
| 406 bitset ss; | |
| 407 nfa *nf; | |
| 408 int istate; | |
| 409 { | |
| 410 if (addbit(ss, istate)) { | |
| 411 nfastate *st = &nf->nf_state[istate]; | |
| 412 nfaarc *ar = st->st_arc; | |
| 413 int i; | |
| 414 | |
| 415 for (i = st->st_narcs; --i >= 0; ) { | |
| 416 if (ar->ar_label == EMPTY) | |
| 417 addclosure(ss, nf, ar->ar_arrow); | |
| 418 ar++; | |
| 419 } | |
| 420 } | |
| 421 } | |
| 422 | |
| 423 typedef struct _ss_arc { | |
| 424 bitset sa_bitset; | |
| 425 int sa_arrow; | |
| 426 int sa_label; | |
| 427 } ss_arc; | |
| 428 | |
| 429 typedef struct _ss_state { | |
| 430 bitset ss_ss; | |
| 431 int ss_narcs; | |
| 432 ss_arc *ss_arc; | |
| 433 int ss_deleted; | |
| 434 int ss_finish; | |
| 435 int ss_rename; | |
| 436 } ss_state; | |
| 437 | |
| 438 typedef struct _ss_dfa { | |
| 439 int sd_nstates; | |
| 440 ss_state *sd_state; | |
| 441 } ss_dfa; | |
| 442 | |
|
170
ee0a32fd4567
Added forward declarations.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
443 /* Forward */ |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
444 static void printssdfa Py_PROTO((int xx_nstates, ss_state *xx_state, int nbits, |
| 4577 | 445 labellist *ll, char *msg)); |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
446 static void simplify Py_PROTO((int xx_nstates, ss_state *xx_state)); |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
447 static void convert Py_PROTO((dfa *d, int xx_nstates, ss_state *xx_state)); |
|
170
ee0a32fd4567
Added forward declarations.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
448 |
| 4577 | 449 static void |
| 6 | 450 makedfa(gr, nf, d) |
| 451 nfagrammar *gr; | |
| 452 nfa *nf; | |
| 453 dfa *d; | |
| 454 { | |
| 455 int nbits = nf->nf_nstates; | |
| 456 bitset ss; | |
| 457 int xx_nstates; | |
| 458 ss_state *xx_state, *yy; | |
| 459 ss_arc *zz; | |
| 460 int istate, jstate, iarc, jarc, ibit; | |
| 461 nfastate *st; | |
| 462 nfaarc *ar; | |
| 463 | |
| 464 ss = newbitset(nbits); | |
| 465 addclosure(ss, nf, nf->nf_start); | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
466 xx_state = PyMem_NEW(ss_state, 1); |
| 6 | 467 if (xx_state == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
468 Py_FatalError("no mem for xx_state in makedfa"); |
| 6 | 469 xx_nstates = 1; |
| 470 yy = &xx_state[0]; | |
| 471 yy->ss_ss = ss; | |
| 472 yy->ss_narcs = 0; | |
| 473 yy->ss_arc = NULL; | |
| 474 yy->ss_deleted = 0; | |
| 475 yy->ss_finish = testbit(ss, nf->nf_finish); | |
| 476 if (yy->ss_finish) | |
| 477 printf("Error: nonterminal '%s' may produce empty.\n", | |
| 478 nf->nf_name); | |
| 479 | |
| 480 /* This algorithm is from a book written before | |
| 481 the invention of structured programming... */ | |
| 482 | |
| 483 /* For each unmarked state... */ | |
| 484 for (istate = 0; istate < xx_nstates; ++istate) { | |
| 485 yy = &xx_state[istate]; | |
| 486 ss = yy->ss_ss; | |
| 487 /* For all its states... */ | |
| 488 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) { | |
| 489 if (!testbit(ss, ibit)) | |
| 490 continue; | |
| 491 st = &nf->nf_state[ibit]; | |
| 492 /* For all non-empty arcs from this state... */ | |
| 493 for (iarc = 0; iarc < st->st_narcs; iarc++) { | |
| 494 ar = &st->st_arc[iarc]; | |
| 495 if (ar->ar_label == EMPTY) | |
| 496 continue; | |
| 497 /* Look up in list of arcs from this state */ | |
| 498 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) { | |
| 499 zz = &yy->ss_arc[jarc]; | |
| 500 if (ar->ar_label == zz->sa_label) | |
| 501 goto found; | |
| 502 } | |
| 503 /* Add new arc for this state */ | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
504 PyMem_RESIZE(yy->ss_arc, ss_arc, |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
505 yy->ss_narcs + 1); |
| 6 | 506 if (yy->ss_arc == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
507 Py_FatalError("out of mem"); |
| 6 | 508 zz = &yy->ss_arc[yy->ss_narcs++]; |
| 509 zz->sa_label = ar->ar_label; | |
| 510 zz->sa_bitset = newbitset(nbits); | |
| 511 zz->sa_arrow = -1; | |
| 512 found: ; | |
| 513 /* Add destination */ | |
| 514 addclosure(zz->sa_bitset, nf, ar->ar_arrow); | |
| 515 } | |
| 516 } | |
| 517 /* Now look up all the arrow states */ | |
| 518 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) { | |
| 519 zz = &xx_state[istate].ss_arc[jarc]; | |
| 520 for (jstate = 0; jstate < xx_nstates; jstate++) { | |
| 521 if (samebitset(zz->sa_bitset, | |
| 522 xx_state[jstate].ss_ss, nbits)) { | |
| 523 zz->sa_arrow = jstate; | |
| 524 goto done; | |
| 525 } | |
| 526 } | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
527 PyMem_RESIZE(xx_state, ss_state, xx_nstates + 1); |
| 6 | 528 if (xx_state == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
529 Py_FatalError("out of mem"); |
| 6 | 530 zz->sa_arrow = xx_nstates; |
| 531 yy = &xx_state[xx_nstates++]; | |
| 532 yy->ss_ss = zz->sa_bitset; | |
| 533 yy->ss_narcs = 0; | |
| 534 yy->ss_arc = NULL; | |
| 535 yy->ss_deleted = 0; | |
| 536 yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish); | |
| 537 done: ; | |
| 538 } | |
| 539 } | |
| 540 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
541 if (Py_DebugFlag) |
| 6 | 542 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll, |
| 543 "before minimizing"); | |
| 544 | |
| 545 simplify(xx_nstates, xx_state); | |
| 546 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
547 if (Py_DebugFlag) |
| 6 | 548 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll, |
| 549 "after minimizing"); | |
| 550 | |
| 551 convert(d, xx_nstates, xx_state); | |
| 552 | |
| 553 /* XXX cleanup */ | |
| 554 } | |
| 555 | |
| 4577 | 556 static void |
| 6 | 557 printssdfa(xx_nstates, xx_state, nbits, ll, msg) |
| 558 int xx_nstates; | |
| 559 ss_state *xx_state; | |
| 560 int nbits; | |
| 561 labellist *ll; | |
| 562 char *msg; | |
| 563 { | |
| 564 int i, ibit, iarc; | |
| 565 ss_state *yy; | |
| 566 ss_arc *zz; | |
| 567 | |
| 568 printf("Subset DFA %s\n", msg); | |
| 569 for (i = 0; i < xx_nstates; i++) { | |
| 570 yy = &xx_state[i]; | |
| 571 if (yy->ss_deleted) | |
| 572 continue; | |
| 573 printf(" Subset %d", i); | |
| 574 if (yy->ss_finish) | |
| 575 printf(" (finish)"); | |
| 576 printf(" { "); | |
| 577 for (ibit = 0; ibit < nbits; ibit++) { | |
| 578 if (testbit(yy->ss_ss, ibit)) | |
| 579 printf("%d ", ibit); | |
| 580 } | |
| 581 printf("}\n"); | |
| 582 for (iarc = 0; iarc < yy->ss_narcs; iarc++) { | |
| 583 zz = &yy->ss_arc[iarc]; | |
| 584 printf(" Arc to state %d, label %s\n", | |
| 585 zz->sa_arrow, | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
586 PyGrammar_LabelRepr( |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
587 &ll->ll_label[zz->sa_label])); |
| 6 | 588 } |
| 589 } | |
| 590 } | |
| 591 | |
| 592 | |
| 593 /* PART THREE -- SIMPLIFY DFA */ | |
| 594 | |
| 595 /* Simplify the DFA by repeatedly eliminating states that are | |
| 596 equivalent to another oner. This is NOT Algorithm 3.3 from | |
| 597 [Aho&Ullman 77]. It does not always finds the minimal DFA, | |
| 598 but it does usually make a much smaller one... (For an example | |
| 599 of sub-optimal behaviour, try S: x a b+ | y a b+.) | |
| 600 */ | |
| 601 | |
| 602 static int | |
| 603 samestate(s1, s2) | |
| 604 ss_state *s1, *s2; | |
| 605 { | |
| 606 int i; | |
| 607 | |
| 608 if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish) | |
| 609 return 0; | |
| 610 for (i = 0; i < s1->ss_narcs; i++) { | |
| 611 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow || | |
| 612 s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label) | |
| 613 return 0; | |
| 614 } | |
| 615 return 1; | |
| 616 } | |
| 617 | |
| 618 static void | |
| 619 renamestates(xx_nstates, xx_state, from, to) | |
| 620 int xx_nstates; | |
| 621 ss_state *xx_state; | |
| 622 int from, to; | |
| 623 { | |
| 624 int i, j; | |
| 625 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
626 if (Py_DebugFlag) |
| 6 | 627 printf("Rename state %d to %d.\n", from, to); |
| 628 for (i = 0; i < xx_nstates; i++) { | |
| 629 if (xx_state[i].ss_deleted) | |
| 630 continue; | |
| 631 for (j = 0; j < xx_state[i].ss_narcs; j++) { | |
| 632 if (xx_state[i].ss_arc[j].sa_arrow == from) | |
| 633 xx_state[i].ss_arc[j].sa_arrow = to; | |
| 634 } | |
| 635 } | |
| 636 } | |
| 637 | |
| 4577 | 638 static void |
| 6 | 639 simplify(xx_nstates, xx_state) |
| 640 int xx_nstates; | |
| 641 ss_state *xx_state; | |
| 642 { | |
| 643 int changes; | |
|
2044
281e40652e23
Parser/tokenizer.c (tok_nextc): zap tok->buf after freeing;
Guido van Rossum <guido@python.org>
parents:
1848
diff
changeset
|
644 int i, j; |
| 6 | 645 |
| 646 do { | |
| 647 changes = 0; | |
| 648 for (i = 1; i < xx_nstates; i++) { | |
| 649 if (xx_state[i].ss_deleted) | |
| 650 continue; | |
| 651 for (j = 0; j < i; j++) { | |
| 652 if (xx_state[j].ss_deleted) | |
| 653 continue; | |
| 654 if (samestate(&xx_state[i], &xx_state[j])) { | |
| 655 xx_state[i].ss_deleted++; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
656 renamestates(xx_nstates, xx_state, |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
657 i, j); |
| 6 | 658 changes++; |
| 659 break; | |
| 660 } | |
| 661 } | |
| 662 } | |
| 663 } while (changes); | |
| 664 } | |
| 665 | |
| 666 | |
| 667 /* PART FOUR -- GENERATE PARSING TABLES */ | |
| 668 | |
| 669 /* Convert the DFA into a grammar that can be used by our parser */ | |
| 670 | |
| 4577 | 671 static void |
| 6 | 672 convert(d, xx_nstates, xx_state) |
| 673 dfa *d; | |
| 674 int xx_nstates; | |
| 675 ss_state *xx_state; | |
| 676 { | |
| 677 int i, j; | |
| 678 ss_state *yy; | |
| 679 ss_arc *zz; | |
| 680 | |
| 681 for (i = 0; i < xx_nstates; i++) { | |
| 682 yy = &xx_state[i]; | |
| 683 if (yy->ss_deleted) | |
| 684 continue; | |
| 685 yy->ss_rename = addstate(d); | |
| 686 } | |
| 687 | |
| 688 for (i = 0; i < xx_nstates; i++) { | |
| 689 yy = &xx_state[i]; | |
| 690 if (yy->ss_deleted) | |
| 691 continue; | |
| 692 for (j = 0; j < yy->ss_narcs; j++) { | |
| 693 zz = &yy->ss_arc[j]; | |
| 694 addarc(d, yy->ss_rename, | |
| 695 xx_state[zz->sa_arrow].ss_rename, | |
| 696 zz->sa_label); | |
| 697 } | |
| 698 if (yy->ss_finish) | |
| 699 addarc(d, yy->ss_rename, yy->ss_rename, 0); | |
| 700 } | |
| 701 | |
| 702 d->d_initial = 0; | |
| 703 } | |
| 704 | |
| 705 | |
| 706 /* PART FIVE -- GLUE IT ALL TOGETHER */ | |
| 707 | |
| 708 static grammar * | |
| 709 maketables(gr) | |
| 710 nfagrammar *gr; | |
| 711 { | |
| 712 int i; | |
| 713 nfa *nf; | |
| 714 dfa *d; | |
| 715 grammar *g; | |
| 716 | |
| 717 if (gr->gr_nnfas == 0) | |
| 718 return NULL; | |
| 719 g = newgrammar(gr->gr_nfa[0]->nf_type); | |
| 720 /* XXX first rule must be start rule */ | |
| 721 g->g_ll = gr->gr_ll; | |
| 722 | |
| 723 for (i = 0; i < gr->gr_nnfas; i++) { | |
| 724 nf = gr->gr_nfa[i]; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
725 if (Py_DebugFlag) { |
| 6 | 726 printf("Dump of NFA for '%s' ...\n", nf->nf_name); |
| 727 dumpnfa(&gr->gr_ll, nf); | |
| 728 } | |
| 729 printf("Making DFA for '%s' ...\n", nf->nf_name); | |
| 730 d = adddfa(g, nf->nf_type, nf->nf_name); | |
| 731 makedfa(gr, gr->gr_nfa[i], d); | |
| 732 } | |
| 733 | |
| 734 return g; | |
| 735 } | |
| 736 | |
| 737 grammar * | |
| 738 pgen(n) | |
| 739 node *n; | |
| 740 { | |
| 741 nfagrammar *gr; | |
| 742 grammar *g; | |
| 743 | |
| 744 gr = metacompile(n); | |
| 745 g = maketables(gr); | |
| 746 translatelabels(g); | |
| 747 addfirstsets(g); | |
| 748 return g; | |
| 749 } | |
| 750 | |
| 751 | |
| 752 /* | |
| 753 | |
| 754 Description | |
| 755 ----------- | |
| 756 | |
| 757 Input is a grammar in extended BNF (using * for repetition, + for | |
| 758 at-least-once repetition, [] for optional parts, | for alternatives and | |
| 759 () for grouping). This has already been parsed and turned into a parse | |
| 760 tree. | |
| 761 | |
| 762 Each rule is considered as a regular expression in its own right. | |
| 763 It is turned into a Non-deterministic Finite Automaton (NFA), which | |
| 764 is then turned into a Deterministic Finite Automaton (DFA), which is then | |
| 765 optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3, | |
| 766 or similar compiler books (this technique is more often used for lexical | |
| 767 analyzers). | |
| 768 | |
| 769 The DFA's are used by the parser as parsing tables in a special way | |
| 770 that's probably unique. Before they are usable, the FIRST sets of all | |
| 771 non-terminals are computed. | |
| 772 | |
| 773 Reference | |
| 774 --------- | |
| 775 | |
| 776 [Aho&Ullman 77] | |
| 777 Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977 | |
| 778 (first edition) | |
| 779 | |
| 780 */ |