source: python/vendor/Python-2.6.5/Parser/firstsets.c

/* Computation of FIRST stets */

#include "pgenheaders.h"
#include "grammar.h"
#include "token.h"

extern int Py_DebugFlag;

/* Forward */
static void calcfirstset(grammar *, dfa *);

void
addfirstsets(grammar *g)
{
        int i;
        dfa *d;

        if (Py_DebugFlag)
                printf("Adding FIRST sets ...\n");
        for (i = 0; i < g->g_ndfas; i++) {
                d = &g->g_dfa[i];
                if (d->d_first == NULL)
                        calcfirstset(g, d);
        }
}

static void
calcfirstset(grammar *g, dfa *d)
{
        int i, j;
        state *s;
        arc *a;
        int nsyms;
        int *sym;
        int nbits;
        static bitset dummy;
        bitset result;
        int type;
        dfa *d1;
        label *l0;
        
        if (Py_DebugFlag)
                printf("Calculate FIRST set for '%s'\n", d->d_name);
        
        if (dummy == NULL)
                dummy = newbitset(1);
        if (d->d_first == dummy) {
                fprintf(stderr, "Left-recursion for '%s'\n", d->d_name);
                return;
        }
        if (d->d_first != NULL) {
                fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n",
                        d->d_name);
        }
        d->d_first = dummy;
        
        l0 = g->g_ll.ll_label;
        nbits = g->g_ll.ll_nlabels;
        result = newbitset(nbits);
        
        sym = (int *)PyObject_MALLOC(sizeof(int));
        if (sym == NULL)
                Py_FatalError("no mem for new sym in calcfirstset");
        nsyms = 1;
        sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL);
        
        s = &d->d_state[d->d_initial];
        for (i = 0; i < s->s_narcs; i++) {
                a = &s->s_arc[i];
                for (j = 0; j < nsyms; j++) {
                        if (sym[j] == a->a_lbl)
                                break;
                }
                if (j >= nsyms) { /* New label */
                        sym = (int *)PyObject_REALLOC(sym, 
                                                sizeof(int) * (nsyms + 1));
                        if (sym == NULL)
                                Py_FatalError(
                                    "no mem to resize sym in calcfirstset");
                        sym[nsyms++] = a->a_lbl;
                        type = l0[a->a_lbl].lb_type;
                        if (ISNONTERMINAL(type)) {
                                d1 = PyGrammar_FindDFA(g, type);
                                if (d1->d_first == dummy) {
                                        fprintf(stderr,
                                                "Left-recursion below '%s'\n",
                                                d->d_name);
                                }
                                else {
                                        if (d1->d_first == NULL)
                                                calcfirstset(g, d1);
                                        mergebitset(result,
                                                    d1->d_first, nbits);
                                }
                        }
                        else if (ISTERMINAL(type)) {
                                addbit(result, a->a_lbl);
                        }
                }
        }
        d->d_first = result;
        if (Py_DebugFlag) {
                printf("FIRST set for '%s': {", d->d_name);
                for (i = 0; i < nbits; i++) {
                        if (testbit(result, i))
                                printf(" %s", PyGrammar_LabelRepr(&l0[i]));
                }
                printf(" }\n");
        }

        PyObject_FREE(sym);
}