Parser/grammar.c

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