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 }