Parser/grammar.c

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