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