| |
| #include <stdio.h> |
| |
| typedef struct node *NODEPTR_TYPE; |
| |
| struct node { |
| int op, state_label; |
| NODEPTR_TYPE left, right; |
| }; |
| |
| #define OP_LABEL(p) ((p)->op) |
| #define STATE_LABEL(p) ((p)->state_label) |
| #define LEFT_CHILD(p) ((p)->left) |
| #define RIGHT_CHILD(p) ((p)->right) |
| #define PANIC printf |
| #ifndef burm_PANIC |
| #define burm_PANIC PANIC |
| #endif /* burm_PANIC */ |
| #ifdef __STDC__ |
| extern void abort(void); |
| #else |
| extern void abort(); |
| #endif |
| #ifdef NDEBUG |
| #define burm_assert(x,y) ; |
| #else |
| #define burm_assert(x,y) if(!(x)) {y; abort();} |
| #endif |
| static short burm_r1_nts[] ={ 0 }; |
| static short burm_r3_nts[] ={ 2, 0 }; |
| static short burm_r4_nts[] ={ 2, 1, 0 }; |
| static short burm_r6_nts[] ={ 3, 0 }; |
| static short burm_r7_nts[] ={ 3, 1, 0 }; |
| short *burm_nts[] = { |
| 0, |
| burm_r1_nts, |
| burm_r1_nts, |
| burm_r3_nts, |
| burm_r4_nts, |
| burm_r4_nts, |
| burm_r6_nts, |
| burm_r7_nts, |
| }; |
| static unsigned char burm_Assign_transition[2][2] = { |
| { 0, 0} /* row 0 */, |
| { 0, 1} /* row 1 */ |
| }; |
| static unsigned char burm_Mul_transition[2][2] = { |
| { 0, 0} /* row 0 */, |
| { 0, 1} /* row 1 */ |
| }; |
| static unsigned char burm_Plus_transition[2][3] = { |
| { 0, 0, 0} /* row 0 */, |
| { 0, 1, 2} /* row 1 */ |
| }; |
| static struct { |
| unsigned int f0:2; |
| unsigned int f1:2; |
| unsigned int f2:2; |
| unsigned int f3:2; |
| unsigned int f4:2; |
| unsigned int f5:3; |
| unsigned int f6:2; |
| unsigned int f7:2; |
| } burm_plank_0[] = { |
| { 0, 0, 0, 0, 0, 0, 0, 0,}, /* row 0 */ |
| { 0, 1, 0, 0, 1, 0, 0, 2,}, /* row 1 */ |
| { 1, 0, 0, 1, 0, 1, 1, 0,}, /* row 2 */ |
| { 0, 1, 0, 0, 1, 0, 0, 1,}, /* row 3 */ |
| { 1, 0, 1, 1, 0, 1, 2, 0,}, /* row 4 */ |
| { 0, 0, 0, 0, 2, 0, 0, 0,}, /* row 5 */ |
| { 1, 0, 0, 0, 0, 2, 0, 0,}, /* row 6 */ |
| { 1, 0, 0, 0, 0, 3, 0, 0,}, /* row 7 */ |
| }; |
| static short burm_eruleMap[] = { |
| 0, 3, 4, 5, 0, 1, 2, 0, 6, 7 |
| }; |
| #define burm_reg_rule(state) burm_eruleMap[burm_plank_0[state].f7 +7] |
| #define burm_con_rule(state) burm_eruleMap[burm_plank_0[state].f6 +4] |
| #define burm_addr_rule(state) burm_eruleMap[burm_plank_0[state].f5 +0] |
| |
| #ifdef __STDC__ |
| int burm_rule(int state, int goalnt) { |
| #else |
| int burm_rule(state, goalnt) int state; int goalnt; { |
| #endif |
| burm_assert(state >= 0 && state < 8, burm_PANIC("Bad state %d passed to burm_rule\n", state)); |
| switch(goalnt) { |
| case 1: |
| return burm_reg_rule(state); |
| case 2: |
| return burm_con_rule(state); |
| case 3: |
| return burm_addr_rule(state); |
| default: |
| burm_PANIC("Unknown nonterminal %d in burm_rule;\n", goalnt); |
| abort(); |
| return 0; |
| } |
| } |
| |
| int burm_TEMP; |
| #define burm_Assign_state(l,r) ( (burm_TEMP = burm_Assign_transition[burm_plank_0[l].f0][burm_plank_0[r].f1]) ? burm_TEMP + 0 : 0 ) |
| #define burm_Constant_state 2 |
| #define burm_Fetch_state(l) ( (burm_TEMP = burm_plank_0[l].f0) ? burm_TEMP + 2 : 0 ) |
| #define burm_Four_state 4 |
| #define burm_Mul_state(l,r) ( (burm_TEMP = burm_Mul_transition[burm_plank_0[l].f2][burm_plank_0[r].f1]) ? burm_TEMP + 4 : 0 ) |
| #define burm_Plus_state(l,r) ( (burm_TEMP = burm_Plus_transition[burm_plank_0[l].f3][burm_plank_0[r].f4]) ? burm_TEMP + 5 : 0 ) |
| |
| #ifdef __STDC__ |
| int burm_state(int op, int l, int r) { |
| #else |
| int burm_state(op, l, r) int op; int l; int r; { |
| #endif |
| register int burm_TEMP; |
| #ifndef NDEBUG |
| switch (op) { |
| case 1: |
| case 5: |
| case 6: |
| burm_assert(r >= 0 && r < 8, burm_PANIC("Bad state %d passed to burm_state\n", r)); |
| /*FALLTHROUGH*/ |
| case 3: |
| burm_assert(l >= 0 && l < 8, burm_PANIC("Bad state %d passed to burm_state\n", l)); |
| /*FALLTHROUGH*/ |
| case 2: |
| case 4: |
| break; |
| } |
| #endif |
| switch (op) { |
| default: burm_PANIC("Unknown op %d in burm_state\n", op); abort(); return 0; |
| case 1: |
| return burm_Assign_state(l,r); |
| case 2: |
| return burm_Constant_state; |
| case 3: |
| return burm_Fetch_state(l); |
| case 4: |
| return burm_Four_state; |
| case 5: |
| return burm_Mul_state(l,r); |
| case 6: |
| return burm_Plus_state(l,r); |
| } |
| } |
| #ifdef burm_STATE_LABEL |
| #define burm_INCLUDE_EXTRA |
| #else |
| #ifdef STATE_LABEL |
| #define burm_INCLUDE_EXTRA |
| #define burm_STATE_LABEL STATE_LABEL |
| #define burm_NODEPTR_TYPE NODEPTR_TYPE |
| #define burm_LEFT_CHILD LEFT_CHILD |
| #define burm_OP_LABEL OP_LABEL |
| #define burm_RIGHT_CHILD RIGHT_CHILD |
| #endif /* STATE_LABEL */ |
| #endif /* burm_STATE_LABEL */ |
| |
| #ifdef burm_INCLUDE_EXTRA |
| |
| #ifdef __STDC__ |
| int burm_label(burm_NODEPTR_TYPE n) { |
| #else |
| int burm_label(n) burm_NODEPTR_TYPE n; { |
| #endif |
| burm_assert(n, burm_PANIC("NULL pointer passed to burm_label\n")); |
| switch (burm_OP_LABEL(n)) { |
| default: burm_PANIC("Bad op %d in burm_label\n", burm_OP_LABEL(n)); abort(); return 0; |
| case 2: |
| case 4: |
| return burm_STATE_LABEL(n) = burm_state(burm_OP_LABEL(n), 0, 0); |
| case 3: |
| return burm_STATE_LABEL(n) = burm_state(burm_OP_LABEL(n), burm_label(burm_LEFT_CHILD(n)), 0); |
| case 1: |
| case 5: |
| case 6: |
| return burm_STATE_LABEL(n) = burm_state(burm_OP_LABEL(n), burm_label(burm_LEFT_CHILD(n)), burm_label(burm_RIGHT_CHILD(n))); |
| } |
| } |
| #ifdef __STDC__ |
| burm_NODEPTR_TYPE * burm_kids(burm_NODEPTR_TYPE p, int rulenumber, burm_NODEPTR_TYPE *kids) { |
| #else |
| burm_NODEPTR_TYPE * burm_kids(p, rulenumber, kids) burm_NODEPTR_TYPE p; int rulenumber; burm_NODEPTR_TYPE *kids; { |
| #endif |
| burm_assert(p, burm_PANIC("NULL node pointer passed to burm_kids\n")); |
| burm_assert(kids, burm_PANIC("NULL kids pointer passed to burm_kids\n")); |
| switch (rulenumber) { |
| default: |
| burm_PANIC("Unknown Rule %d in burm_kids;\n", rulenumber); |
| abort(); |
| /* NOTREACHED */ |
| case 1: |
| case 2: |
| break; |
| case 3: |
| kids[0] = p; |
| break; |
| case 5: |
| kids[0] = burm_LEFT_CHILD(p); |
| kids[1] = burm_RIGHT_CHILD(burm_RIGHT_CHILD(p)); |
| break; |
| case 6: |
| kids[0] = burm_LEFT_CHILD(p); |
| break; |
| case 4: |
| case 7: |
| kids[0] = burm_LEFT_CHILD(p); |
| kids[1] = burm_RIGHT_CHILD(p); |
| break; |
| } |
| return kids; |
| } |
| #endif /* burm_INCLUDE_EXTRA */ |
| #define burm_addr_NT 3 |
| #define burm_con_NT 2 |
| #define burm_reg_NT 1 |
| #define burm_NT 3 |
| short burm_closure[4][4] = { |
| { 0, 0, 0, 0,}, |
| { 0, 0, 0, 0,}, |
| { 0, 0, 0, 0,}, |
| { 0, 0, 3, 0,}, |
| }; |
| |
| |
| #define Assign 1 |
| #define Constant 2 |
| #define Fetch 3 |
| #define Four 4 |
| #define Mul 5 |
| #define Plus 6 |
| |
| #ifdef __STDC__ |
| #define ARGS(x) x |
| #else |
| #define ARGS(x) () |
| #endif |
| |
| NODEPTR_TYPE buildtree ARGS((int, NODEPTR_TYPE, NODEPTR_TYPE)); |
| void printcover ARGS((NODEPTR_TYPE, int, int)); |
| void printtree ARGS((NODEPTR_TYPE)); |
| int treecost ARGS((NODEPTR_TYPE, int, int)); |
| void printMatches ARGS((NODEPTR_TYPE)); |
| int main ARGS((void)); |
| |
| NODEPTR_TYPE buildtree(op, left, right) int op; NODEPTR_TYPE left; NODEPTR_TYPE right; { |
| NODEPTR_TYPE p; |
| extern void *malloc ARGS((unsigned)); |
| |
| p = (NODEPTR_TYPE) malloc(sizeof *p); |
| p->op = op; |
| p->left = left; |
| p->right = right; |
| return p; |
| } |
| |
| void printcover(p, goalnt, indent) NODEPTR_TYPE p; int goalnt; int indent; { |
| int eruleno = burm_rule(STATE_LABEL(p), goalnt); |
| short *nts = burm_nts[eruleno]; |
| NODEPTR_TYPE kids[10]; |
| int i; |
| |
| if (eruleno == 0) { |
| printf("no cover\n"); |
| return; |
| } |
| for (i = 0; i < indent; i++) |
| printf("."); |
| printf("%s\n", burm_string[eruleno]); |
| burm_kids(p, eruleno, kids); |
| for (i = 0; nts[i]; i++) |
| printcover(kids[i], nts[i], indent+1); |
| } |
| |
| void printtree(p) NODEPTR_TYPE p; { |
| int op = burm_op_label(p); |
| |
| printf("%s", burm_opname[op]); |
| switch (burm_arity[op]) { |
| case 0: |
| break; |
| case 1: |
| printf("("); |
| printtree(burm_child(p, 0)); |
| printf(")"); |
| break; |
| case 2: |
| printf("("); |
| printtree(burm_child(p, 0)); |
| printf(", "); |
| printtree(burm_child(p, 1)); |
| printf(")"); |
| break; |
| } |
| } |
| |
| int treecost(p, goalnt, costindex) NODEPTR_TYPE p; int goalnt; int costindex; { |
| int eruleno = burm_rule(STATE_LABEL(p), goalnt); |
| int cost = burm_cost[eruleno][costindex], i; |
| short *nts = burm_nts[eruleno]; |
| NODEPTR_TYPE kids[10]; |
| |
| burm_kids(p, eruleno, kids); |
| for (i = 0; nts[i]; i++) |
| cost += treecost(kids[i], nts[i], costindex); |
| return cost; |
| } |
| |
| void printMatches(p) NODEPTR_TYPE p; { |
| int nt; |
| int eruleno; |
| |
| printf("Node 0x%lx= ", (unsigned long)p); |
| printtree(p); |
| printf(" matched rules:\n"); |
| for (nt = 1; burm_ntname[nt] != (char*)NULL; nt++) |
| if ((eruleno = burm_rule(STATE_LABEL(p), nt)) != 0) |
| printf("\t%s\n", burm_string[eruleno]); |
| } |
| |
| main() { |
| NODEPTR_TYPE p; |
| |
| p = buildtree(Assign, |
| buildtree(Constant, 0, 0), |
| buildtree(Fetch, |
| buildtree(Plus, |
| buildtree(Constant, 0, 0), |
| buildtree(Mul, |
| buildtree(Four, 0, 0), |
| buildtree(Fetch, buildtree(Constant, 0, 0), 0) |
| ) |
| ), |
| 0 |
| ) |
| ); |
| printtree(p); |
| printf("\n\n"); |
| burm_label(p); |
| printcover(p, 1, 0); |
| printf("\nCover cost == %d\n\n", treecost(p, 1, 0)); |
| printMatches(p); |
| return 0; |
| } |
| |
| exit 0 |