1
2 /* Grammar implementation */
3
4 #include "Python.h"
5 #include "pgenheaders.h"
6
7 #include <ctype.h>
8
9 #include "token.h"
10 #include "grammar.h"
11
12 #ifdef RISCOS
13 #include <unixlib.h>
14 #endif
15
16 extern int Py_DebugFlag;
17
18 grammar *
newgrammar(int start)19 newgrammar(int start)
20 {
21 grammar *g;
22
23 g = (grammar *)PyObject_MALLOC(sizeof(grammar));
24 if (g == NULL)
25 Py_FatalError("no mem for new grammar");
26 g->g_ndfas = 0;
27 g->g_dfa = NULL;
28 g->g_start = start;
29 g->g_ll.ll_nlabels = 0;
30 g->g_ll.ll_label = NULL;
31 g->g_accel = 0;
32 return g;
33 }
34
35 void
freegrammar(grammar * g)36 freegrammar(grammar *g)
37 {
38 int i;
39 for (i = 0; i < g->g_ndfas; i++) {
40 int j;
41 free(g->g_dfa[i].d_name);
42 for (j = 0; j < g->g_dfa[i].d_nstates; j++)
43 PyObject_FREE(g->g_dfa[i].d_state[j].s_arc);
44 PyObject_FREE(g->g_dfa[i].d_state);
45 }
46 PyObject_FREE(g->g_dfa);
47 for (i = 0; i < g->g_ll.ll_nlabels; i++)
48 free(g->g_ll.ll_label[i].lb_str);
49 PyObject_FREE(g->g_ll.ll_label);
50 PyObject_FREE(g);
51 }
52
53 dfa *
adddfa(grammar * g,int type,char * name)54 adddfa(grammar *g, int type, char *name)
55 {
56 dfa *d;
57
58 g->g_dfa = (dfa *)PyObject_REALLOC(g->g_dfa,
59 sizeof(dfa) * (g->g_ndfas + 1));
60 if (g->g_dfa == NULL)
61 Py_FatalError("no mem to resize dfa in adddfa");
62 d = &g->g_dfa[g->g_ndfas++];
63 d->d_type = type;
64 d->d_name = strdup(name);
65 d->d_nstates = 0;
66 d->d_state = NULL;
67 d->d_initial = -1;
68 d->d_first = NULL;
69 return d; /* Only use while fresh! */
70 }
71
72 int
addstate(dfa * d)73 addstate(dfa *d)
74 {
75 state *s;
76
77 d->d_state = (state *)PyObject_REALLOC(d->d_state,
78 sizeof(state) * (d->d_nstates + 1));
79 if (d->d_state == NULL)
80 Py_FatalError("no mem to resize state in addstate");
81 s = &d->d_state[d->d_nstates++];
82 s->s_narcs = 0;
83 s->s_arc = NULL;
84 s->s_lower = 0;
85 s->s_upper = 0;
86 s->s_accel = NULL;
87 s->s_accept = 0;
88 return s - d->d_state;
89 }
90
91 void
addarc(dfa * d,int from,int to,int lbl)92 addarc(dfa *d, int from, int to, int lbl)
93 {
94 state *s;
95 arc *a;
96
97 assert(0 <= from && from < d->d_nstates);
98 assert(0 <= to && to < d->d_nstates);
99
100 s = &d->d_state[from];
101 s->s_arc = (arc *)PyObject_REALLOC(s->s_arc, sizeof(arc) * (s->s_narcs + 1));
102 if (s->s_arc == NULL)
103 Py_FatalError("no mem to resize arc list in addarc");
104 a = &s->s_arc[s->s_narcs++];
105 a->a_lbl = lbl;
106 a->a_arrow = to;
107 }
108
109 int
addlabel(labellist * ll,int type,char * str)110 addlabel(labellist *ll, int type, char *str)
111 {
112 int i;
113 label *lb;
114
115 for (i = 0; i < ll->ll_nlabels; i++) {
116 if (ll->ll_label[i].lb_type == type &&
117 strcmp(ll->ll_label[i].lb_str, str) == 0)
118 return i;
119 }
120 ll->ll_label = (label *)PyObject_REALLOC(ll->ll_label,
121 sizeof(label) * (ll->ll_nlabels + 1));
122 if (ll->ll_label == NULL)
123 Py_FatalError("no mem to resize labellist in addlabel");
124 lb = &ll->ll_label[ll->ll_nlabels++];
125 lb->lb_type = type;
126 lb->lb_str = strdup(str);
127 if (Py_DebugFlag)
128 printf("Label @ %8p, %d: %s\n", ll, ll->ll_nlabels,
129 PyGrammar_LabelRepr(lb));
130 return lb - ll->ll_label;
131 }
132
133 /* Same, but rather dies than adds */
134
135 int
findlabel(labellist * ll,int type,char * str)136 findlabel(labellist *ll, int type, char *str)
137 {
138 int i;
139
140 for (i = 0; i < ll->ll_nlabels; i++) {
141 if (ll->ll_label[i].lb_type == type /*&&
142 strcmp(ll->ll_label[i].lb_str, str) == 0*/)
143 return i;
144 }
145 fprintf(stderr, "Label %d/'%s' not found\n", type, str);
146 Py_FatalError("grammar.c:findlabel()");
147 return 0; /* Make gcc -Wall happy */
148 }
149
150 /* Forward */
151 static void translabel(grammar *, label *);
152
153 void
translatelabels(grammar * g)154 translatelabels(grammar *g)
155 {
156 int i;
157
158 #ifdef Py_DEBUG
159 printf("Translating labels ...\n");
160 #endif
161 /* Don't translate EMPTY */
162 for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
163 translabel(g, &g->g_ll.ll_label[i]);
164 }
165
166 static void
translabel(grammar * g,label * lb)167 translabel(grammar *g, label *lb)
168 {
169 int i;
170
171 if (Py_DebugFlag)
172 printf("Translating label %s ...\n", PyGrammar_LabelRepr(lb));
173
174 if (lb->lb_type == NAME) {
175 for (i = 0; i < g->g_ndfas; i++) {
176 if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
177 if (Py_DebugFlag)
178 printf(
179 "Label %s is non-terminal %d.\n",
180 lb->lb_str,
181 g->g_dfa[i].d_type);
182 lb->lb_type = g->g_dfa[i].d_type;
183 free(lb->lb_str);
184 lb->lb_str = NULL;
185 return;
186 }
187 }
188 for (i = 0; i < (int)N_TOKENS; i++) {
189 if (strcmp(lb->lb_str, _PyParser_TokenNames[i]) == 0) {
190 if (Py_DebugFlag)
191 printf("Label %s is terminal %d.\n",
192 lb->lb_str, i);
193 lb->lb_type = i;
194 free(lb->lb_str);
195 lb->lb_str = NULL;
196 return;
197 }
198 }
199 printf("Can't translate NAME label '%s'\n", lb->lb_str);
200 return;
201 }
202
203 if (lb->lb_type == STRING) {
204 if (isalpha(Py_CHARMASK(lb->lb_str[1])) ||
205 lb->lb_str[1] == '_') {
206 char *p;
207 char *src;
208 char *dest;
209 size_t name_len;
210 if (Py_DebugFlag)
211 printf("Label %s is a keyword\n", lb->lb_str);
212 lb->lb_type = NAME;
213 src = lb->lb_str + 1;
214 p = strchr(src, '\'');
215 if (p)
216 name_len = p - src;
217 else
218 name_len = strlen(src);
219 dest = (char *)malloc(name_len + 1);
220 if (!dest) {
221 printf("Can't alloc dest '%s'\n", src);
222 return;
223 }
224 strncpy(dest, src, name_len);
225 dest[name_len] = '\0';
226 free(lb->lb_str);
227 lb->lb_str = dest;
228 }
229 else if (lb->lb_str[2] == lb->lb_str[0]) {
230 int type = (int) PyToken_OneChar(lb->lb_str[1]);
231 if (type != OP) {
232 lb->lb_type = type;
233 free(lb->lb_str);
234 lb->lb_str = NULL;
235 }
236 else
237 printf("Unknown OP label %s\n",
238 lb->lb_str);
239 }
240 else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
241 int type = (int) PyToken_TwoChars(lb->lb_str[1],
242 lb->lb_str[2]);
243 if (type != OP) {
244 lb->lb_type = type;
245 free(lb->lb_str);
246 lb->lb_str = NULL;
247 }
248 else
249 printf("Unknown OP label %s\n",
250 lb->lb_str);
251 }
252 else if (lb->lb_str[2] && lb->lb_str[3] && lb->lb_str[4] == lb->lb_str[0]) {
253 int type = (int) PyToken_ThreeChars(lb->lb_str[1],
254 lb->lb_str[2],
255 lb->lb_str[3]);
256 if (type != OP) {
257 lb->lb_type = type;
258 free(lb->lb_str);
259 lb->lb_str = NULL;
260 }
261 else
262 printf("Unknown OP label %s\n",
263 lb->lb_str);
264 }
265 else
266 printf("Can't translate STRING label %s\n",
267 lb->lb_str);
268 }
269 else
270 printf("Can't translate label '%s'\n",
271 PyGrammar_LabelRepr(lb));
272 }
273