Mercurial > cpython-lru_cache-weakref
annotate Parser/firstsets.c @ 17322:bd110eadc19a legacy-trunk
One-liner critical fix from Jim Fulton: Eric's string-method crusade
got the order backwards in a line (for .find()).
| author | Tim Peters <tim.peters@gmail.com> |
|---|---|
| date | Thu, 05 Apr 2001 22:26:23 +0000 |
| parents | 6f6f965c5e2d |
| children | 5780724470ee |
| rev | line source |
|---|---|
| 145 | 1 |
| 6 | 2 /* Computation of FIRST stets */ |
| 3 | |
| 86 | 4 #include "pgenheaders.h" |
| 6 | 5 #include "grammar.h" |
| 6 #include "token.h" | |
| 7 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
8 extern int Py_DebugFlag; |
| 6 | 9 |
| 86 | 10 /* Forward */ |
|
13447
a89f7f268de4
Nuke all remaining occurrences of Py_PROTO and Py_FPROTO.
Tim Peters <tim.peters@gmail.com>
parents:
13256
diff
changeset
|
11 static void calcfirstset(grammar *, dfa *); |
| 86 | 12 |
| 13 void | |
| 13659 | 14 addfirstsets(grammar *g) |
| 86 | 15 { |
| 16 int i; | |
| 17 dfa *d; | |
| 18 | |
| 19 printf("Adding FIRST sets ...\n"); | |
| 20 for (i = 0; i < g->g_ndfas; i++) { | |
| 21 d = &g->g_dfa[i]; | |
| 22 if (d->d_first == NULL) | |
| 23 calcfirstset(g, d); | |
| 24 } | |
| 25 } | |
| 26 | |
| 6 | 27 static void |
| 13659 | 28 calcfirstset(grammar *g, dfa *d) |
| 6 | 29 { |
| 30 int i, j; | |
| 31 state *s; | |
| 32 arc *a; | |
| 33 int nsyms; | |
| 34 int *sym; | |
| 35 int nbits; | |
| 36 static bitset dummy; | |
| 37 bitset result; | |
| 38 int type; | |
| 39 dfa *d1; | |
| 40 label *l0; | |
| 41 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
42 if (Py_DebugFlag) |
| 6 | 43 printf("Calculate FIRST set for '%s'\n", d->d_name); |
| 44 | |
| 45 if (dummy == NULL) | |
| 46 dummy = newbitset(1); | |
| 47 if (d->d_first == dummy) { | |
| 48 fprintf(stderr, "Left-recursion for '%s'\n", d->d_name); | |
| 49 return; | |
| 50 } | |
| 51 if (d->d_first != NULL) { | |
| 52 fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n", | |
| 53 d->d_name); | |
| 54 } | |
| 55 d->d_first = dummy; | |
| 56 | |
| 57 l0 = g->g_ll.ll_label; | |
| 58 nbits = g->g_ll.ll_nlabels; | |
| 59 result = newbitset(nbits); | |
| 60 | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
61 sym = PyMem_NEW(int, 1); |
| 6 | 62 if (sym == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
63 Py_FatalError("no mem for new sym in calcfirstset"); |
| 6 | 64 nsyms = 1; |
| 65 sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL); | |
| 66 | |
| 67 s = &d->d_state[d->d_initial]; | |
| 68 for (i = 0; i < s->s_narcs; i++) { | |
| 69 a = &s->s_arc[i]; | |
| 70 for (j = 0; j < nsyms; j++) { | |
| 71 if (sym[j] == a->a_lbl) | |
| 72 break; | |
| 73 } | |
| 74 if (j >= nsyms) { /* New label */ | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
75 PyMem_RESIZE(sym, int, nsyms + 1); |
| 6 | 76 if (sym == NULL) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
77 Py_FatalError( |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
78 "no mem to resize sym in calcfirstset"); |
| 6 | 79 sym[nsyms++] = a->a_lbl; |
| 80 type = l0[a->a_lbl].lb_type; | |
| 81 if (ISNONTERMINAL(type)) { | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
82 d1 = PyGrammar_FindDFA(g, type); |
| 6 | 83 if (d1->d_first == dummy) { |
| 84 fprintf(stderr, | |
| 85 "Left-recursion below '%s'\n", | |
| 86 d->d_name); | |
| 87 } | |
| 88 else { | |
| 89 if (d1->d_first == NULL) | |
| 90 calcfirstset(g, d1); | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
91 mergebitset(result, |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
92 d1->d_first, nbits); |
| 6 | 93 } |
| 94 } | |
| 95 else if (ISTERMINAL(type)) { | |
| 96 addbit(result, a->a_lbl); | |
| 97 } | |
| 98 } | |
| 99 } | |
| 100 d->d_first = result; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
101 if (Py_DebugFlag) { |
| 6 | 102 printf("FIRST set for '%s': {", d->d_name); |
| 103 for (i = 0; i < nbits; i++) { | |
| 104 if (testbit(result, i)) | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
105 printf(" %s", PyGrammar_LabelRepr(&l0[i])); |
| 6 | 106 } |
| 107 printf(" }\n"); | |
| 108 } | |
| 109 } |