grammar.c revision dbd9ba6a6c19c3d06f5684b3384a934f740038db
1/*********************************************************** 2Copyright (c) 2000, BeOpen.com. 3Copyright (c) 1995-2000, Corporation for National Research Initiatives. 4Copyright (c) 1990-1995, Stichting Mathematisch Centrum. 5All rights reserved. 6 7See the file "Misc/COPYRIGHT" for information on usage and 8redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES. 9******************************************************************/ 10 11/* Grammar implementation */ 12 13#include "pgenheaders.h" 14 15#include <ctype.h> 16 17#include "assert.h" 18#include "token.h" 19#include "grammar.h" 20 21extern int Py_DebugFlag; 22 23grammar * 24newgrammar(start) 25 int start; 26{ 27 grammar *g; 28 29 g = PyMem_NEW(grammar, 1); 30 if (g == NULL) 31 Py_FatalError("no mem for new grammar"); 32 g->g_ndfas = 0; 33 g->g_dfa = NULL; 34 g->g_start = start; 35 g->g_ll.ll_nlabels = 0; 36 g->g_ll.ll_label = NULL; 37 g->g_accel = 0; 38 return g; 39} 40 41dfa * 42adddfa(g, type, name) 43 grammar *g; 44 int type; 45 char *name; 46{ 47 dfa *d; 48 49 PyMem_RESIZE(g->g_dfa, dfa, g->g_ndfas + 1); 50 if (g->g_dfa == NULL) 51 Py_FatalError("no mem to resize dfa in adddfa"); 52 d = &g->g_dfa[g->g_ndfas++]; 53 d->d_type = type; 54 d->d_name = name; 55 d->d_nstates = 0; 56 d->d_state = NULL; 57 d->d_initial = -1; 58 d->d_first = NULL; 59 return d; /* Only use while fresh! */ 60} 61 62int 63addstate(d) 64 dfa *d; 65{ 66 state *s; 67 68 PyMem_RESIZE(d->d_state, state, d->d_nstates + 1); 69 if (d->d_state == NULL) 70 Py_FatalError("no mem to resize state in addstate"); 71 s = &d->d_state[d->d_nstates++]; 72 s->s_narcs = 0; 73 s->s_arc = NULL; 74 s->s_lower = 0; 75 s->s_upper = 0; 76 s->s_accel = NULL; 77 s->s_accept = 0; 78 return s - d->d_state; 79} 80 81void 82addarc(d, from, to, lbl) 83 dfa *d; 84 int lbl; 85{ 86 state *s; 87 arc *a; 88 89 assert(0 <= from && from < d->d_nstates); 90 assert(0 <= to && to < d->d_nstates); 91 92 s = &d->d_state[from]; 93 PyMem_RESIZE(s->s_arc, arc, s->s_narcs + 1); 94 if (s->s_arc == NULL) 95 Py_FatalError("no mem to resize arc list in addarc"); 96 a = &s->s_arc[s->s_narcs++]; 97 a->a_lbl = lbl; 98 a->a_arrow = to; 99} 100 101int 102addlabel(ll, type, str) 103 labellist *ll; 104 int type; 105 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 PyMem_RESIZE(ll->ll_label, label, ll->ll_nlabels + 1); 116 if (ll->ll_label == NULL) 117 Py_FatalError("no mem to resize labellist in addlabel"); 118 lb = &ll->ll_label[ll->ll_nlabels++]; 119 lb->lb_type = type; 120 lb->lb_str = str; /* XXX strdup(str) ??? */ 121 return lb - ll->ll_label; 122} 123 124/* Same, but rather dies than adds */ 125 126int 127findlabel(ll, type, str) 128 labellist *ll; 129 int type; 130 char *str; 131{ 132 int i; 133 134 for (i = 0; i < ll->ll_nlabels; i++) { 135 if (ll->ll_label[i].lb_type == type /*&& 136 strcmp(ll->ll_label[i].lb_str, str) == 0*/) 137 return i; 138 } 139 fprintf(stderr, "Label %d/'%s' not found\n", type, str); 140 Py_FatalError("grammar.c:findlabel()"); 141 return 0; /* Make gcc -Wall happy */ 142} 143 144/* Forward */ 145static void translabel(grammar *, label *); 146 147void 148translatelabels(g) 149 grammar *g; 150{ 151 int i; 152 153#ifdef Py_DEBUG 154 printf("Translating labels ...\n"); 155#endif 156 /* Don't translate EMPTY */ 157 for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++) 158 translabel(g, &g->g_ll.ll_label[i]); 159} 160 161static void 162translabel(g, lb) 163 grammar *g; 164 label *lb; 165{ 166 int i; 167 168 if (Py_DebugFlag) 169 printf("Translating label %s ...\n", PyGrammar_LabelRepr(lb)); 170 171 if (lb->lb_type == NAME) { 172 for (i = 0; i < g->g_ndfas; i++) { 173 if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) { 174 if (Py_DebugFlag) 175 printf( 176 "Label %s is non-terminal %d.\n", 177 lb->lb_str, 178 g->g_dfa[i].d_type); 179 lb->lb_type = g->g_dfa[i].d_type; 180 lb->lb_str = NULL; 181 return; 182 } 183 } 184 for (i = 0; i < (int)N_TOKENS; i++) { 185 if (strcmp(lb->lb_str, _PyParser_TokenNames[i]) == 0) { 186 if (Py_DebugFlag) 187 printf("Label %s is terminal %d.\n", 188 lb->lb_str, i); 189 lb->lb_type = i; 190 lb->lb_str = NULL; 191 return; 192 } 193 } 194 printf("Can't translate NAME label '%s'\n", lb->lb_str); 195 return; 196 } 197 198 if (lb->lb_type == STRING) { 199 if (isalpha((int)(lb->lb_str[1])) || lb->lb_str[1] == '_') { 200 char *p; 201 if (Py_DebugFlag) 202 printf("Label %s is a keyword\n", lb->lb_str); 203 lb->lb_type = NAME; 204 lb->lb_str++; 205 p = strchr(lb->lb_str, '\''); 206 if (p) 207 *p = '\0'; 208 } 209 else if (lb->lb_str[2] == lb->lb_str[0]) { 210 int type = (int) PyToken_OneChar(lb->lb_str[1]); 211 if (type != OP) { 212 lb->lb_type = type; 213 lb->lb_str = NULL; 214 } 215 else 216 printf("Unknown OP label %s\n", 217 lb->lb_str); 218 } 219 else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) { 220 int type = (int) PyToken_TwoChars(lb->lb_str[1], 221 lb->lb_str[2]); 222 if (type != OP) { 223 lb->lb_type = type; 224 lb->lb_str = NULL; 225 } 226 else 227 printf("Unknown OP label %s\n", 228 lb->lb_str); 229 } 230 else 231 printf("Can't translate STRING label %s\n", 232 lb->lb_str); 233 } 234 else 235 printf("Can't translate label '%s'\n", 236 PyGrammar_LabelRepr(lb)); 237} 238