utils/Burg/sample.gr

   1 %{
   2 #include <stdio.h>
   3
   4 typedef struct node *NODEPTR_TYPE;
   5
   6 struct node {
   7         int op, state_label;
   8         NODEPTR_TYPE left, right;
   9 };
  10
  11 #define OP_LABEL(p)     ((p)->op)
  12 #define STATE_LABEL(p)  ((p)->state_label)
  13 #define LEFT_CHILD(p)   ((p)->left)
  14 #define RIGHT_CHILD(p)  ((p)->right)
  15 #define PANIC           printf
  16 %}
  17
  18 %start reg
  19 %term Assign=1 Constant=2 Fetch=3 Four=4 Mul=5 Plus=6
  20 %%
  21 con:  Constant                = 1 (0);
  22 con:  Four                    = 2 (0);
  23 addr: con                     = 3 (0);
  24 addr: Plus(con,reg)           = 4 (0);
  25 addr: Plus(con,Mul(Four,reg)) = 5 (0);
  26 reg:  Fetch(addr)             = 6 (1);
  27 reg:  Assign(addr,reg)        = 7 (1);
  28
  29 %%
  30
  31 #define Assign 1
  32 #define Constant 2
  33 #define Fetch 3
  34 #define Four 4
  35 #define Mul 5
  36 #define Plus 6
  37
  38 #ifdef __STDC__
  39 #define ARGS(x) x
  40 #else
  41 #define ARGS(x) ()
  42 #endif
  43
  44 NODEPTR_TYPE buildtree ARGS((int, NODEPTR_TYPE, NODEPTR_TYPE));
  45 void printcover ARGS((NODEPTR_TYPE, int, int));
  46 void printtree ARGS((NODEPTR_TYPE));
  47 int treecost ARGS((NODEPTR_TYPE, int, int));
  48 void printMatches ARGS((NODEPTR_TYPE));
  49 int main ARGS((void));
  50
  51 NODEPTR_TYPE buildtree(op, left, right) int op; NODEPTR_TYPE left; NODEPTR_TYPE right; {
  52         NODEPTR_TYPE p;
  53         extern void *malloc ARGS((unsigned));
  54
  55         p = (NODEPTR_TYPE) malloc(sizeof *p);
  56         p->op = op;
  57         p->left = left;
  58         p->right = right;
  59         return p;
  60 }
  61
  62 void printcover(p, goalnt, indent) NODEPTR_TYPE p; int goalnt; int indent; {
  63         int eruleno = burm_rule(STATE_LABEL(p), goalnt);
  64         short *nts = burm_nts[eruleno];
  65         NODEPTR_TYPE kids[10];
  66         int i;
  67
  68         if (eruleno == 0) {
  69                 printf("no cover\n");
  70                 return;
  71         }
  72         for (i = 0; i < indent; i++)
  73                 printf(".");
  74         printf("%s\n", burm_string[eruleno]);
  75         burm_kids(p, eruleno, kids);
  76         for (i = 0; nts[i]; i++)
  77                 printcover(kids[i], nts[i], indent+1);
  78 }
  79
  80 void printtree(p) NODEPTR_TYPE p; {
  81         int op = burm_op_label(p);
  82
  83         printf("%s", burm_opname[op]);
  84         switch (burm_arity[op]) {
  85         case 0:
  86                 break;
  87         case 1:
  88                 printf("(");
  89                 printtree(burm_child(p, 0));
  90                 printf(")");
  91                 break;
  92         case 2:
  93                 printf("(");
  94                 printtree(burm_child(p, 0));
  95                 printf(", ");
  96                 printtree(burm_child(p, 1));
  97                 printf(")");
  98                 break;
  99         }
 100 }
 101
 102 int treecost(p, goalnt, costindex) NODEPTR_TYPE p; int goalnt; int costindex; {
 103         int eruleno = burm_rule(STATE_LABEL(p), goalnt);
 104         int cost = burm_cost[eruleno][costindex], i;
 105         short *nts = burm_nts[eruleno];
 106         NODEPTR_TYPE kids[10];
 107
 108         burm_kids(p, eruleno, kids);
 109         for (i = 0; nts[i]; i++)
 110                 cost += treecost(kids[i], nts[i], costindex);
 111         return cost;
 112 }
 113
 114 void printMatches(p) NODEPTR_TYPE p; {
 115         int nt;
 116         int eruleno;
 117
 118         printf("Node 0x%lx= ", (unsigned long)p);
 119         printtree(p);
 120         printf(" matched rules:\n");
 121         for (nt = 1; burm_ntname[nt] != (char*)NULL; nt++)
 122                 if ((eruleno = burm_rule(STATE_LABEL(p), nt)) != 0)
 123                         printf("\t%s\n", burm_string[eruleno]);
 124 }
 125
 126 main() {
 127         NODEPTR_TYPE p;
 128
 129         p = buildtree(Assign,
 130                 buildtree(Constant, 0, 0),
 131                 buildtree(Fetch,
 132                         buildtree(Plus,
 133                                 buildtree(Constant, 0, 0),
 134                                 buildtree(Mul,
 135                                         buildtree(Four, 0, 0),
 136                                         buildtree(Fetch, buildtree(Constant, 0, 0), 0)
 137                                 )
 138                         ),
 139                         0
 140                 )
 141         );
 142         printtree(p);
 143         printf("\n\n");
 144         burm_label(p);
 145         printcover(p, 1, 0);
 146         printf("\nCover cost == %d\n\n", treecost(p, 1, 0));
 147         printMatches(p);
 148         return 0;
 149 }
 150