1 
2 /* Computation of FIRST stets */
3 
4 #include "pgenheaders.h"
5 #include "grammar.h"
6 #include "token.h"
7 
8 extern int Py_DebugFlag;
9 
10 /* Forward */
11 static void calcfirstset(grammar *, dfa *);
12 
13 void
addfirstsets(grammar * g)14 addfirstsets(grammar *g)
15 {
16     int i;
17     dfa *d;
18 
19     if (Py_DebugFlag)
20         printf("Adding FIRST sets ...\n");
21     for (i = 0; i < g->g_ndfas; i++) {
22         d = &g->g_dfa[i];
23         if (d->d_first == NULL)
24             calcfirstset(g, d);
25     }
26 }
27 
28 static void
calcfirstset(grammar * g,dfa * d)29 calcfirstset(grammar *g, dfa *d)
30 {
31     int i, j;
32     state *s;
33     arc *a;
34     int nsyms;
35     int *sym;
36     int nbits;
37     static bitset dummy;
38     bitset result;
39     int type;
40     dfa *d1;
41     label *l0;
42 
43     if (Py_DebugFlag)
44         printf("Calculate FIRST set for '%s'\n", d->d_name);
45 
46     if (dummy == NULL)
47         dummy = newbitset(1);
48     if (d->d_first == dummy) {
49         fprintf(stderr, "Left-recursion for '%s'\n", d->d_name);
50         return;
51     }
52     if (d->d_first != NULL) {
53         fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n",
54             d->d_name);
55     }
56     d->d_first = dummy;
57 
58     l0 = g->g_ll.ll_label;
59     nbits = g->g_ll.ll_nlabels;
60     result = newbitset(nbits);
61 
62     sym = (int *)PyObject_MALLOC(sizeof(int));
63     if (sym == NULL)
64         Py_FatalError("no mem for new sym in calcfirstset");
65     nsyms = 1;
66     sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL);
67 
68     s = &d->d_state[d->d_initial];
69     for (i = 0; i < s->s_narcs; i++) {
70         a = &s->s_arc[i];
71         for (j = 0; j < nsyms; j++) {
72             if (sym[j] == a->a_lbl)
73                 break;
74         }
75         if (j >= nsyms) { /* New label */
76             sym = (int *)PyObject_REALLOC(sym,
77                                     sizeof(int) * (nsyms + 1));
78             if (sym == NULL)
79                 Py_FatalError(
80                     "no mem to resize sym in calcfirstset");
81             sym[nsyms++] = a->a_lbl;
82             type = l0[a->a_lbl].lb_type;
83             if (ISNONTERMINAL(type)) {
84                 d1 = PyGrammar_FindDFA(g, type);
85                 if (d1->d_first == dummy) {
86                     fprintf(stderr,
87                         "Left-recursion below '%s'\n",
88                         d->d_name);
89                 }
90                 else {
91                     if (d1->d_first == NULL)
92                         calcfirstset(g, d1);
93                     mergebitset(result,
94                                 d1->d_first, nbits);
95                 }
96             }
97             else if (ISTERMINAL(type)) {
98                 addbit(result, a->a_lbl);
99             }
100         }
101     }
102     d->d_first = result;
103     if (Py_DebugFlag) {
104         printf("FIRST set for '%s': {", d->d_name);
105         for (i = 0; i < nbits; i++) {
106             if (testbit(result, i))
107                 printf(" %s", PyGrammar_LabelRepr(&l0[i]));
108         }
109         printf(" }\n");
110     }
111 
112     PyObject_FREE(sym);
113 }
114