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