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