|
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 |
|
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 |
|
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 } |