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