lburg.c File Reference

#include <assert.h>
#include <ctype.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "lburg.h"

Include dependency graph for lburg.c:

Go to the source code of this file.

Data Structures
struct	block
struct	entry
Defines
#define	HASHSIZE   (sizeof table/sizeof table[0])
Functions
void *	alloc (int nbytes)
void	ckreach (Nonterm p)
char *	computekids (Tree t, char *v, char *bp, int *ip)
char *	computents (Tree t, char *bp)
void	emitcase (Term p, int ntnumber)
void	emitclosure (Nonterm nts)
void	emitcost (Tree t, char *v)
void	emitdefs (Nonterm nts, int ntnumber)
void	emitheader (void)
void	emitkids (Rule rules, int nrules)
void	emitlabel (Term terms, Nonterm start, int ntnumber)
void	emitnts (Rule rules, int nrules)
void	emitrecalc (char *pre, Term root, Term kid)
void	emitrecord (char *pre, Rule r, char *c, int cost)
void	emitrule (Nonterm nts)
void	emitstring (Rule rules)
void	emitstruct (Nonterm nts, int ntnumber)
void	emittest (Tree t, char *v, char *suffix)
unsigned	hash (char *str)
void *	install (char *name)
void *	lookup (char *name)
int	main (int argc, char *argv[])
Nonterm	nonterm (char *id)
void	print (char *fmt,...)
void	reach (Tree t)
Rule	rule (char *id, Tree pattern, char *template, char *code)
char *	stringf (char *fmt,...)
Term	term (char *id, int esn)
Tree	tree (char *id, Tree left, Tree right)
Variables
block *	memlist
int	nrules
int	ntnumber = 0
Nonterm	nts
char *	prefix = ""
char	rcsid [] = "lburg.c - faked rcsid"
Rule	rules
Nonterm	start = 0
entry *	table [211]
Term	terms
int	Tflag = 0

---

Define Documentation

#define HASHSIZE   (sizeof table/sizeof table[0])

Definition at line 137 of file lburg.c. Referenced by constant(), findlabel(), install(), lookup(), and relocate().

---

Function Documentation

void* alloc (  int  nbytes  )

Definition at line 106 of file lburg.c. References calloc(), exit(), block::link, memlist, p, and yyerror(). Referenced by append(), compose(), concat(), emitkids(), emitnts(), install(), rule(), string(), stringf(), strsave(), tree(), and yylex(). { 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; }

Here is the call graph for this function:

void ckreach (  Nonterm  p  )  [static]

Definition at line 334 of file lburg.c. References rule::decode, Nonterm, p, rule::pattern, r, reach(), nonterm::reached, Rule, and nonterm::rules. Referenced by main(), and reach(). { Rule r; p->reached = 1; for (r = p->rules; r; r = r->decode) reach(r->pattern); }

Here is the call graph for this function:

char* computekids (  Tree  t, char *  v, char *  bp, int *  ip )  [static]

Definition at line 468 of file lburg.c. References term::arity, term::kind, tree::left, tree::op, p, tree::right, sprintf(), stringf(), strlen(), t, Term, Tree, and v. Referenced by emitkids(). { 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; }

Here is the call graph for this function:

char* computents (  Tree  t, char *  bp )  [static]

Definition at line 531 of file lburg.c. References computents(), nonterm::kind, tree::left, nonterm::name, Nonterm, tree::op, p, prefix, tree::right, sprintf(), strlen(), t, and Tree. Referenced by computents(), and emitnts(). { 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; }

Here is the call graph for this function:

void emitcase (  Term  p, int  ntnumber )  [static]

Definition at line 343 of file lburg.c. References term::arity, assert, rule::code, rule::cost, emitcost(), emitrecalc(), emitrecord(), emittest(), term::esn, tree::left, rule::next, tree::nterms, tree::op, p, rule::pattern, print(), r, tree::right, Rule, term::rules, and Term. Referenced by emitlabel(). { 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"); }

Here is the call graph for this function:

void emitclosure (  Nonterm  nts  )  [static]

Definition at line 413 of file lburg.c. References rule::chain, nonterm::chain, rule::cost, emitrecord(), nonterm::link, Nonterm, p, print(), r, and Rule. Referenced by main(). { 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"); } }

Here is the call graph for this function:

void emitcost (  Tree  t, char *  v )  [static]

Definition at line 432 of file lburg.c. References nonterm::kind, tree::left, Nonterm, tree::op, p, print(), tree::right, stringf(), t, Tree, and v. Referenced by emitcase(). { 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); }

Here is the call graph for this function:

void emitdefs (  Nonterm  nts, int  ntnumber )  [static]

Definition at line 445 of file lburg.c. References nonterm::link, Nonterm, nonterm::number, p, and print(). Referenced by main(). { 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"); }

Here is the call graph for this function:

void emitheader (  void   )  [static]

Definition at line 458 of file lburg.c. References ctime(), NULL, print(), rcsid, time(), and time_t. Referenced by main(). { 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"); }

Here is the call graph for this function:

void emitkids (  Rule  rules, int  nrules )  [static]

Definition at line 483 of file lburg.c. References alloc(), computekids(), rule::ern, i, j, rule::kids, rule::link, nrules, rule::pattern, print(), r, Rule, strcmp(), strcpy(), and strlen(). Referenced by main(). { 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"); }

Here is the call graph for this function:

void emitlabel (  Term  terms, Nonterm  start, int  ntnumber )  [static]

Definition at line 512 of file lburg.c. References emitcase(), i, term::link, Nonterm, ntnumber, p, print(), and Term. Referenced by main(). { 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"); }

Here is the call graph for this function:

void emitnts (  Rule  rules, int  nrules )  [static]

Definition at line 544 of file lburg.c. References alloc(), computents(), rule::ern, i, j, rule::link, nrules, nts, rule::pattern, print(), r, Rule, strcmp(), strcpy(), and strlen(). Referenced by main(). { 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"); }

Here is the call graph for this function:

void emitrecalc (  char *  pre, Term  root, Term  kid )  [static]

Definition at line 570 of file lburg.c. References term::kind, nonterm::link, term::name, Nonterm, p, print(), root(), strcmp(), strncmp(), TERM, and Term. Referenced by emitcase(). { 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); } }

Here is the call graph for this function:

void emitrecord (  char *  pre, Rule  r, char *  c, int  cost )  [static]

Definition at line 587 of file lburg.c. References c, nonterm::chain, rule::ern, rule::lhs, rule::packed, print(), r, and Rule. Referenced by emitcase(), and emitclosure(). { 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); }

Here is the call graph for this function:

void emitrule (  Nonterm  nts  )  [static]

Definition at line 602 of file lburg.c. References rule::decode, rule::ern, nonterm::link, Nonterm, ntnumber, p, print(), r, Rule, and nonterm::rules. Referenced by main(). { 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"); }

Here is the call graph for this function:

void emitstring (  Rule  rules  )  [static]

Definition at line 622 of file lburg.c. References rule::ern, rule::link, print(), r, Rule, strlen(), and rule::template. Referenced by main(). { 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"); }

Here is the call graph for this function:

void emitstruct (  Nonterm  nts, int  ntnumber )  [static]

Definition at line 647 of file lburg.c. References nonterm::lhscount, nonterm::link, m, n, Nonterm, ntnumber, nts, and print(). Referenced by main(). { 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"); }

Here is the call graph for this function:

void emittest (  Tree  t, char *  v, char *  suffix )  [static]

Definition at line 659 of file lburg.c. References term::esn, term::kind, tree::left, tree::nterms, tree::op, p, print(), tree::right, stringf(), suffix(), t, Term, Tree, and v. Referenced by emitcase(). { 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); } }

Here is the call graph for this function:

unsigned hash (  char *  str  )  [static]

Definition at line 140 of file lburg.c. References h(). Referenced by install(), and lookup(). { unsigned h = 0; while (*str) h = (h<<1) + *str++; return h; }

Here is the call graph for this function:

void* install (  char *  name  )  [static]

Definition at line 159 of file lburg.c. References alloc(), hash(), i, symbol::name, name, and p. { 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; }

Here is the call graph for this function:

void* lookup (  char *  name  )  [static]

Definition at line 149 of file lburg.c. References hash(), entry::link, entry::name, name, p, strcmp(), and entry::sym. { struct entry *p = table[hash(name)%HASHSIZE]; for ( ; p; p = p->link) if (strcmp(name, p->sym.name) == 0) return &p->sym; return 0; }

Here is the call graph for this function:

int main (  int  argc, char *  argv[] )

Definition at line 41 of file lburg.c. References argv, c, ckreach(), emitclosure(), emitdefs(), emitheader(), emitkids(), emitlabel(), emitnts(), emitrule(), emitstring(), emitstruct(), errcnt, exit(), feof, fopen(), free(), getc, i, infp, block::link, nonterm::link, memlist, nonterm::name, Nonterm, nrules, ntnumber, nts, outfp, p, prefix, putc, q, nonterm::reached, rules, nonterm::rules, start, strcmp(), strncmp(), terms, Tflag, yyerror(), and yyparse(). { 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