Mercurial > cpython-lru_cache-weakref
annotate Parser/firstsets.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 /* Computation of FIRST stets */ |
| 26 | |
| 86 | 27 #include "pgenheaders.h" |
| 6 | 28 #include "grammar.h" |
| 29 #include "token.h" | |
| 30 | |
| 31 extern int debugging; | |
| 32 | |
| 86 | 33 /* Forward */ |
| 34 static void calcfirstset PROTO((grammar *, dfa *)); | |
| 35 | |
| 36 void | |
| 37 addfirstsets(g) | |
| 38 grammar *g; | |
| 39 { | |
| 40 int i; | |
| 41 dfa *d; | |
| 42 | |
| 43 printf("Adding FIRST sets ...\n"); | |
| 44 for (i = 0; i < g->g_ndfas; i++) { | |
| 45 d = &g->g_dfa[i]; | |
| 46 if (d->d_first == NULL) | |
| 47 calcfirstset(g, d); | |
| 48 } | |
| 49 } | |
| 50 | |
| 6 | 51 static void |
| 52 calcfirstset(g, d) | |
| 53 grammar *g; | |
| 54 dfa *d; | |
| 55 { | |
| 56 int i, j; | |
| 57 state *s; | |
| 58 arc *a; | |
| 59 int nsyms; | |
| 60 int *sym; | |
| 61 int nbits; | |
| 62 static bitset dummy; | |
| 63 bitset result; | |
| 64 int type; | |
| 65 dfa *d1; | |
| 66 label *l0; | |
| 67 | |
| 68 if (debugging) | |
| 69 printf("Calculate FIRST set for '%s'\n", d->d_name); | |
| 70 | |
| 71 if (dummy == NULL) | |
| 72 dummy = newbitset(1); | |
| 73 if (d->d_first == dummy) { | |
| 74 fprintf(stderr, "Left-recursion for '%s'\n", d->d_name); | |
| 75 return; | |
| 76 } | |
| 77 if (d->d_first != NULL) { | |
| 78 fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n", | |
| 79 d->d_name); | |
| 80 } | |
| 81 d->d_first = dummy; | |
| 82 | |
| 83 l0 = g->g_ll.ll_label; | |
| 84 nbits = g->g_ll.ll_nlabels; | |
| 85 result = newbitset(nbits); | |
| 86 | |
| 87 sym = NEW(int, 1); | |
| 88 if (sym == NULL) | |
| 89 fatal("no mem for new sym in calcfirstset"); | |
| 90 nsyms = 1; | |
| 91 sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL); | |
| 92 | |
| 93 s = &d->d_state[d->d_initial]; | |
| 94 for (i = 0; i < s->s_narcs; i++) { | |
| 95 a = &s->s_arc[i]; | |
| 96 for (j = 0; j < nsyms; j++) { | |
| 97 if (sym[j] == a->a_lbl) | |
| 98 break; | |
| 99 } | |
| 100 if (j >= nsyms) { /* New label */ | |
| 101 RESIZE(sym, int, nsyms + 1); | |
| 102 if (sym == NULL) | |
| 103 fatal("no mem to resize sym in calcfirstset"); | |
| 104 sym[nsyms++] = a->a_lbl; | |
| 105 type = l0[a->a_lbl].lb_type; | |
| 106 if (ISNONTERMINAL(type)) { | |
| 107 d1 = finddfa(g, type); | |
| 108 if (d1->d_first == dummy) { | |
| 109 fprintf(stderr, | |
| 110 "Left-recursion below '%s'\n", | |
| 111 d->d_name); | |
| 112 } | |
| 113 else { | |
| 114 if (d1->d_first == NULL) | |
| 115 calcfirstset(g, d1); | |
| 116 mergebitset(result, d1->d_first, nbits); | |
| 117 } | |
| 118 } | |
| 119 else if (ISTERMINAL(type)) { | |
| 120 addbit(result, a->a_lbl); | |
| 121 } | |
| 122 } | |
| 123 } | |
| 124 d->d_first = result; | |
| 125 if (debugging) { | |
| 126 printf("FIRST set for '%s': {", d->d_name); | |
| 127 for (i = 0; i < nbits; i++) { | |
| 128 if (testbit(result, i)) | |
| 129 printf(" %s", labelrepr(&l0[i])); | |
| 130 } | |
| 131 printf(" }\n"); | |
| 132 } | |
| 133 } |