← Back to branch summary

~ubuntu-branches/ubuntu/natty/python3.1/natty-security

« back to all changes in this revision

Viewing changes to Parser/firstsets.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2010-07-06 16:52:42 UTC
  • mfrom: (1.2.1 upstream) (2.1.11 sid)
  • Revision ID: james.westby@ubuntu.com-20100706165242-2xv4i019r3et6c0j
Tags: 3.1.2+20100706-1ubuntu1
* Merge with Debian; remaining changes:
  - Regenerate the control file.
  - Add debian/patches/overwrite-semaphore-check for Lucid buildds.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Parser/firstsets.c
13
13
void
14
14
addfirstsets(grammar *g)
15
15
{
16
 
        int i;
17
 
        dfa *d;
 
16
    int i;
 
17
    dfa *d;
18
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
 
        }
 
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
26
}
27
27
 
28
28
static void
29
29
calcfirstset(grammar *g, dfa *d)
30
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);
 
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
113
}