Parser/grammar.c

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