Parser/grammar.c

   1 /***********************************************************
   2 Copyright 1991, 1992, 1993, 1994 by Stichting Mathematisch Centrum,
   3 Amsterdam, 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         return g;
  52 }
  53
  54 dfa *
  55 adddfa(g, type, name)
  56         grammar *g;
  57         int type;
  58         char *name;
  59 {
  60         dfa *d;
  61
  62         RESIZE(g->g_dfa, dfa, g->g_ndfas + 1);
  63         if (g->g_dfa == NULL)
  64                 fatal("no mem to resize dfa in adddfa");
  65         d = &g->g_dfa[g->g_ndfas++];
  66         d->d_type = type;
  67         d->d_name = name;
  68         d->d_nstates = 0;
  69         d->d_state = NULL;
  70         d->d_initial = -1;
  71         d->d_first = NULL;
  72         return d; /* Only use while fresh! */
  73 }
  74
  75 int
  76 addstate(d)
  77         dfa *d;
  78 {
  79         state *s;
  80
  81         RESIZE(d->d_state, state, d->d_nstates + 1);
  82         if (d->d_state == NULL)
  83                 fatal("no mem to resize state in addstate");
  84         s = &d->d_state[d->d_nstates++];
  85         s->s_narcs = 0;
  86         s->s_arc = NULL;
  87         return s - d->d_state;
  88 }
  89
  90 void
  91 addarc(d, from, to, lbl)
  92         dfa *d;
  93         int lbl;
  94 {
  95         state *s;
  96         arc *a;
  97
  98         assert(0 <= from && from < d->d_nstates);
  99         assert(0 <= to && to < d->d_nstates);
 100
 101         s = &d->d_state[from];
 102         RESIZE(s->s_arc, arc, s->s_narcs + 1);
 103         if (s->s_arc == NULL)
 104                 fatal("no mem to resize arc list in addarc");
 105         a = &s->s_arc[s->s_narcs++];
 106         a->a_lbl = lbl;
 107         a->a_arrow = to;
 108 }
 109
 110 int
 111 addlabel(ll, type, str)
 112         labellist *ll;
 113         int type;
 114         char *str;
 115 {
 116         int i;
 117         label *lb;
 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         RESIZE(ll->ll_label, label, ll->ll_nlabels + 1);
 125         if (ll->ll_label == NULL)
 126                 fatal("no mem to resize labellist in addlabel");
 127         lb = &ll->ll_label[ll->ll_nlabels++];
 128         lb->lb_type = type;
 129         lb->lb_str = str; /* XXX strdup(str) ??? */
 130         return lb - ll->ll_label;
 131 }
 132
 133 /* Same, but rather dies than adds */
 134
 135 int
 136 findlabel(ll, type, str)
 137         labellist *ll;
 138         int type;
 139         char *str;
 140 {
 141         int i;
 142         label *lb;
 143
 144         for (i = 0; i < ll->ll_nlabels; i++) {
 145                 if (ll->ll_label[i].lb_type == type /*&&
 146                         strcmp(ll->ll_label[i].lb_str, str) == 0*/)
 147                         return i;
 148         }
 149         fprintf(stderr, "Label %d/'%s' not found\n", type, str);
 150         abort();
 151 }
 152
 153 /* Forward */
 154 static void translabel PROTO((grammar *, label *));
 155
 156 void
 157 translatelabels(g)
 158         grammar *g;
 159 {
 160         int i;
 161
 162         printf("Translating labels ...\n");
 163         /* Don't translate EMPTY */
 164         for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
 165                 translabel(g, &g->g_ll.ll_label[i]);
 166 }
 167
 168 static void
 169 translabel(g, lb)
 170         grammar *g;
 171         label *lb;
 172 {
 173         int i;
 174
 175         if (debugging)
 176                 printf("Translating label %s ...\n", labelrepr(lb));
 177
 178         if (lb->lb_type == NAME) {
 179                 for (i = 0; i < g->g_ndfas; i++) {
 180                         if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
 181                                 if (debugging)
 182                                         printf("Label %s is non-terminal %d.\n",
 183                                                 lb->lb_str,
 184                                                 g->g_dfa[i].d_type);
 185                                 lb->lb_type = g->g_dfa[i].d_type;
 186                                 lb->lb_str = NULL;
 187                                 return;
 188                         }
 189                 }
 190                 for (i = 0; i < (int)N_TOKENS; i++) {
 191                         if (strcmp(lb->lb_str, tok_name[i]) == 0) {
 192                                 if (debugging)
 193                                         printf("Label %s is terminal %d.\n",
 194                                                 lb->lb_str, i);
 195                                 lb->lb_type = i;
 196                                 lb->lb_str = NULL;
 197                                 return;
 198                         }
 199                 }
 200                 printf("Can't translate NAME label '%s'\n", lb->lb_str);
 201                 return;
 202         }
 203
 204         if (lb->lb_type == STRING) {
 205                 if (isalpha(lb->lb_str[1])) {
 206                         char *p;
 207                         if (debugging)
 208                                 printf("Label %s is a keyword\n", lb->lb_str);
 209                         lb->lb_type = NAME;
 210                         lb->lb_str++;
 211                         p = strchr(lb->lb_str, '\'');
 212                         if (p)
 213                                 *p = '\0';
 214                 }
 215                 else if (lb->lb_str[2] == lb->lb_str[0]) {
 216                         int type = (int) tok_1char(lb->lb_str[1]);
 217                         if (type != OP) {
 218                                 lb->lb_type = type;
 219                                 lb->lb_str = NULL;
 220                         }
 221                         else
 222                                 printf("Unknown OP label %s\n",
 223                                         lb->lb_str);
 224                 }
 225                 else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
 226                         int type = (int) tok_2char(lb->lb_str[1],
 227                                                    lb->lb_str[2]);
 228                         if (type != OP) {
 229                                 lb->lb_type = type;
 230                                 lb->lb_str = NULL;
 231                         }
 232                         else
 233                                 printf("Unknown OP label %s\n",
 234                                         lb->lb_str);
 235                 }
 236                 else
 237                         printf("Can't translate STRING label %s\n",
 238                                 lb->lb_str);
 239         }
 240         else
 241                 printf("Can't translate label '%s'\n", labelrepr(lb));
 242 }