1
2/* Computation of FIRST stets */
3
4#include "pgenheaders.h"
5#include "grammar.h"
6#include "token.h"
7
8extern int Py_DebugFlag;
9
10/* Forward */
11static void calcfirstset(grammar *, dfa *);
12
13void
14addfirstsets(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
28static void
29calcfirstset(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