utils/Burg/fe.c

   1 char rcsid_fe[] = "$Id$";
   2
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include "b.h"
   6 #include "fe.h"
   7
   8 int grammarflag;
   9
  10 static int arity;
  11
  12 List    ruleASTs;
  13 List    grammarNts;
  14
  15 static void doBinding ARGS((Binding));
  16 static void doDecl ARGS((Arity));
  17 static NonTerminal lookup ARGS((Pattern));
  18 static NonTerminal normalize ARGS((PatternAST, NonTerminal, Pattern *));
  19 static void doEnterNonTerm ARGS((RuleAST));
  20 static void doRule ARGS((RuleAST));
  21 static void doTable ARGS((Operator));
  22
  23 static void
  24 doBinding(b) Binding b;
  25 {
  26         int new;
  27         Symbol s;
  28
  29         s = enter(b->name, &new);
  30         if (!new) {
  31                 fprintf(stderr, "Non-unique name: %s\n", b->name);
  32                 exit(1);
  33         }
  34         s->tag = OPERATOR;
  35         s->u.op = newOperator(b->name, b->opnum, arity);
  36         if (arity == 0) {
  37                 leaves = newList(s->u.op, leaves);
  38         }
  39 }
  40
  41 static void
  42 doDecl(a) Arity a;
  43 {
  44         if (!a) {
  45                 return;
  46         }
  47         arity = a->arity;
  48         foreachList((ListFn) doBinding, a->bindings);
  49 }
  50
  51
  52 static List xpatterns;
  53 static int tcount;
  54
  55 static NonTerminal
  56 lookup(p) Pattern p;
  57 {
  58         char buf[10];
  59         char *s;
  60         List l;
  61         NonTerminal n;
  62         DeltaCost dummy;
  63
  64         for (l = xpatterns; l; l = l->next) {
  65                 Pattern x = (Pattern) l->x;
  66                 if (x->op == p->op
  67                                 && x->children[0] == p->children[0]
  68                                 && x->children[1] == p->children[1]) {
  69                         return x->normalizer;
  70                 }
  71         }
  72         sprintf(buf, "n%%%d", tcount++);
  73         s = (char *) zalloc(strlen(buf)+1);
  74         strcpy(s, buf);
  75         n = newNonTerminal(s);
  76         p->normalizer = n;
  77         xpatterns = newList(p, xpatterns);
  78         ZEROCOST(dummy);
  79         (void) newRule(dummy, 0, n, p);
  80         return n;
  81 }
  82
  83 static NonTerminal
  84 normalize(ast, nt, patt) PatternAST ast; NonTerminal nt; Pattern *patt;
  85 {
  86         Symbol s;
  87         int new;
  88         Pattern dummy;
  89
  90         s = enter(ast->op, &new);
  91         ast->sym = s;
  92         if (new) {
  93                 fprintf(stderr, "Illegal use of %s --- undefined symbol\n", s->name);
  94                 exit(1);
  95                 return 0; /* shut up compilers */
  96         } else if (s->tag == NONTERMINAL) {
  97                 if (ast->children) {
  98                         fprintf(stderr, "Illegal use of %s, a non-terminal, as a terminal\n", s->name);
  99                         exit(1);
 100                 }
 101                 *patt = newPattern(0);
 102                 (*patt)->children[0] = s->u.nt;
 103                 return s->u.nt;
 104         } else {
 105                 s->u.op->ref = 1;
 106                 *patt = newPattern(s->u.op);
 107                 if (s->u.op->arity == -1) {
 108                         if (!ast->children) {
 109                                 s->u.op->arity = 0;
 110                                 leaves = newList(s->u.op, leaves);
 111                         } else if (!ast->children->next) {
 112                                 s->u.op->arity = 1;
 113                         } else if (!ast->children->next->next) {
 114                                 s->u.op->arity = 2;
 115                         } else {
 116                                 fprintf(stderr, "ERROR: Too many children (max = 2) for \"%s\"\n", s->name);
 117                                 exit(1);
 118                         }
 119                         if (s->u.op->arity > max_arity) {
 120                                 max_arity = s->u.op->arity;
 121                         }
 122                 }
 123                 switch (s->u.op->arity) {
 124                 default:
 125                         assert(0);
 126                         break;
 127                 case 0:
 128                         if (ast->children) {
 129                                 fprintf(stderr, "ERROR: Incorrect number of children for leaf operator, \"%s\"\n", s->name);
 130                                 exit(1);
 131                         }
 132                         break;
 133                 case 1:
 134                         if (!ast->children || ast->children->next) {
 135                                 fprintf(stderr, "ERROR: Incorrect number of children for unary operator, \"%s\"\n", s->name);
 136                                 exit(1);
 137                         }
 138                         (*patt)->children[0] = normalize((PatternAST) ast->children->x, 0, &dummy);
 139                         break;
 140                 case 2:
 141                         if (!ast->children || !ast->children->next) {
 142                                 fprintf(stderr, "ERROR: Incorrect number of children for binary operator, \"%s\"\n", s->name);
 143                                 exit(1);
 144                         }
 145                         (*patt)->children[0] = normalize((PatternAST) ast->children->x, 0, &dummy);
 146                         (*patt)->children[1] = normalize((PatternAST) ast->children->next->x, 0, &dummy);
 147                         break;
 148                 }
 149                 if (nt) {
 150                         (*patt)->normalizer = nt;
 151                         return nt;
 152                 } else {
 153                         return lookup(*patt);
 154                 }
 155         }
 156 }
 157
 158 static void
 159 doEnterNonTerm(ast) RuleAST ast;
 160 {
 161         int new;
 162         Symbol s;
 163         DeltaCost delta;
 164         int i;
 165         IntList p;
 166
 167
 168         s = enter(ast->lhs, &new);
 169         if (new) {
 170                 s->u.nt = newNonTerminal(s->name);
 171                 s->tag = NONTERMINAL;
 172         } else {
 173                 if (s->tag != NONTERMINAL) {
 174                         fprintf(stderr, "Illegal use of %s as a non-terminal\n", s->name);
 175                         exit(1);
 176                 }
 177         }
 178         ZEROCOST(delta);
 179         for (p = ast->cost, i = 0; p; p = p->next, i++) {
 180                 int x = p->x;
 181 #ifndef NOLEX
 182                 if (lexical) {
 183                         if (i < DELTAWIDTH) {
 184                                 delta[i] = x;
 185                         }
 186                 } else
 187 #endif /* NOLEX */
 188                 {
 189                         if (i == principleCost) {
 190                                 PRINCIPLECOST(delta) = x;
 191                         }
 192                 }
 193         }
 194         ast->rule = newRule(delta, ast->erulenum, s->u.nt, 0);
 195 }
 196
 197 static void
 198 doRule(ast) RuleAST ast;
 199 {
 200         Pattern pat;
 201
 202         (void) normalize(ast->pat, ast->rule->lhs, &pat);
 203         ast->rule->pat = pat;
 204 }
 205
 206 static void
 207 doTable(op) Operator op;
 208 {
 209         op->table = newTable(op);
 210 }
 211
 212 void
 213 doSpec(decls, rules) List decls; List rules;
 214 {
 215         foreachList((ListFn) doDecl, decls);
 216         debug(debugTables, foreachList((ListFn) dumpOperator_l, operators));
 217
 218         ruleASTs = rules;
 219         reveachList((ListFn) doEnterNonTerm, rules);
 220
 221         last_user_nonterminal = max_nonterminal;
 222
 223         reveachList((ListFn) doRule, rules);
 224         debug(debugTables, foreachList((ListFn) dumpRule, rules));
 225
 226         foreachList((ListFn) doTable, operators);
 227 }
 228
 229 void
 230 doStart(name) char *name;
 231 {
 232         Symbol s;
 233         int new;
 234
 235         if (start) {
 236                 yyerror1("Redeclaration of start symbol to be ");
 237                 fprintf(stderr, "\"%s\"\n", name);
 238                 exit(1);
 239         }
 240         s = enter(name, &new);
 241         if (new) {
 242                 s->u.nt = newNonTerminal(s->name);
 243                 s->tag = NONTERMINAL;
 244         } else {
 245                 if (s->tag != NONTERMINAL) {
 246                         fprintf(stderr, "Illegal use of %s as a non-terminal\n", s->name);
 247                         exit(1);
 248                 }
 249         }
 250 }
 251
 252 void
 253 doGrammarNts()
 254 {
 255         List l;
 256         int new;
 257
 258         for (l = grammarNts; l; l = l->next) {
 259                 char *n = (char*) l->x;
 260                 Symbol s;
 261
 262                 s = enter(n, &new);
 263                 if (new) {
 264                         fprintf(stderr, "ERROR: %%gram, unused non-terminal: \"%s\"\n", n);
 265                         exit(1);
 266                 }
 267                 if (s->tag != NONTERMINAL) {
 268                         fprintf(stderr, "ERROR: %%gram, Not a non-terminal: \"%s\"\n", n);
 269                         exit(1);
 270                 }
 271                 l->x = s;
 272         }
 273 }
 274
 275 void
 276 doGram(nts) List nts;
 277 {
 278         if (grammarNts) {
 279                 yyerror1("Redeclaration of %%gram\n");
 280                 exit(1);
 281         }
 282         grammarNts = nts;
 283 }
 284
 285 Arity
 286 newArity(ar, b) int ar; List b;
 287 {
 288         Arity a = (Arity) zalloc(sizeof(struct arity));
 289         a->arity = ar;
 290         a->bindings = b;
 291         return a;
 292 }
 293
 294 Binding
 295 newBinding(name, opnum) char *name; int opnum;
 296 {
 297         Binding b = (Binding) zalloc(sizeof(struct binding));
 298         if (opnum == 0) {
 299                 yyerror1("ERROR: Non-positive external symbol number, ");
 300                 fprintf(stderr, "%d", opnum);
 301                 exit(1);
 302         }
 303         b->name = name;
 304         b->opnum = opnum;
 305         return b;
 306 }
 307
 308 PatternAST
 309 newPatternAST(op, children) char *op; List children;
 310 {
 311         PatternAST p = (PatternAST) zalloc(sizeof(struct patternAST));
 312         p->op = op;
 313         p->children = children;
 314         return p;
 315 }
 316
 317 int max_ruleAST;
 318
 319 RuleAST
 320 newRuleAST(lhs, pat, erulenum, cost) char *lhs; PatternAST pat; int erulenum; IntList cost;
 321 {
 322         RuleAST p = (RuleAST) zalloc(sizeof(struct ruleAST));
 323         p->lhs = lhs;
 324         p->pat = pat;
 325         if (erulenum <= 0) {
 326                 yyerror1("External Rulenumber ");
 327                 fprintf(stderr, "(%d) <= 0\n", erulenum);
 328                 exit(1);
 329         }
 330         p->erulenum = erulenum;
 331         p->cost = cost;
 332         max_ruleAST++;
 333         return p;
 334 }
 335
 336 void
 337 dumpBinding(b) Binding b;
 338 {
 339         printf("%s=%d ", b->name, b->opnum);
 340 }
 341
 342 void
 343 dumpArity(a) Arity a;
 344 {
 345         List l;
 346
 347         printf("Arity(%d) ", a->arity);
 348         for (l = a->bindings; l; l = l->next) {
 349                 Binding b = (Binding) l->x;
 350                 dumpBinding(b);
 351         }
 352         printf("\n");
 353 }
 354
 355 void
 356 dumpPatternAST(p) PatternAST p;
 357 {
 358         List l;
 359
 360         printf("%s", p->op);
 361         if (p->children) {
 362                 printf("(");
 363                 for (l = p->children; l; l = l->next) {
 364                         PatternAST past = (PatternAST) l->x;
 365                         dumpPatternAST(past);
 366                         if (l->next) {
 367                                 printf(", ");
 368                         }
 369                 }
 370                 printf(")");
 371         }
 372 }
 373
 374 void
 375 dumpRuleAST(p) RuleAST p;
 376 {
 377         printf("%s : ", p->lhs);
 378         dumpPatternAST(p->pat);
 379         printf(" = %d (%ld)\n", p->erulenum, (long) p->cost);
 380 }
 381
 382 void
 383 dumpDecls(decls) List decls;
 384 {
 385         List l;
 386
 387         for (l = decls; l; l = l->next) {
 388                 Arity a = (Arity) l->x;
 389                 dumpArity(a);
 390         }
 391 }
 392
 393 void
 394 dumpRules(rules) List rules;
 395 {
 396         List l;
 397
 398         for (l = rules; l; l = l->next) {
 399                 RuleAST p = (RuleAST) l->x;
 400                 dumpRuleAST(p);
 401         }
 402 }
 403