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