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