blob: 57bdb967c168e95effa4dfc550b61623778eb8bd [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001/***********************************************************
Guido van Rossum1d5735e1994-08-30 08:27:36 +00002Copyright 1991, 1992, 1993, 1994 by Stichting Mathematisch Centrum,
Guido van Rossum9bfef441993-03-29 10:43:31 +00003Amsterdam, The Netherlands.
Guido van Rossumf70e43a1991-02-19 12:39:46 +00004
5 All Rights Reserved
6
7Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
9provided that the above copyright notice appear in all copies and that
10both that copyright notice and this permission notice appear in
11supporting documentation, and that the names of Stichting Mathematisch
12Centrum or CWI not be used in advertising or publicity pertaining to
13distribution of the software without specific, written prior permission.
14
15STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
16THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
17FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
18FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
19WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
20ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
21OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22
23******************************************************************/
24
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000025/* Computation of FIRST stets */
26
Guido van Rossum3f5da241990-12-20 15:06:42 +000027#include "pgenheaders.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000028#include "grammar.h"
29#include "token.h"
30
31extern int debugging;
32
Guido van Rossum3f5da241990-12-20 15:06:42 +000033/* Forward */
34static void calcfirstset PROTO((grammar *, dfa *));
35
36void
37addfirstsets(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
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000051static void
52calcfirstset(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}