URL https://opencores.org/ocsvn/eco32/eco32/trunk

Subversion Repositories eco32

[/] [eco32/] [trunk/] [lcc/] [lburg/] [lburg.c] - Blame information for rev 4

Details | Compare with Previous | View Log


#include <assert.h>
#include <ctype.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "lburg.h"
 
static char rcsid[] = "$Id: lburg.c,v 2.10 2002/03/08 18:45:21 drh Exp $";
static char *prefix = "";
static int Tflag = 0;
static int ntnumber = 0;
static Nonterm start = 0;
static Term terms;
static Nonterm nts;
static Rule rules;
static int nrules;
static struct block {
        struct block *link;
} *memlist;                     /* list of allocated blocks */
 
static char *stringf(char *fmt, ...);
static void print(char *fmt, ...);
static void ckreach(Nonterm p);
static void emitclosure(Nonterm nts);
static void emitcost(Tree t, char *v);
static void emitdefs(Nonterm nts, int ntnumber);
static void emitheader(void);
static void emitkids(Rule rules, int nrules);
static void emitnts(Rule rules, int nrules);
static void emitrecalc(char *pre, Term root, Term kid);
static void emitrecord(char *pre, Rule r, char *c, int cost);
static void emitrule(Nonterm nts);
static void emitlabel(Term terms, Nonterm start, int ntnumber);
static void emitstring(Rule rules);
static void emitstruct(Nonterm nts, int ntnumber);
static void emittest(Tree t, char *v, char *suffix);
 
int main(int argc, char *argv[]) {
        int c, i;
        Nonterm p;
 
        for (i = 1; i < argc; i++)
                if (strcmp(argv[i], "-T") == 0)
                        Tflag = 1;
                else if (strncmp(argv[i], "-p", 2) == 0 && argv[i][2])
                        prefix = &argv[i][2];
                else if (strncmp(argv[i], "-p", 2) == 0 && i + 1 < argc)
                        prefix = argv[++i];
                else if (*argv[i] == '-' && argv[i][1]) {
                        yyerror("usage: %s [-T | -p prefix]... [ [ input ] output ] \n",
                                argv[0]);
                        exit(1);
                } else if (infp == NULL) {
                        if (strcmp(argv[i], "-") == 0)
                                infp = stdin;
                        else if ((infp = fopen(argv[i], "r")) == NULL) {
                                yyerror("%s: can't read `%s'\n", argv[0], argv[i]);
                                exit(1);
                        }
                } else if (outfp == NULL) {
                        if (strcmp(argv[i], "-") == 0)
                                outfp = stdout;
                        if ((outfp = fopen(argv[i], "w")) == NULL) {
                                yyerror("%s: can't write `%s'\n", argv[0], argv[i]);
                                exit(1);
                        }
                }
        if (infp == NULL)
                infp = stdin;
        if (outfp == NULL)
                outfp = stdout;
        yyparse();
        if (start)
                ckreach(start);
        for (p = nts; p; p = p->link) {
                if (p->rules == NULL)
                        yyerror("undefined nonterminal `%s'\n", p->name);
                if (!p->reached)
                        yyerror("can't reach nonterminal `%s'\n", p->name);
        }
        emitheader();
        emitdefs(nts, ntnumber);
        emitstruct(nts, ntnumber);
        emitnts(rules, nrules);
        emitstring(rules);
        emitrule(nts);
        emitclosure(nts);
        if (start)
                emitlabel(terms, start, ntnumber);
        emitkids(rules, nrules);
        if (!feof(infp))
                while ((c = getc(infp)) != EOF)
                        putc(c, outfp);
        while (memlist) {       /* for purify */
                struct block *q = memlist->link;
                free(memlist);
                memlist = q;
        }
        return errcnt > 0;
}
 
/* alloc - allocate nbytes or issue fatal error */
void *alloc(int nbytes) {
        struct block *p = calloc(1, sizeof *p + nbytes);
 
        if (p == NULL) {
                yyerror("out of memory\n");
                exit(1);
        }
        p->link = memlist;
        memlist = p;
        return p + 1;
}
 
/* stringf - format and save a string */
static char *stringf(char *fmt, ...) {
        va_list ap;
        char buf[512];
 
        va_start(ap, fmt);
        vsprintf(buf, fmt, ap);
        va_end(ap);
        return strcpy(alloc(strlen(buf) + 1), buf);
}
 
struct entry {
        union {
                char *name;
                struct term t;
                struct nonterm nt;
        } sym;
        struct entry *link;
} *table[211];
#define HASHSIZE (sizeof table/sizeof table[0])
 
/* hash - return hash number for str */
static unsigned hash(char *str) {
        unsigned h = 0;
 
        while (*str)
                h = (h<<1) + *str++;
        return h;
}
 
/* lookup - lookup symbol name */
static void *lookup(char *name) {
        struct entry *p = table[hash(name)%HASHSIZE];
 
        for ( ; p; p = p->link)
                if (strcmp(name, p->sym.name) == 0)
                        return &p->sym;
        return 0;
}
 
/* install - install symbol name */
static void *install(char *name) {
        struct entry *p = alloc(sizeof *p);
        int i = hash(name)%HASHSIZE;
 
        p->sym.name = name;
        p->link = table[i];
        table[i] = p;
        return &p->sym;
}
 
/* nonterm - create a new terminal id, if necessary */
Nonterm nonterm(char *id) {
        Nonterm p = lookup(id), *q = &nts;
 
        if (p && p->kind == NONTERM)
                return p;
        if (p && p->kind == TERM)
                yyerror("`%s' is a terminal\n", id);
        p = install(id);
        p->kind = NONTERM;
        p->number = ++ntnumber;
        if (p->number == 1)
                start = p;
        while (*q && (*q)->number < p->number)
                q = &(*q)->link;
        assert(*q == 0 || (*q)->number != p->number);
        p->link = *q;
        *q = p;
        return p;
}
 
/* term - create a new terminal id with external symbol number esn */
Term term(char *id, int esn) {
        Term p = lookup(id), *q = &terms;
 
        if (p)
                yyerror("redefinition of terminal `%s'\n", id);
        else
                p = install(id);
        p->kind = TERM;
        p->esn = esn;
        p->arity = -1;
        while (*q && (*q)->esn < p->esn)
                q = &(*q)->link;
        if (*q && (*q)->esn == p->esn)
                yyerror("duplicate external symbol number `%s=%d'\n",
                        p->name, p->esn);
        p->link = *q;
        *q = p;
        return p;
}
 
/* tree - create & initialize a tree node with the given fields */
Tree tree(char *id, Tree left, Tree right) {
        Tree t = alloc(sizeof *t);
        Term p = lookup(id);
        int arity = 0;
 
        if (left && right)
                arity = 2;
        else if (left)
                arity = 1;
        if (p == NULL && arity > 0) {
                yyerror("undefined terminal `%s'\n", id);
                p = term(id, -1);
        } else if (p == NULL && arity == 0)
                p = (Term)nonterm(id);
        else if (p && p->kind == NONTERM && arity > 0) {
                yyerror("`%s' is a nonterminal\n", id);
                p = term(id, -1);
        }
        if (p->kind == TERM && p->arity == -1)
                p->arity = arity;
        if (p->kind == TERM && arity != p->arity)
                yyerror("inconsistent arity for terminal `%s'\n", id);
        t->op = p;
        t->nterms = p->kind == TERM;
        if ((t->left = left) != NULL)
                t->nterms += left->nterms;
        if ((t->right = right) != NULL)
                t->nterms += right->nterms;
        return t;
}
 
/* rule - create & initialize a rule with the given fields */
Rule rule(char *id, Tree pattern, char *template, char *code) {
        Rule r = alloc(sizeof *r), *q;
        Term p = pattern->op;
        char *end;
 
        r->lhs = nonterm(id);
        r->packed = ++r->lhs->lhscount;
        for (q = &r->lhs->rules; *q; q = &(*q)->decode)
                ;
        *q = r;
        r->pattern = pattern;
        r->ern = ++nrules;
        r->template = template;
        r->code = code;
        r->cost = strtol(code, &end, 10);
        if (*end) {
                r->cost = -1;
                r->code = stringf("(%s)", code);
        }
        if (p->kind == TERM) {
                for (q = &p->rules; *q; q = &(*q)->next)
                        ;
                *q = r;
        } else if (pattern->left == NULL && pattern->right == NULL) {
                Nonterm p = pattern->op;
                r->chain = p->chain;
                p->chain = r;
                if (r->cost == -1)
                        yyerror("illegal nonconstant cost `%s'\n", code);
        }
        for (q = &rules; *q; q = &(*q)->link)
                ;
        r->link = *q;
        *q = r;
        return r;
}
 
/* print - formatted output */
static void print(char *fmt, ...) {
        va_list ap;
 
        va_start(ap, fmt);
        for ( ; *fmt; fmt++)
                if (*fmt == '%')
                        switch (*++fmt) {
                        case 'd': fprintf(outfp, "%d", va_arg(ap, int)); break;
                        case 's': fputs(va_arg(ap, char *), outfp); break;
                        case 'P': fprintf(outfp, "%s_", prefix); break;
                        case 'T': {
                                Tree t = va_arg(ap, Tree);
                                print("%S", t->op);
                                if (t->left && t->right)
                                        print("(%T,%T)", t->left, t->right);
                                else if (t->left)
                                        print("(%T)", t->left);
                                break;
                                }
                        case 'R': {
                                Rule r = va_arg(ap, Rule);
                                print("%S: %T", r->lhs, r->pattern);
                                break;
                                }
                        case 'S': {
                                Term t = va_arg(ap, Term);
                                fputs(t->name, outfp);
                                break;
                                }
                        case '1': case '2': case '3': case '4': case '5': {
                                int n = *fmt - '0';
                                while (n-- > 0)
                                        putc('\t', outfp);
                                break;
                                }
                        default: putc(*fmt, outfp); break;
                        }
                else
                        putc(*fmt, outfp);
        va_end(ap);
}
 
/* reach - mark all nonterminals in tree t as reachable */
static void reach(Tree t) {
        Nonterm p = t->op;
 
        if (p->kind == NONTERM)
                if (!p->reached)
                        ckreach(p);
        if (t->left)
                reach(t->left);
        if (t->right)
                reach(t->right);
}
 
/* ckreach - mark all nonterminals reachable from p */
static void ckreach(Nonterm p) {
        Rule r;
 
        p->reached = 1;
        for (r = p->rules; r; r = r->decode)
                reach(r->pattern);
}
 
/* emitcase - emit one case in function state */
static void emitcase(Term p, int ntnumber) {
        Rule r;
 
        print("%1case %d: /* %S */\n", p->esn, p);
        switch (p->arity) {
        case 0: case -1:
                break;
        case 1:
                print("%2%Plabel(LEFT_CHILD(a));\n");
                break;
        case 2:
                print("%2%Plabel(LEFT_CHILD(a));\n");
                print("%2%Plabel(RIGHT_CHILD(a));\n");
                break;
        default: assert(0);
        }
        for (r = p->rules; r; r = r->next) {
                char *indent = "\t\t\0";
                switch (p->arity) {
                case 0: case -1:
                        print("%2/* %R */\n", r);
                        if (r->cost == -1) {
                                print("%2c = %s;\n", r->code);
                                emitrecord("\t\t", r, "c", 0);
                        } else
                                emitrecord("\t\t", r, r->code, 0);
                        break;
                case 1:
                        if (r->pattern->nterms > 1) {
                                print("%2if (%1/* %R */\n", r);
                                emittest(r->pattern->left, "LEFT_CHILD(a)", " ");
                                print("%2) {\n");
                                indent = "\t\t\t";
                        } else
                                print("%2/* %R */\n", r);
                        if (r->pattern->nterms == 2 && r->pattern->left
                        &&  r->pattern->right == NULL)
                                emitrecalc(indent, r->pattern->op, r->pattern->left->op);
                        print("%sc = ", indent);
                        emitcost(r->pattern->left, "LEFT_CHILD(a)");
                        print("%s;\n", r->code);
                        emitrecord(indent, r, "c", 0);
                        if (indent[2])
                                print("%2}\n");
                        break;
                case 2:
                        if (r->pattern->nterms > 1) {
                                print("%2if (%1/* %R */\n", r);
                                emittest(r->pattern->left,  "LEFT_CHILD(a)",
                                        r->pattern->right->nterms ? " && " : " ");
                                emittest(r->pattern->right, "RIGHT_CHILD(a)", " ");
                                print("%2) {\n");
                                indent = "\t\t\t";
                        } else
                                print("%2/* %R */\n", r);
                        print("%sc = ", indent);
                        emitcost(r->pattern->left,  "LEFT_CHILD(a)");
                        emitcost(r->pattern->right, "RIGHT_CHILD(a)");
                        print("%s;\n", r->code);
                        emitrecord(indent, r, "c", 0);
                        if (indent[2])
                                print("%2}\n");
                        break;
                default: assert(0);
                }
        }
        print("%2break;\n");
}
 
/* emitclosure - emit the closure functions */
static void emitclosure(Nonterm nts) {
        Nonterm p;
 
        for (p = nts; p; p = p->link)
                if (p->chain)
                        print("static void %Pclosure_%S(NODEPTR_TYPE, int);\n", p);
        print("\n");
        for (p = nts; p; p = p->link)
                if (p->chain) {
                        Rule r;
                        print("static void %Pclosure_%S(NODEPTR_TYPE a, int c) {\n"
"%1struct %Pstate *p = STATE_LABEL(a);\n", p);
                        for (r = p->chain; r; r = r->chain)
                                emitrecord("\t", r, "c", r->cost);
                        print("}\n\n");
                }
}
 
/* emitcost - emit cost computation for tree t */
static void emitcost(Tree t, char *v) {
        Nonterm p = t->op;
 
        if (p->kind == TERM) {
                if (t->left)
                        emitcost(t->left,  stringf("LEFT_CHILD(%s)",  v));
                if (t->right)
                        emitcost(t->right, stringf("RIGHT_CHILD(%s)", v));
        } else
                print("((struct %Pstate *)(%s->x.state))->cost[%P%S_NT] + ", v, p);
}
 
/* emitdefs - emit nonterminal defines and data structures */
static void emitdefs(Nonterm nts, int ntnumber) {
        Nonterm p;
 
        for (p = nts; p; p = p->link)
                print("#define %P%S_NT %d\n", p, p->number);
        print("\n");
        print("static char *%Pntname[] = {\n%10,\n");
        for (p = nts; p; p = p->link)
                print("%1\"%S\",\n", p);
        print("%10\n};\n\n");
}
 
/* emitheader - emit initial definitions */
static void emitheader(void) {
        time_t timer = time(NULL);
 
        print("/*\ngenerated at %sby %s\n*/\n", ctime(&timer), rcsid);
        print("static void %Pkids(NODEPTR_TYPE, int, NODEPTR_TYPE[]);\n");
        print("static void %Plabel(NODEPTR_TYPE);\n");
        print("static int %Prule(void*, int);\n\n");
}
 
/* computekids - compute paths to kids in tree t */
static char *computekids(Tree t, char *v, char *bp, int *ip) {
        Term p = t->op;
 
        if (p->kind == NONTERM) {
                sprintf(bp, "\t\tkids[%d] = %s;\n", (*ip)++, v);
                bp += strlen(bp);
        } else if (p->arity > 0) {
                bp = computekids(t->left, stringf("LEFT_CHILD(%s)", v), bp, ip);
                if (p->arity == 2)
                        bp = computekids(t->right, stringf("RIGHT_CHILD(%s)", v), bp, ip);
        }
        return bp;
}
 
/* emitkids - emit _kids */
static void emitkids(Rule rules, int nrules) {
        int i;
        Rule r, *rc = alloc((nrules + 1 + 1)*sizeof *rc);
        char **str  = alloc((nrules + 1 + 1)*sizeof *str);
 
        for (i = 0, r = rules; r; r = r->link) {
                int j = 0;
                char buf[1024], *bp = buf;
                *computekids(r->pattern, "p", bp, &j) = 0;
                for (j = 0; str[j] && strcmp(str[j], buf); j++)
                        ;
                if (str[j] == NULL)
                        str[j] = strcpy(alloc(strlen(buf) + 1), buf);
                r->kids = rc[j];
                rc[j] = r;
        }
        print("static void %Pkids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]) {\n"
"%1if (!p)\n%2fatal(\"%Pkids\", \"Null tree\\n\", 0);\n"
"%1if (!kids)\n%2fatal(\"%Pkids\", \"Null kids\\n\", 0);\n"
"%1switch (eruleno) {\n");
        for (i = 0; (r = rc[i]) != NULL; i++) {
                for ( ; r; r = r->kids)
                        print("%1case %d: /* %R */\n", r->ern, r);
                print("%s%2break;\n", str[i]);
        }
        print("%1default:\n%2fatal(\"%Pkids\", \"Bad rule number %%d\\n\", eruleno);\n%1}\n}\n\n");
}
 
/* emitlabel - emit label function */
static void emitlabel(Term terms, Nonterm start, int ntnumber) {
        int i;
        Term p;
 
        print("static void %Plabel(NODEPTR_TYPE a) {\n%1int c;\n"
"%1struct %Pstate *p;\n\n"
"%1if (!a)\n%2fatal(\"%Plabel\", \"Null tree\\n\", 0);\n");
        print("%1STATE_LABEL(a) = p = allocate(sizeof *p, FUNC);\n"
"%1p->rule._stmt = 0;\n");
        for (i = 1; i <= ntnumber; i++)
                print("%1p->cost[%d] =\n", i);
        print("%20x7fff;\n%1switch (OP_LABEL(a)) {\n");
        for (p = terms; p; p = p->link)
                emitcase(p, ntnumber);
        print("%1default:\n"
"%2fatal(\"%Plabel\", \"Bad terminal %%d\\n\", OP_LABEL(a));\n%1}\n}\n\n");
}
 
/* computents - fill in bp with _nts vector for tree t */
static char *computents(Tree t, char *bp) {
        if (t) {
                Nonterm p = t->op;
                if (p->kind == NONTERM) {
                        sprintf(bp, "%s_%s_NT, ", prefix, p->name);
                        bp += strlen(bp);
                } else
                        bp = computents(t->right, computents(t->left,  bp));
        }
        return bp;
}
 
/* emitnts - emit _nts ragged array */
static void emitnts(Rule rules, int nrules) {
        Rule r;
        int i, j, *nts = alloc((nrules + 1)*sizeof *nts);
        char **str = alloc((nrules + 1)*sizeof *str);
 
        for (i = 0, r = rules; r; r = r->link) {
                char buf[1024];
                *computents(r->pattern, buf) = 0;
                for (j = 0; str[j] && strcmp(str[j], buf); j++)
                        ;
                if (str[j] == NULL) {
                        print("static short %Pnts_%d[] = { %s0 };\n", j, buf);
                        str[j] = strcpy(alloc(strlen(buf) + 1), buf);
                }
                nts[i++] = j;
        }
        print("\nstatic short *%Pnts[] = {\n");
        for (i = j = 0, r = rules; r; r = r->link) {
                for ( ; j < r->ern; j++)
                        print("%10,%1/* %d */\n", j);
                print("%1%Pnts_%d,%1/* %d */\n", nts[i++], j++);
        }
        print("};\n\n");
}
 
/* emitrecalc - emit code that tests for recalculation of INDIR?(VREGP) */
static void emitrecalc(char *pre, Term root, Term kid) {
        if (root->kind == TERM && strncmp(root->name, "INDIR", 5) == 0
        &&   kid->kind == TERM &&  strcmp(kid->name,  "VREGP"   ) == 0) {
                Nonterm p;
                print("%sif (mayrecalc(a)) {\n", pre);
                print("%s%1struct %Pstate *q = a->syms[RX]->u.t.cse->x.state;\n", pre);
                for (p = nts; p; p = p->link) {
                        print("%s%1if (q->cost[%P%S_NT] == 0) {\n", pre, p);
                        print("%s%2p->cost[%P%S_NT] = 0;\n", pre, p);
                        print("%s%2p->rule.%P%S = q->rule.%P%S;\n", pre, p, p);
                        print("%s%1}\n", pre);
                }
                print("%s}\n", pre);
        }
}
 
/* emitrecord - emit code that tests for a winning match of rule r */
static void emitrecord(char *pre, Rule r, char *c, int cost) {
        if (Tflag)
                print("%s%Ptrace(a, %d, %s + %d, p->cost[%P%S_NT]);\n",
                        pre, r->ern, c, cost, r->lhs);
        print("%sif (", pre);
        print("%s + %d < p->cost[%P%S_NT]) {\n"
"%s%1p->cost[%P%S_NT] = %s + %d;\n%s%1p->rule.%P%S = %d;\n",
                c, cost, r->lhs, pre, r->lhs, c, cost, pre, r->lhs,
                r->packed);
        if (r->lhs->chain)
                print("%s%1%Pclosure_%S(a, %s + %d);\n", pre, r->lhs, c, cost);
        print("%s}\n", pre);
}
 
/* emitrule - emit decoding vectors and _rule */
static void emitrule(Nonterm nts) {
        Nonterm p;
 
        for (p = nts; p; p = p->link) {
                Rule r;
                print("static short %Pdecode_%S[] = {\n%10,\n", p);
                for (r = p->rules; r; r = r->decode)
                        print("%1%d,\n", r->ern);
                print("};\n\n");
        }
        print("static int %Prule(void *state, int goalnt) {\n"
"%1if (goalnt < 1 || goalnt > %d)\n%2fatal(\"%Prule\", \"Bad goal nonterminal %%d\\n\", goalnt);\n"
"%1if (!state)\n%2return 0;\n%1switch (goalnt) {\n", ntnumber);
        for (p = nts; p; p = p->link)
                print("%1case %P%S_NT:"
"%1return %Pdecode_%S[((struct %Pstate *)state)->rule.%P%S];\n", p, p, p);
        print("%1default:\n%2fatal(\"%Prule\", \"Bad goal nonterminal %%d\\n\", goalnt);\n%2return 0;\n%1}\n}\n\n");
}
 
/* emitstring - emit arrays of templates, instruction flags, and rules */
static void emitstring(Rule rules) {
        Rule r;
 
        print("static char *%Ptemplates[] = {\n");
        print("/* 0 */%10,\n");
        for (r = rules; r; r = r->link)
                print("/* %d */%1\"%s\",%1/* %R */\n", r->ern, r->template, r);
        print("};\n");
        print("\nstatic char %Pisinstruction[] = {\n");
        print("/* 0 */%10,\n");
        for (r = rules; r; r = r->link) {
                int len = strlen(r->template);
                print("/* %d */%1%d,%1/* %s */\n", r->ern,
                        len >= 2 && r->template[len-2] == '\\' && r->template[len-1] == 'n',
                        r->template);
        }
        print("};\n");
        print("\nstatic char *%Pstring[] = {\n");
        print("/* 0 */%10,\n");
        for (r = rules; r; r = r->link)
                print("/* %d */%1\"%R\",\n", r->ern, r);
        print("};\n\n");
}
 
/* emitstruct - emit the definition of the state structure */
static void emitstruct(Nonterm nts, int ntnumber) {
        print("struct %Pstate {\n%1short cost[%d];\n%1struct {\n", ntnumber + 1);
        for ( ; nts; nts = nts->link) {
                int n = 1, m = nts->lhscount;
                while ((m >>= 1) != 0)
                        n++;
                print("%2unsigned int %P%S:%d;\n", nts, n);
        }
        print("%1} rule;\n};\n\n");
}
 
/* emittest - emit clause for testing a match */
static void emittest(Tree t, char *v, char *suffix) {
        Term p = t->op;
 
        if (p->kind == TERM) {
                print("%3%s->op == %d%s/* %S */\n", v, p->esn,
                        t->nterms > 1 ? " && " : suffix, p);
                if (t->left)
                        emittest(t->left, stringf("LEFT_CHILD(%s)",  v),
                                t->right && t->right->nterms ? " && " : suffix);
                if (t->right)
                        emittest(t->right, stringf("RIGHT_CHILD(%s)", v), suffix);
        }
}

Browse

Tools

Subversion Repositories eco32

[/] [eco32/] [trunk/] [lcc/] [lburg/] [lburg.c] - Blame information for rev 4

Line No.	Rev	Author	Line
1	4	hellwig	`#include <assert.h>`
2			`#include <ctype.h>`
3			`#include <stdarg.h>`
4			`#include <stdlib.h>`
5			`#include <stdio.h>`
6			`#include <string.h>`
7			`#include <time.h>`
8			`#include "lburg.h"`
9
10			`static char rcsid[] = "$Id: lburg.c,v 2.10 2002/03/08 18:45:21 drh Exp $";`
11			`static char *prefix = "";`
12			`static int Tflag = 0;`
13			`static int ntnumber = 0;`
14			`static Nonterm start = 0;`
15			`static Term terms;`
16			`static Nonterm nts;`
17			`static Rule rules;`
18			`static int nrules;`
19			`static struct block {`
20			`struct block *link;`
21			`} memlist; / list of allocated blocks */`
22
23			`static char stringf(char fmt, ...);`
24			`static void print(char *fmt, ...);`
25			`static void ckreach(Nonterm p);`
26			`static void emitclosure(Nonterm nts);`
27			`static void emitcost(Tree t, char *v);`
28			`static void emitdefs(Nonterm nts, int ntnumber);`
29			`static void emitheader(void);`
30			`static void emitkids(Rule rules, int nrules);`
31			`static void emitnts(Rule rules, int nrules);`
32			`static void emitrecalc(char *pre, Term root, Term kid);`
33			`static void emitrecord(char pre, Rule r, char c, int cost);`
34			`static void emitrule(Nonterm nts);`
35			`static void emitlabel(Term terms, Nonterm start, int ntnumber);`
36			`static void emitstring(Rule rules);`
37			`static void emitstruct(Nonterm nts, int ntnumber);`
38			`static void emittest(Tree t, char v, char suffix);`
39
40			`int main(int argc, char *argv[]) {`
41			`int c, i;`
42			`Nonterm p;`
43
44			`for (i = 1; i < argc; i++)`
45			`if (strcmp(argv[i], "-T") == 0)`
46			`Tflag = 1;`
47			`else if (strncmp(argv[i], "-p", 2) == 0 && argv[i][2])`
48			`prefix = &argv[i][2];`
49			`else if (strncmp(argv[i], "-p", 2) == 0 && i + 1 < argc)`
50			`prefix = argv[++i];`
51			`else if (*argv[i] == '-' && argv[i][1]) {`
52			`yyerror("usage: %s [-T \| -p prefix]... [ [ input ] output ] \n",`
53			`argv[0]);`
54			`exit(1);`
55			`} else if (infp == NULL) {`
56			`if (strcmp(argv[i], "-") == 0)`
57			`infp = stdin;`
58			`else if ((infp = fopen(argv[i], "r")) == NULL) {`
59			yyerror("%s: can't read `%s'\n", argv[0], argv[i]);
60			`exit(1);`
61			`}`
62			`} else if (outfp == NULL) {`
63			`if (strcmp(argv[i], "-") == 0)`
64			`outfp = stdout;`
65			`if ((outfp = fopen(argv[i], "w")) == NULL) {`
66			yyerror("%s: can't write `%s'\n", argv[0], argv[i]);
67			`exit(1);`
68			`}`
69			`}`
70			`if (infp == NULL)`
71			`infp = stdin;`
72			`if (outfp == NULL)`
73			`outfp = stdout;`
74			`yyparse();`
75			`if (start)`
76			`ckreach(start);`
77			`for (p = nts; p; p = p->link) {`
78			`if (p->rules == NULL)`
79			yyerror("undefined nonterminal `%s'\n", p->name);
80			`if (!p->reached)`
81			yyerror("can't reach nonterminal `%s'\n", p->name);
82			`}`
83			`emitheader();`
84			`emitdefs(nts, ntnumber);`
85			`emitstruct(nts, ntnumber);`
86			`emitnts(rules, nrules);`
87			`emitstring(rules);`
88			`emitrule(nts);`
89			`emitclosure(nts);`
90			`if (start)`
91			`emitlabel(terms, start, ntnumber);`
92			`emitkids(rules, nrules);`
93			`if (!feof(infp))`
94			`while ((c = getc(infp)) != EOF)`
95			`putc(c, outfp);`
96			`while (memlist) { /* for purify */`
97			`struct block *q = memlist->link;`
98			`free(memlist);`
99			`memlist = q;`
100			`}`
101			`return errcnt > 0;`
102			`}`
103
104			`/* alloc - allocate nbytes or issue fatal error */`
105			`void *alloc(int nbytes) {`
106			`struct block p = calloc(1, sizeof p + nbytes);`
107
108			`if (p == NULL) {`
109			`yyerror("out of memory\n");`
110			`exit(1);`
111			`}`
112			`p->link = memlist;`
113			`memlist = p;`
114			`return p + 1;`
115			`}`
116
117			`/* stringf - format and save a string */`
118			`static char stringf(char fmt, ...) {`
119			`va_list ap;`
120			`char buf[512];`
121
122			`va_start(ap, fmt);`
123			`vsprintf(buf, fmt, ap);`
124			`va_end(ap);`
125			`return strcpy(alloc(strlen(buf) + 1), buf);`
126			`}`
127
128			`struct entry {`
129			`union {`
130			`char *name;`
131			`struct term t;`
132			`struct nonterm nt;`
133			`} sym;`
134			`struct entry *link;`
135			`} *table[211];`
136			`#define HASHSIZE (sizeof table/sizeof table[0])`
137
138			`/* hash - return hash number for str */`
139			`static unsigned hash(char *str) {`
140			`unsigned h = 0;`
141
142			`while (*str)`
143			`h = (h<<1) + *str++;`
144			`return h;`
145			`}`
146
147			`/* lookup - lookup symbol name */`
148			`static void lookup(char name) {`
149			`struct entry *p = table[hash(name)%HASHSIZE];`
150
151			`for ( ; p; p = p->link)`
152			`if (strcmp(name, p->sym.name) == 0)`
153			`return &p->sym;`
154			`return 0;`
155			`}`
156
157			`/* install - install symbol name */`
158			`static void install(char name) {`
159			`struct entry p = alloc(sizeof p);`
160			`int i = hash(name)%HASHSIZE;`
161
162			`p->sym.name = name;`
163			`p->link = table[i];`
164			`table[i] = p;`
165			`return &p->sym;`
166			`}`
167
168			`/* nonterm - create a new terminal id, if necessary */`
169			`Nonterm nonterm(char *id) {`
170			`Nonterm p = lookup(id), *q = &nts;`
171
172			`if (p && p->kind == NONTERM)`
173			`return p;`
174			`if (p && p->kind == TERM)`
175			yyerror("`%s' is a terminal\n", id);
176			`p = install(id);`
177			`p->kind = NONTERM;`
178			`p->number = ++ntnumber;`
179			`if (p->number == 1)`
180			`start = p;`
181			`while (q && (q)->number < p->number)`
182			`q = &(*q)->link;`
183			`assert(q == 0 \|\| (q)->number != p->number);`
184			`p->link = *q;`
185			`*q = p;`
186			`return p;`
187			`}`
188
189			`/* term - create a new terminal id with external symbol number esn */`
190			`Term term(char *id, int esn) {`
191			`Term p = lookup(id), *q = &terms;`
192
193			`if (p)`
194			yyerror("redefinition of terminal `%s'\n", id);
195			`else`
196			`p = install(id);`
197			`p->kind = TERM;`
198			`p->esn = esn;`
199			`p->arity = -1;`
200			`while (q && (q)->esn < p->esn)`
201			`q = &(*q)->link;`
202			`if (q && (q)->esn == p->esn)`
203			yyerror("duplicate external symbol number `%s=%d'\n",
204			`p->name, p->esn);`
205			`p->link = *q;`
206			`*q = p;`
207			`return p;`
208			`}`
209
210			`/* tree - create & initialize a tree node with the given fields */`
211			`Tree tree(char *id, Tree left, Tree right) {`
212			`Tree t = alloc(sizeof *t);`
213			`Term p = lookup(id);`
214			`int arity = 0;`
215
216			`if (left && right)`
217			`arity = 2;`
218			`else if (left)`
219			`arity = 1;`
220			`if (p == NULL && arity > 0) {`
221			yyerror("undefined terminal `%s'\n", id);
222			`p = term(id, -1);`
223			`} else if (p == NULL && arity == 0)`
224			`p = (Term)nonterm(id);`
225			`else if (p && p->kind == NONTERM && arity > 0) {`
226			yyerror("`%s' is a nonterminal\n", id);
227			`p = term(id, -1);`
228			`}`
229			`if (p->kind == TERM && p->arity == -1)`
230			`p->arity = arity;`
231			`if (p->kind == TERM && arity != p->arity)`
232			yyerror("inconsistent arity for terminal `%s'\n", id);
233			`t->op = p;`
234			`t->nterms = p->kind == TERM;`
235			`if ((t->left = left) != NULL)`
236			`t->nterms += left->nterms;`
237			`if ((t->right = right) != NULL)`
238			`t->nterms += right->nterms;`
239			`return t;`
240			`}`
241
242			`/* rule - create & initialize a rule with the given fields */`
243			`Rule rule(char id, Tree pattern, char template, char *code) {`
244			`Rule r = alloc(sizeof r), q;`
245			`Term p = pattern->op;`
246			`char *end;`
247
248			`r->lhs = nonterm(id);`
249			`r->packed = ++r->lhs->lhscount;`
250			`for (q = &r->lhs->rules; q; q = &(q)->decode)`
251			`;`
252			`*q = r;`
253			`r->pattern = pattern;`
254			`r->ern = ++nrules;`
255			`r->template = template;`
256			`r->code = code;`
257			`r->cost = strtol(code, &end, 10);`
258			`if (*end) {`
259			`r->cost = -1;`
260			`r->code = stringf("(%s)", code);`
261			`}`
262			`if (p->kind == TERM) {`
263			`for (q = &p->rules; q; q = &(q)->next)`
264			`;`
265			`*q = r;`
266			`} else if (pattern->left == NULL && pattern->right == NULL) {`
267			`Nonterm p = pattern->op;`
268			`r->chain = p->chain;`
269			`p->chain = r;`
270			`if (r->cost == -1)`
271			yyerror("illegal nonconstant cost `%s'\n", code);
272			`}`
273			`for (q = &rules; q; q = &(q)->link)`
274			`;`
275			`r->link = *q;`
276			`*q = r;`
277			`return r;`
278			`}`
279
280			`/* print - formatted output */`
281			`static void print(char *fmt, ...) {`
282			`va_list ap;`
283
284			`va_start(ap, fmt);`
285			`for ( ; *fmt; fmt++)`
286			`if (*fmt == '%')`
287			`switch (*++fmt) {`
288			`case 'd': fprintf(outfp, "%d", va_arg(ap, int)); break;`
289			`case 's': fputs(va_arg(ap, char *), outfp); break;`
290			`case 'P': fprintf(outfp, "%s_", prefix); break;`
291			`case 'T': {`
292			`Tree t = va_arg(ap, Tree);`
293			`print("%S", t->op);`
294			`if (t->left && t->right)`
295			`print("(%T,%T)", t->left, t->right);`
296			`else if (t->left)`
297			`print("(%T)", t->left);`
298			`break;`
299			`}`
300			`case 'R': {`
301			`Rule r = va_arg(ap, Rule);`
302			`print("%S: %T", r->lhs, r->pattern);`
303			`break;`
304			`}`
305			`case 'S': {`
306			`Term t = va_arg(ap, Term);`
307			`fputs(t->name, outfp);`
308			`break;`
309			`}`
310			`case '1': case '2': case '3': case '4': case '5': {`
311			`int n = *fmt - '0';`
312			`while (n-- > 0)`
313			`putc('\t', outfp);`
314			`break;`
315			`}`
316			`default: putc(*fmt, outfp); break;`
317			`}`
318			`else`
319			`putc(*fmt, outfp);`
320			`va_end(ap);`
321			`}`
322
323			`/* reach - mark all nonterminals in tree t as reachable */`
324			`static void reach(Tree t) {`
325			`Nonterm p = t->op;`
326
327			`if (p->kind == NONTERM)`
328			`if (!p->reached)`
329			`ckreach(p);`
330			`if (t->left)`
331			`reach(t->left);`
332			`if (t->right)`
333			`reach(t->right);`
334			`}`
335
336			`/* ckreach - mark all nonterminals reachable from p */`
337			`static void ckreach(Nonterm p) {`
338			`Rule r;`
339
340			`p->reached = 1;`
341			`for (r = p->rules; r; r = r->decode)`
342			`reach(r->pattern);`
343			`}`
344
345			`/* emitcase - emit one case in function state */`
346			`static void emitcase(Term p, int ntnumber) {`
347			`Rule r;`
348
349			`print("%1case %d: /* %S */\n", p->esn, p);`
350			`switch (p->arity) {`
351			`case 0: case -1:`
352			`break;`
353			`case 1:`
354			`print("%2%Plabel(LEFT_CHILD(a));\n");`
355			`break;`
356			`case 2:`
357			`print("%2%Plabel(LEFT_CHILD(a));\n");`
358			`print("%2%Plabel(RIGHT_CHILD(a));\n");`
359			`break;`
360			`default: assert(0);`
361			`}`
362			`for (r = p->rules; r; r = r->next) {`
363			`char *indent = "\t\t\0";`
364			`switch (p->arity) {`
365			`case 0: case -1:`
366			`print("%2/* %R */\n", r);`
367			`if (r->cost == -1) {`
368			`print("%2c = %s;\n", r->code);`
369			`emitrecord("\t\t", r, "c", 0);`
370			`} else`
371			`emitrecord("\t\t", r, r->code, 0);`
372			`break;`
373			`case 1:`
374			`if (r->pattern->nterms > 1) {`
375			`print("%2if (%1/* %R */\n", r);`
376			`emittest(r->pattern->left, "LEFT_CHILD(a)", " ");`
377			`print("%2) {\n");`
378			`indent = "\t\t\t";`
379			`} else`
380			`print("%2/* %R */\n", r);`
381			`if (r->pattern->nterms == 2 && r->pattern->left`
382			`&& r->pattern->right == NULL)`
383			`emitrecalc(indent, r->pattern->op, r->pattern->left->op);`
384			`print("%sc = ", indent);`
385			`emitcost(r->pattern->left, "LEFT_CHILD(a)");`
386			`print("%s;\n", r->code);`
387			`emitrecord(indent, r, "c", 0);`
388			`if (indent[2])`
389			`print("%2}\n");`
390			`break;`
391			`case 2:`
392			`if (r->pattern->nterms > 1) {`
393			`print("%2if (%1/* %R */\n", r);`
394			`emittest(r->pattern->left, "LEFT_CHILD(a)",`
395			`r->pattern->right->nterms ? " && " : " ");`
396			`emittest(r->pattern->right, "RIGHT_CHILD(a)", " ");`
397			`print("%2) {\n");`
398			`indent = "\t\t\t";`
399			`} else`
400			`print("%2/* %R */\n", r);`
401			`print("%sc = ", indent);`
402			`emitcost(r->pattern->left, "LEFT_CHILD(a)");`
403			`emitcost(r->pattern->right, "RIGHT_CHILD(a)");`
404			`print("%s;\n", r->code);`
405			`emitrecord(indent, r, "c", 0);`
406			`if (indent[2])`
407			`print("%2}\n");`
408			`break;`
409			`default: assert(0);`
410			`}`
411			`}`
412			`print("%2break;\n");`
413			`}`
414
415			`/* emitclosure - emit the closure functions */`
416			`static void emitclosure(Nonterm nts) {`
417			`Nonterm p;`
418
419			`for (p = nts; p; p = p->link)`
420			`if (p->chain)`
421			`print("static void %Pclosure_%S(NODEPTR_TYPE, int);\n", p);`
422			`print("\n");`
423			`for (p = nts; p; p = p->link)`
424			`if (p->chain) {`
425			`Rule r;`
426			`print("static void %Pclosure_%S(NODEPTR_TYPE a, int c) {\n"`
427			`"%1struct %Pstate *p = STATE_LABEL(a);\n", p);`
428			`for (r = p->chain; r; r = r->chain)`
429			`emitrecord("\t", r, "c", r->cost);`
430			`print("}\n\n");`
431			`}`
432			`}`
433
434			`/* emitcost - emit cost computation for tree t */`
435			`static void emitcost(Tree t, char *v) {`
436			`Nonterm p = t->op;`
437
438			`if (p->kind == TERM) {`
439			`if (t->left)`
440			`emitcost(t->left, stringf("LEFT_CHILD(%s)", v));`
441			`if (t->right)`
442			`emitcost(t->right, stringf("RIGHT_CHILD(%s)", v));`
443			`} else`
444			`print("((struct %Pstate *)(%s->x.state))->cost[%P%S_NT] + ", v, p);`
445			`}`
446
447			`/* emitdefs - emit nonterminal defines and data structures */`
448			`static void emitdefs(Nonterm nts, int ntnumber) {`
449			`Nonterm p;`
450
451			`for (p = nts; p; p = p->link)`
452			`print("#define %P%S_NT %d\n", p, p->number);`
453			`print("\n");`
454			`print("static char *%Pntname[] = {\n%10,\n");`
455			`for (p = nts; p; p = p->link)`
456			`print("%1\"%S\",\n", p);`
457			`print("%10\n};\n\n");`
458			`}`
459
460			`/* emitheader - emit initial definitions */`
461			`static void emitheader(void) {`
462			`time_t timer = time(NULL);`
463
464			`print("/\ngenerated at %sby %s\n/\n", ctime(&timer), rcsid);`
465			`print("static void %Pkids(NODEPTR_TYPE, int, NODEPTR_TYPE[]);\n");`
466			`print("static void %Plabel(NODEPTR_TYPE);\n");`
467			`print("static int %Prule(void*, int);\n\n");`
468			`}`
469
470			`/* computekids - compute paths to kids in tree t */`
471			`static char computekids(Tree t, char v, char bp, int ip) {`
472			`Term p = t->op;`
473
474			`if (p->kind == NONTERM) {`
475			`sprintf(bp, "\t\tkids[%d] = %s;\n", (*ip)++, v);`
476			`bp += strlen(bp);`
477			`} else if (p->arity > 0) {`
478			`bp = computekids(t->left, stringf("LEFT_CHILD(%s)", v), bp, ip);`
479			`if (p->arity == 2)`
480			`bp = computekids(t->right, stringf("RIGHT_CHILD(%s)", v), bp, ip);`
481			`}`
482			`return bp;`
483			`}`
484
485			`/* emitkids - emit _kids */`
486			`static void emitkids(Rule rules, int nrules) {`
487			`int i;`
488			`Rule r, rc = alloc((nrules + 1 + 1)sizeof *rc);`
489			`char *str = alloc((nrules + 1 + 1)sizeof *str);`
490
491			`for (i = 0, r = rules; r; r = r->link) {`
492			`int j = 0;`
493			`char buf[1024], *bp = buf;`
494			`*computekids(r->pattern, "p", bp, &j) = 0;`
495			`for (j = 0; str[j] && strcmp(str[j], buf); j++)`
496			`;`
497			`if (str[j] == NULL)`
498			`str[j] = strcpy(alloc(strlen(buf) + 1), buf);`
499			`r->kids = rc[j];`
500			`rc[j] = r;`
501			`}`
502			`print("static void %Pkids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]) {\n"`
503			`"%1if (!p)\n%2fatal(\"%Pkids\", \"Null tree\\n\", 0);\n"`
504			`"%1if (!kids)\n%2fatal(\"%Pkids\", \"Null kids\\n\", 0);\n"`
505			`"%1switch (eruleno) {\n");`
506			`for (i = 0; (r = rc[i]) != NULL; i++) {`
507			`for ( ; r; r = r->kids)`
508			`print("%1case %d: /* %R */\n", r->ern, r);`
509			`print("%s%2break;\n", str[i]);`
510			`}`
511			`print("%1default:\n%2fatal(\"%Pkids\", \"Bad rule number %%d\\n\", eruleno);\n%1}\n}\n\n");`
512			`}`
513
514			`/* emitlabel - emit label function */`
515			`static void emitlabel(Term terms, Nonterm start, int ntnumber) {`
516			`int i;`
517			`Term p;`
518
519			`print("static void %Plabel(NODEPTR_TYPE a) {\n%1int c;\n"`
520			`"%1struct %Pstate *p;\n\n"`
521			`"%1if (!a)\n%2fatal(\"%Plabel\", \"Null tree\\n\", 0);\n");`
522			`print("%1STATE_LABEL(a) = p = allocate(sizeof *p, FUNC);\n"`
523			`"%1p->rule._stmt = 0;\n");`
524			`for (i = 1; i <= ntnumber; i++)`
525			`print("%1p->cost[%d] =\n", i);`
526			`print("%20x7fff;\n%1switch (OP_LABEL(a)) {\n");`
527			`for (p = terms; p; p = p->link)`
528			`emitcase(p, ntnumber);`
529			`print("%1default:\n"`
530			`"%2fatal(\"%Plabel\", \"Bad terminal %%d\\n\", OP_LABEL(a));\n%1}\n}\n\n");`
531			`}`
532
533			`/* computents - fill in bp with _nts vector for tree t */`
534			`static char computents(Tree t, char bp) {`
535			`if (t) {`
536			`Nonterm p = t->op;`
537			`if (p->kind == NONTERM) {`
538			`sprintf(bp, "%s_%s_NT, ", prefix, p->name);`
539			`bp += strlen(bp);`
540			`} else`
541			`bp = computents(t->right, computents(t->left, bp));`
542			`}`
543			`return bp;`
544			`}`
545
546			`/* emitnts - emit _nts ragged array */`
547			`static void emitnts(Rule rules, int nrules) {`
548			`Rule r;`
549			`int i, j, nts = alloc((nrules + 1)sizeof *nts);`
550			`char *str = alloc((nrules + 1)sizeof *str);`
551
552			`for (i = 0, r = rules; r; r = r->link) {`
553			`char buf[1024];`
554			`*computents(r->pattern, buf) = 0;`
555			`for (j = 0; str[j] && strcmp(str[j], buf); j++)`
556			`;`
557			`if (str[j] == NULL) {`
558			`print("static short %Pnts_%d[] = { %s0 };\n", j, buf);`
559			`str[j] = strcpy(alloc(strlen(buf) + 1), buf);`
560			`}`
561			`nts[i++] = j;`
562			`}`
563			`print("\nstatic short *%Pnts[] = {\n");`
564			`for (i = j = 0, r = rules; r; r = r->link) {`
565			`for ( ; j < r->ern; j++)`
566			`print("%10,%1/* %d */\n", j);`
567			`print("%1%Pnts_%d,%1/* %d */\n", nts[i++], j++);`
568			`}`
569			`print("};\n\n");`
570			`}`
571
572			`/* emitrecalc - emit code that tests for recalculation of INDIR?(VREGP) */`
573			`static void emitrecalc(char *pre, Term root, Term kid) {`
574			`if (root->kind == TERM && strncmp(root->name, "INDIR", 5) == 0`
575			`&& kid->kind == TERM && strcmp(kid->name, "VREGP" ) == 0) {`
576			`Nonterm p;`
577			`print("%sif (mayrecalc(a)) {\n", pre);`
578			`print("%s%1struct %Pstate *q = a->syms[RX]->u.t.cse->x.state;\n", pre);`
579			`for (p = nts; p; p = p->link) {`
580			`print("%s%1if (q->cost[%P%S_NT] == 0) {\n", pre, p);`
581			`print("%s%2p->cost[%P%S_NT] = 0;\n", pre, p);`
582			`print("%s%2p->rule.%P%S = q->rule.%P%S;\n", pre, p, p);`
583			`print("%s%1}\n", pre);`
584			`}`
585			`print("%s}\n", pre);`
586			`}`
587			`}`
588
589			`/* emitrecord - emit code that tests for a winning match of rule r */`
590			`static void emitrecord(char pre, Rule r, char c, int cost) {`
591			`if (Tflag)`
592			`print("%s%Ptrace(a, %d, %s + %d, p->cost[%P%S_NT]);\n",`
593			`pre, r->ern, c, cost, r->lhs);`
594			`print("%sif (", pre);`
595			`print("%s + %d < p->cost[%P%S_NT]) {\n"`
596			`"%s%1p->cost[%P%S_NT] = %s + %d;\n%s%1p->rule.%P%S = %d;\n",`
597			`c, cost, r->lhs, pre, r->lhs, c, cost, pre, r->lhs,`
598			`r->packed);`
599			`if (r->lhs->chain)`
600			`print("%s%1%Pclosure_%S(a, %s + %d);\n", pre, r->lhs, c, cost);`
601			`print("%s}\n", pre);`
602			`}`
603
604			`/* emitrule - emit decoding vectors and _rule */`
605			`static void emitrule(Nonterm nts) {`
606			`Nonterm p;`
607
608			`for (p = nts; p; p = p->link) {`
609			`Rule r;`
610			`print("static short %Pdecode_%S[] = {\n%10,\n", p);`
611			`for (r = p->rules; r; r = r->decode)`
612			`print("%1%d,\n", r->ern);`
613			`print("};\n\n");`
614			`}`
615			`print("static int %Prule(void *state, int goalnt) {\n"`
616			`"%1if (goalnt < 1 \|\| goalnt > %d)\n%2fatal(\"%Prule\", \"Bad goal nonterminal %%d\\n\", goalnt);\n"`
617			`"%1if (!state)\n%2return 0;\n%1switch (goalnt) {\n", ntnumber);`
618			`for (p = nts; p; p = p->link)`
619			`print("%1case %P%S_NT:"`
620			`"%1return %Pdecode_%S[((struct %Pstate *)state)->rule.%P%S];\n", p, p, p);`
621			`print("%1default:\n%2fatal(\"%Prule\", \"Bad goal nonterminal %%d\\n\", goalnt);\n%2return 0;\n%1}\n}\n\n");`
622			`}`
623
624			`/* emitstring - emit arrays of templates, instruction flags, and rules */`
625			`static void emitstring(Rule rules) {`
626			`Rule r;`
627
628			`print("static char *%Ptemplates[] = {\n");`
629			`print("/* 0 */%10,\n");`
630			`for (r = rules; r; r = r->link)`
631			`print("/* %d /%1\"%s\",%1/ %R */\n", r->ern, r->template, r);`
632			`print("};\n");`
633			`print("\nstatic char %Pisinstruction[] = {\n");`
634			`print("/* 0 */%10,\n");`
635			`for (r = rules; r; r = r->link) {`
636			`int len = strlen(r->template);`
637			`print("/* %d /%1%d,%1/ %s */\n", r->ern,`
638			`len >= 2 && r->template[len-2] == '\\' && r->template[len-1] == 'n',`
639			`r->template);`
640			`}`
641			`print("};\n");`
642			`print("\nstatic char *%Pstring[] = {\n");`
643			`print("/* 0 */%10,\n");`
644			`for (r = rules; r; r = r->link)`
645			`print("/* %d */%1\"%R\",\n", r->ern, r);`
646			`print("};\n\n");`
647			`}`
648
649			`/* emitstruct - emit the definition of the state structure */`
650			`static void emitstruct(Nonterm nts, int ntnumber) {`
651			`print("struct %Pstate {\n%1short cost[%d];\n%1struct {\n", ntnumber + 1);`
652			`for ( ; nts; nts = nts->link) {`
653			`int n = 1, m = nts->lhscount;`
654			`while ((m >>= 1) != 0)`
655			`n++;`
656			`print("%2unsigned int %P%S:%d;\n", nts, n);`
657			`}`
658			`print("%1} rule;\n};\n\n");`
659			`}`
660
661			`/* emittest - emit clause for testing a match */`
662			`static void emittest(Tree t, char v, char suffix) {`
663			`Term p = t->op;`
664
665			`if (p->kind == TERM) {`
666			`print("%3%s->op == %d%s/* %S */\n", v, p->esn,`
667			`t->nterms > 1 ? " && " : suffix, p);`
668			`if (t->left)`
669			`emittest(t->left, stringf("LEFT_CHILD(%s)", v),`
670			`t->right && t->right->nterms ? " && " : suffix);`
671			`if (t->right)`
672			`emittest(t->right, stringf("RIGHT_CHILD(%s)", v), suffix);`
673			`}`
674			`}`