Parser/grammar.c

   1 /***********************************************************
   2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
   3 The Netherlands.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the names of Stichting Mathematisch
  12 Centrum or CWI or Corporation for National Research Initiatives or
  13 CNRI not be used in advertising or publicity pertaining to
  14 distribution of the software without specific, written prior
  15 permission.
  16
  17 While CWI is the initial source for this software, a modified version
  18 is made available by the Corporation for National Research Initiatives
  19 (CNRI) at the Internet address ftp://ftp.python.org.
  20
  21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
  22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
  24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  28 PERFORMANCE OF THIS SOFTWARE.
  29
  30 ******************************************************************/
  31
  32 /* Grammar implementation */
  33
  34 #include "pgenheaders.h"
  35
  36 #include <ctype.h>
  37
  38 #include "assert.h"
  39 #include "token.h"
  40 #include "grammar.h"
  41
  42 extern int Py_DebugFlag;
  43
  44 grammar *
  45 newgrammar(start)
  46         int start;
  47 {
  48         grammar *g;
  49
  50         g = PyMem_NEW(grammar, 1);
  51         if (g == NULL)
  52                 Py_FatalError("no mem for new grammar");
  53         g->g_ndfas = 0;
  54         g->g_dfa = NULL;
  55         g->g_start = start;
  56         g->g_ll.ll_nlabels = 0;
  57         g->g_ll.ll_label = NULL;
  58         g->g_accel = 0;
  59         return g;
  60 }
  61
  62 dfa *
  63 adddfa(g, type, name)
  64         grammar *g;
  65         int type;
  66         char *name;
  67 {
  68         dfa *d;
  69
  70         PyMem_RESIZE(g->g_dfa, dfa, g->g_ndfas + 1);
  71         if (g->g_dfa == NULL)
  72                 Py_FatalError("no mem to resize dfa in adddfa");
  73         d = &g->g_dfa[g->g_ndfas++];
  74         d->d_type = type;
  75         d->d_name = name;
  76         d->d_nstates = 0;
  77         d->d_state = NULL;
  78         d->d_initial = -1;
  79         d->d_first = NULL;
  80         return d; /* Only use while fresh! */
  81 }
  82
  83 int
  84 addstate(d)
  85         dfa *d;
  86 {
  87         state *s;
  88
  89         PyMem_RESIZE(d->d_state, state, d->d_nstates + 1);
  90         if (d->d_state == NULL)
  91                 Py_FatalError("no mem to resize state in addstate");
  92         s = &d->d_state[d->d_nstates++];
  93         s->s_narcs = 0;
  94         s->s_arc = NULL;
  95         s->s_lower = 0;
  96         s->s_upper = 0;
  97         s->s_accel = NULL;
  98         s->s_accept = 0;
  99         return s - d->d_state;
 100 }
 101
 102 void
 103 addarc(d, from, to, lbl)
 104         dfa *d;
 105         int lbl;
 106 {
 107         state *s;
 108         arc *a;
 109
 110         assert(0 <= from && from < d->d_nstates);
 111         assert(0 <= to && to < d->d_nstates);
 112
 113         s = &d->d_state[from];
 114         PyMem_RESIZE(s->s_arc, arc, s->s_narcs + 1);
 115         if (s->s_arc == NULL)
 116                 Py_FatalError("no mem to resize arc list in addarc");
 117         a = &s->s_arc[s->s_narcs++];
 118         a->a_lbl = lbl;
 119         a->a_arrow = to;
 120 }
 121
 122 int
 123 addlabel(ll, type, str)
 124         labellist *ll;
 125         int type;
 126         char *str;
 127 {
 128         int i;
 129         label *lb;
 130
 131         for (i = 0; i < ll->ll_nlabels; i++) {
 132                 if (ll->ll_label[i].lb_type == type &&
 133                         strcmp(ll->ll_label[i].lb_str, str) == 0)
 134                         return i;
 135         }
 136         PyMem_RESIZE(ll->ll_label, label, ll->ll_nlabels + 1);
 137         if (ll->ll_label == NULL)
 138                 Py_FatalError("no mem to resize labellist in addlabel");
 139         lb = &ll->ll_label[ll->ll_nlabels++];
 140         lb->lb_type = type;
 141         lb->lb_str = str; /* XXX strdup(str) ??? */
 142         return lb - ll->ll_label;
 143 }
 144
 145 /* Same, but rather dies than adds */
 146
 147 int
 148 findlabel(ll, type, str)
 149         labellist *ll;
 150         int type;
 151         char *str;
 152 {
 153         int i;
 154
 155         for (i = 0; i < ll->ll_nlabels; i++) {
 156                 if (ll->ll_label[i].lb_type == type /*&&
 157                         strcmp(ll->ll_label[i].lb_str, str) == 0*/)
 158                         return i;
 159         }
 160         fprintf(stderr, "Label %d/'%s' not found\n", type, str);
 161         Py_FatalError("grammar.c:findlabel()");
 162         return 0; /* Make gcc -Wall happy */
 163 }
 164
 165 /* Forward */
 166 static void translabel Py_PROTO((grammar *, label *));
 167
 168 void
 169 translatelabels(g)
 170         grammar *g;
 171 {
 172         int i;
 173
 174 #ifdef Py_DEBUG
 175         printf("Translating labels ...\n");
 176 #endif
 177         /* Don't translate EMPTY */
 178         for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
 179                 translabel(g, &g->g_ll.ll_label[i]);
 180 }
 181
 182 static void
 183 translabel(g, lb)
 184         grammar *g;
 185         label *lb;
 186 {
 187         int i;
 188
 189         if (Py_DebugFlag)
 190                 printf("Translating label %s ...\n", PyGrammar_LabelRepr(lb));
 191
 192         if (lb->lb_type == NAME) {
 193                 for (i = 0; i < g->g_ndfas; i++) {
 194                         if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
 195                                 if (Py_DebugFlag)
 196                                         printf(
 197                                             "Label %s is non-terminal %d.\n",
 198                                             lb->lb_str,
 199                                             g->g_dfa[i].d_type);
 200                                 lb->lb_type = g->g_dfa[i].d_type;
 201                                 lb->lb_str = NULL;
 202                                 return;
 203                         }
 204                 }
 205                 for (i = 0; i < (int)N_TOKENS; i++) {
 206                         if (strcmp(lb->lb_str, _PyParser_TokenNames[i]) == 0) {
 207                                 if (Py_DebugFlag)
 208                                         printf("Label %s is terminal %d.\n",
 209                                                 lb->lb_str, i);
 210                                 lb->lb_type = i;
 211                                 lb->lb_str = NULL;
 212                                 return;
 213                         }
 214                 }
 215                 printf("Can't translate NAME label '%s'\n", lb->lb_str);
 216                 return;
 217         }
 218
 219         if (lb->lb_type == STRING) {
 220                 if (isalpha((int)(lb->lb_str[1])) || lb->lb_str[1] == '_') {
 221                         char *p;
 222                         if (Py_DebugFlag)
 223                                 printf("Label %s is a keyword\n", lb->lb_str);
 224                         lb->lb_type = NAME;
 225                         lb->lb_str++;
 226                         p = strchr(lb->lb_str, '\'');
 227                         if (p)
 228                                 *p = '\0';
 229                 }
 230                 else if (lb->lb_str[2] == lb->lb_str[0]) {
 231                         int type = (int) PyToken_OneChar(lb->lb_str[1]);
 232                         if (type != OP) {
 233                                 lb->lb_type = type;
 234                                 lb->lb_str = NULL;
 235                         }
 236                         else
 237                                 printf("Unknown OP label %s\n",
 238                                         lb->lb_str);
 239                 }
 240                 else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
 241                         int type = (int) PyToken_TwoChars(lb->lb_str[1],
 242                                                    lb->lb_str[2]);
 243                         if (type != OP) {
 244                                 lb->lb_type = type;
 245                                 lb->lb_str = NULL;
 246                         }
 247                         else
 248                                 printf("Unknown OP label %s\n",
 249                                         lb->lb_str);
 250                 }
 251                 else
 252                         printf("Can't translate STRING label %s\n",
 253                                 lb->lb_str);
 254         }
 255         else
 256                 printf("Can't translate label '%s'\n",
 257                        PyGrammar_LabelRepr(lb));
 258 }