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