Initial commit

5 files changed, 1799 insertions, 0 deletions

diff --git a/src/tools/lcc/lburg/gram.c b/src/tools/lcc/lburg/gram.c
new file mode 100644
index 0000000..a1cc890
--- /dev/null
+++ b/src/tools/lcc/lburg/gram.c
@@ -0,0 +1,682 @@
+#if defined(__STDC__) || defined(__cplusplus)
+#define YYCONST const
+#define YYPARAMS(x) x
+#define YYDEFUN(name, arglist, args) name(args)
+#define YYAND ,
+#define YYPTR void *
+#else
+#define YYCONST
+#define YYPARAMS(x) ()
+#define YYDEFUN(name, arglist, args) name arglist args;
+#define YYAND ;
+#define YYPTR char *
+#endif
+#ifndef lint
+YYCONST static char yysccsid[] = "@(#)yaccpar	1.8 (Berkeley +Cygnus.28) 01/20/91";
+#endif
+#define YYBYACC 1
+#ifndef YYDONT_INCLUDE_STDIO
+#include <stdio.h>
+#endif
+//#ifdef __cplusplus TA <tim@ngus.net> stdlib.h applies to C too
+#include <stdlib.h> /* for malloc/realloc/free */
+//#endif
+#line 2 "lburg/gram.y"
+#include <stdio.h>
+#include "lburg.h"
+/*lint -e616 -e527 -e652 -esym(552,yynerrs) -esym(563,yynewstate,yyerrlab) */
+static int yylineno = 0;
+#line 8 "lburg/gram.y"
+typedef union {
+	int n;
+	char *string;
+	Tree tree;
+} YYSTYPE;
+#line 37 "y.tab.c"
+#define TERMINAL 257
+#define START 258
+#define PPERCENT 259
+#define ID 260
+#define TEMPLATE 261
+#define CODE 262
+#define INT 263
+#define YYERRCODE 256
+static YYCONST short yylhs[] = {                                        -1,
+    0,    0,    4,    4,    6,    6,    6,    6,    7,    7,
+    5,    5,    5,    5,    1,    3,    3,    3,    2,
+};
+static YYCONST short yylen[] = {                                         2,
+    3,    1,    0,    2,    3,    3,    1,    2,    0,    4,
+    0,    7,    2,    3,    1,    1,    4,    6,    1,
+};
+static YYCONST short yydefred[] = {                                      3,
+    0,    0,    0,    9,    0,   11,    7,    4,    8,    0,
+   15,    0,    0,    0,    5,    6,    0,   13,    0,    0,
+   14,    0,   10,    0,    0,    0,    0,    0,   19,    0,
+   17,    0,   12,    0,   18,
+};
+static YYCONST short yydgoto[] = {                                       1,
+   12,   30,   25,    2,   13,    8,   10,
+};
+static YYCONST short yysindex[] = {                                      0,
+    0,   -4,   -2,    0, -250,    0,    0,    0,    0,   -9,
+    0,    1,  -10,  -49,    0,    0,    3,    0,  -44, -248,
+    0, -244,    0,  -22, -242, -244, -245,  -37,    0,   10,
+    0, -244,    0,  -20,    0,
+};
+static YYCONST short yyrindex[] = {                                      0,
+    0,   22,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,   23,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,  -39,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,
+};
+static YYCONST short yygindex[] = {                                      0,
+   11,    0,  -23,    0,    0,    0,    0,
+};
+#define YYTABLESIZE 255
+static YYCONST short yytable[] = {                                      18,
+   15,   16,   28,   31,   16,    7,   32,    9,   34,   11,
+   16,   20,   21,   22,   23,   24,   29,   26,   27,   33,
+   35,    2,    1,   19,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,   16,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
+    0,    0,    0,    0,    0,   17,    0,    0,    0,   11,
+   14,    3,    4,    5,    6,
+};
+static YYCONST short yycheck[] = {                                      10,
+   10,   41,   26,   41,   44,   10,   44,   10,   32,  260,
+   10,   61,   10,   58,  263,  260,  262,   40,  261,   10,
+   41,    0,    0,   13,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,  261,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,
+   -1,   -1,   -1,   -1,   -1,  256,   -1,   -1,   -1,  260,
+  260,  256,  257,  258,  259,
+};
+#define YYFINAL 1
+#ifndef YYDEBUG
+#define YYDEBUG 0
+#endif
+#define YYMAXTOKEN 263
+#if YYDEBUG
+static YYCONST char *YYCONST yyname[] = {
+"end-of-file",0,0,0,0,0,0,0,0,0,"'\\n'",0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+0,0,0,0,0,0,0,0,0,"'('","')'",0,0,"','",0,0,0,0,0,0,0,0,0,0,0,0,0,"':'",0,0,
+"'='",0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+"TERMINAL","START","PPERCENT","ID","TEMPLATE","CODE","INT",
+};
+static YYCONST char *YYCONST yyrule[] = {
+"$accept : spec",
+"spec : decls PPERCENT rules",
+"spec : decls",
+"decls :",
+"decls : decls decl",
+"decl : TERMINAL blist '\\n'",
+"decl : START nonterm '\\n'",
+"decl : '\\n'",
+"decl : error '\\n'",
+"blist :",
+"blist : blist ID '=' INT",
+"rules :",
+"rules : rules nonterm ':' tree TEMPLATE cost '\\n'",
+"rules : rules '\\n'",
+"rules : rules error '\\n'",
+"nonterm : ID",
+"tree : ID",
+"tree : ID '(' tree ')'",
+"tree : ID '(' tree ',' tree ')'",
+"cost : CODE",
+};
+#endif
+#define YYLEX yylex()
+#define YYEMPTY -1
+#define yyclearin (yychar=(YYEMPTY))
+#define yyerrok (yyerrflag=0)
+#ifndef YYINITDEPTH
+#define YYINITDEPTH 200
+#endif
+#ifdef YYSTACKSIZE
+#ifndef YYMAXDEPTH
+#define YYMAXDEPTH YYSTACKSIZE
+#endif
+#else
+#ifdef YYMAXDEPTH
+#define YYSTACKSIZE YYMAXDEPTH
+#else
+#define YYSTACKSIZE 500
+#define YYMAXDEPTH 500
+#endif
+#endif
+#ifndef YYMAXSTACKSIZE
+#define YYMAXSTACKSIZE 10000
+#endif
+int yydebug;
+int yynerrs;
+int yyerrflag;
+int yychar;
+YYSTYPE yyval;
+YYSTYPE yylval;
+static short *yyss;
+static YYSTYPE *yyvs;
+static int yystacksize;
+#define yyfree(x) free(x)
+extern int yylex();
+
+static YYPTR
+YYDEFUN (yymalloc, (bytes), unsigned bytes)
+{
+    YYPTR ptr = (YYPTR) malloc (bytes);
+    if (ptr != 0) return (ptr);
+    yyerror ("yyparse: memory exhausted");
+    return (0);
+}
+
+static YYPTR
+YYDEFUN (yyrealloc, (old, bytes), YYPTR old YYAND unsigned bytes)
+{
+    YYPTR ptr = (YYPTR) realloc (old, bytes);
+    if (ptr != 0) return (ptr);
+    yyerror ("yyparse: memory exhausted");
+    return (0);
+}
+
+static int
+#ifdef __GNUC__
+inline
+#endif
+yygrow ()
+{
+#if YYDEBUG
+    int old_stacksize = yystacksize;
+#endif
+    short *new_yyss;
+    YYSTYPE *new_yyvs;
+
+    if (yystacksize == YYMAXSTACKSIZE)
+        return (1);
+    yystacksize += (yystacksize + 1 ) / 2;
+    if (yystacksize > YYMAXSTACKSIZE)
+        yystacksize = YYMAXSTACKSIZE;
+#if YYDEBUG
+    if (yydebug)
+        printf("yydebug: growing stack size from %d to %d\n",
+               old_stacksize, yystacksize);
+#endif
+    new_yyss = (short *) yyrealloc ((char *)yyss, yystacksize * sizeof (short));
+    if (new_yyss == 0)
+        return (1);
+    new_yyvs = (YYSTYPE *) yyrealloc ((char *)yyvs, yystacksize * sizeof (YYSTYPE));
+    if (new_yyvs == 0)
+    {
+        yyfree (new_yyss);
+        return (1);
+    }
+    yyss = new_yyss;
+    yyvs = new_yyvs;
+    return (0);
+}
+#line 60 "lburg/gram.y"
+#include <assert.h>
+#include <stdarg.h>
+#include <ctype.h>
+#include <string.h>
+#include <limits.h>
+
+int errcnt = 0;
+FILE *infp = NULL;
+FILE *outfp = NULL;
+static char buf[BUFSIZ], *bp = buf;
+static int ppercent = 0;
+static int code = 0;
+
+static int get(void) {
+	if (*bp == 0) {
+		bp = buf;
+		*bp = 0;
+		if (fgets(buf, sizeof buf, infp) == NULL)
+			return EOF;
+		yylineno++;
+		while (buf[0] == '%' && buf[1] == '{' && buf[2] == '\n') {
+			for (;;) {
+				if (fgets(buf, sizeof buf, infp) == NULL) {
+					yywarn("unterminated %{...%}\n");
+					return EOF;
+				}
+				yylineno++;
+				if (strcmp(buf, "%}\n") == 0)
+					break;
+				fputs(buf, outfp);
+			}
+			if (fgets(buf, sizeof buf, infp) == NULL)
+				return EOF;
+			yylineno++;
+		}
+	}
+	return *bp++;
+}
+
+void yyerror(char *fmt, ...) {
+	va_list ap;
+
+	va_start(ap, fmt);
+	if (yylineno > 0)
+		fprintf(stderr, "line %d: ", yylineno);
+	vfprintf(stderr, fmt, ap);
+	if (fmt[strlen(fmt)-1] != '\n')
+		 fprintf(stderr, "\n");
+	errcnt++;
+	va_end(ap);
+}
+
+int yylex(void) {
+	int c;
+
+	if (code) {
+		char *p;
+		bp += strspn(bp, " \t\f");
+		p = strchr(bp, '\n');
+		if (p == NULL)
+			p = strchr(bp, '\n');
+		while (p > bp && isspace(p[-1]))
+			p--;
+		yylval.string = alloc(p - bp + 1);
+		strncpy(yylval.string, bp, p - bp);
+		yylval.string[p - bp] = 0;
+		bp = p;
+		code--;
+		return CODE;
+	}
+	while ((c = get()) != EOF) {
+		switch (c) {
+		case ' ': case '\f': case '\t':
+			continue;
+		case '\n':
+		case '(': case ')': case ',':
+		case ':': case '=':
+			return c;
+		}
+		if (c == '%' && *bp == '%') {
+			bp++;
+			return ppercent++ ? 0 : PPERCENT;
+		} else if (c == '%' && strncmp(bp, "term", 4) == 0
+		&& isspace(bp[4])) {
+			bp += 4;
+			return TERMINAL;
+		} else if (c == '%' && strncmp(bp, "start", 5) == 0
+		&& isspace(bp[5])) {
+			bp += 5;
+			return START;
+		} else if (c == '"') {
+			char *p = strchr(bp, '"');
+			if (p == NULL) {
+				yyerror("missing \" in assembler template\n");
+				p = strchr(bp, '\n');
+				if (p == NULL)
+					p = strchr(bp, '\0');
+			}
+			assert(p);
+			yylval.string = alloc(p - bp + 1);
+			strncpy(yylval.string, bp, p - bp);
+			yylval.string[p - bp] = 0;
+			bp = *p == '"' ? p + 1 : p;
+			code++;
+			return TEMPLATE;
+		} else if (isdigit(c)) {
+			int n = 0;
+			do {
+				int d = c - '0';
+				if (n > (INT_MAX - d)/10)
+					yyerror("integer greater than %d\n", INT_MAX);
+				else
+					n = 10*n + d;
+				c = get();
+			} while (c != EOF && isdigit(c));
+			bp--;
+			yylval.n = n;
+			return INT;
+		} else if (isalpha(c)) {
+			char *p = bp - 1;
+			while (isalpha(*bp) || isdigit(*bp) || *bp == '_')
+				bp++;
+			yylval.string = alloc(bp - p + 1);
+			strncpy(yylval.string, p, bp - p);
+			yylval.string[bp - p] = 0;
+			return ID;
+		} else if (isprint(c))
+			yyerror("invalid character `%c'\n", c);
+		else
+			yyerror("invalid character `\\%03o'\n", (unsigned char)c);
+	}
+	return 0;
+}
+
+void yywarn(char *fmt, ...) {
+	va_list ap;
+
+	va_start(ap, fmt);
+	if (yylineno > 0)
+		fprintf(stderr, "line %d: ", yylineno);
+	fprintf(stderr, "warning: ");
+	vfprintf(stderr, fmt, ap);
+}
+#line 403 "y.tab.c"
+#define YYABORT goto yyabort
+#define YYACCEPT goto yyaccept
+#define YYERROR goto yyerrlab
+
+#if YYDEBUG
+#ifdef __cplusplus
+extern "C" char *getenv();
+#else
+extern char *getenv();
+#endif
+#endif
+
+int
+yyparse()
+{
+    register int yym, yyn, yystate;
+    register YYSTYPE *yyvsp;
+    register short *yyssp;
+    short *yysse;
+#if YYDEBUG
+    register YYCONST char *yys;
+
+    if (yys = getenv("YYDEBUG"))
+    {
+        yyn = *yys;
+        if (yyn >= '0' && yyn <= '9')
+            yydebug = yyn - '0';
+    }
+#endif
+
+    yynerrs = 0;
+    yyerrflag = 0;
+    yychar = (-1);
+
+    if (yyss == 0)
+    {
+        yyss = (short *) yymalloc (YYSTACKSIZE * sizeof (short));
+        if (yyss == 0)
+          goto yyabort;
+        yyvs = (YYSTYPE *) yymalloc (YYSTACKSIZE * sizeof (YYSTYPE));
+        if (yyvs == 0)
+        {
+            yyfree (yyss);
+            goto yyabort;
+        }
+        yystacksize = YYSTACKSIZE;
+    }
+    yysse = yyss + yystacksize - 1;
+    yyssp = yyss;
+    yyvsp = yyvs;
+    *yyssp = yystate = 0;
+    goto yyloop;
+
+yypush_lex:
+    yyval = yylval;
+    yystate = yytable[yyn];
+yypush:
+    if (yyssp >= yysse)
+    {
+        int depth = yyssp - yyss;
+        if (yygrow() != 0)
+             goto yyoverflow;
+        yysse = yyss + yystacksize -1;
+        yyssp = depth + yyss;
+        yyvsp = depth + yyvs;
+    }
+    *++yyssp = yystate;
+    *++yyvsp = yyval;
+
+yyloop:
+    if ((yyn = yydefred[yystate])) goto yyreduce;
+    yyn = yysindex[yystate];
+    if (yychar < 0)
+    {
+        if ((yychar = yylex()) < 0) yychar = 0;
+#if YYDEBUG
+        if (yydebug)
+        {
+            yys = 0;
+            if (yychar <= YYMAXTOKEN) yys = yyname[yychar];
+            if (!yys) yys = "illegal-symbol";
+            printf("yydebug: state %d, reading %d (%s)\n", yystate,
+                    yychar, yys);
+        }
+#endif
+    }
+    if (yyn != 0
+        && ((yyn += yychar), ((unsigned)yyn <= (unsigned)YYTABLESIZE))
+        && yycheck[yyn] == yychar)
+    {
+#if YYDEBUG
+        if (yydebug)
+            printf("yydebug: state %d, shifting to state %d\n",
+                    yystate, yytable[yyn]);
+#endif
+        if (yyerrflag > 0)  --yyerrflag;
+        yychar = (-1);
+        goto yypush_lex;
+    }
+    yyn = yyrindex[yystate];
+    if (yyn != 0
+        && ((yyn += yychar), ((unsigned)yyn <= (unsigned)YYTABLESIZE))
+        && yycheck[yyn] == yychar)
+    {
+        yyn = yytable[yyn];
+        goto yyreduce;
+    }
+    if (yyerrflag) goto yyinrecovery;
+#ifdef lint
+    goto yynewerror;
+yynewerror:
+#endif
+    yyerror("syntax error");
+#ifdef lint
+    goto yyerrlab;
+yyerrlab:
+#endif
+    ++yynerrs;
+yyinrecovery:
+    if (yyerrflag < 3)
+    {
+        yyerrflag = 3;
+        for (;;)
+        {
+            yyn = yysindex[*yyssp];
+            if (yyn != 0
+                && ((yyn += YYERRCODE), ((unsigned)yyn <= (unsigned)YYTABLESIZE))
+                && yycheck[yyn] == YYERRCODE)
+            {
+#if YYDEBUG
+                if (yydebug)
+                    printf("yydebug: state %d, error recovery shifting\
+ to state %d\n", *yyssp, yytable[yyn]);
+#endif
+                goto yypush_lex;
+            }
+            else
+            {
+#if YYDEBUG
+                if (yydebug)
+                    printf("yydebug: error recovery discarding state %d\n",
+                            *yyssp);
+#endif
+                if (yyssp <= yyss) goto yyabort;
+                --yyssp;
+                --yyvsp;
+            }
+        }
+    }
+    else
+    {
+        if (yychar == 0) goto yyabort;
+#if YYDEBUG
+        if (yydebug)
+        {
+            yys = 0;
+            if (yychar <= YYMAXTOKEN) yys = yyname[yychar];
+            if (!yys) yys = "illegal-symbol";
+            printf("yydebug: state %d, error recovery discards token %d (%s)\n",
+                    yystate, yychar, yys);
+        }
+#endif
+        yychar = (-1);
+        goto yyloop;
+    }
+yyreduce:
+#if YYDEBUG
+    if (yydebug)
+        printf("yydebug: state %d, reducing by rule %d (%s)\n",
+                yystate, yyn, yyrule[yyn]);
+#endif
+    yym = yylen[yyn];
+    yyval = yyvsp[1-yym];
+    switch (yyn)
+    {
+case 1:
+#line 22 "lburg/gram.y"
+{ yylineno = 0; }
+break;
+case 2:
+#line 23 "lburg/gram.y"
+{ yylineno = 0; }
+break;
+case 6:
+#line 31 "lburg/gram.y"
+{
+		if (nonterm(yyvsp[-1].string)->number != 1)
+			yyerror("redeclaration of the start symbol\n");
+		}
+break;
+case 8:
+#line 36 "lburg/gram.y"
+{ yyerrok; }
+break;
+case 10:
+#line 40 "lburg/gram.y"
+{ term(yyvsp[-2].string, yyvsp[0].n); }
+break;
+case 12:
+#line 44 "lburg/gram.y"
+{ rule(yyvsp[-5].string, yyvsp[-3].tree, yyvsp[-2].string, yyvsp[-1].string); }
+break;
+case 14:
+#line 46 "lburg/gram.y"
+{ yyerrok; }
+break;
+case 15:
+#line 49 "lburg/gram.y"
+{ nonterm(yyval.string = yyvsp[0].string); }
+break;
+case 16:
+#line 52 "lburg/gram.y"
+{ yyval.tree = tree(yyvsp[0].string,  0,  0); }
+break;
+case 17:
+#line 53 "lburg/gram.y"
+{ yyval.tree = tree(yyvsp[-3].string, yyvsp[-1].tree,  0); }
+break;
+case 18:
+#line 54 "lburg/gram.y"
+{ yyval.tree = tree(yyvsp[-5].string, yyvsp[-3].tree, yyvsp[-1].tree); }
+break;
+case 19:
+#line 57 "lburg/gram.y"
+{ if (*yyvsp[0].string == 0) yyval.string = "0"; }
+break;
+#line 630 "y.tab.c"
+    }
+    yyssp -= yym;
+    yyvsp -= yym;
+    yym = yylhs[yyn];
+    yystate = *yyssp;
+    if (yystate == 0 && yym == 0)
+    {
+#if YYDEBUG
+        if (yydebug)
+            printf("yydebug: after reduction, shifting from state 0 to\
+ state %d\n", YYFINAL);
+#endif
+        yystate = YYFINAL;
+        *++yyssp = YYFINAL;
+        *++yyvsp = yyval;
+        if (yychar < 0)
+        {
+            if ((yychar = yylex()) < 0) yychar = 0;
+#if YYDEBUG
+            if (yydebug)
+            {
+                yys = 0;
+                if (yychar <= YYMAXTOKEN) yys = yyname[yychar];
+                if (!yys) yys = "illegal-symbol";
+                printf("yydebug: state %d, reading %d (%s)\n",
+                        YYFINAL, yychar, yys);
+            }
+#endif
+        }
+        if (yychar == 0) goto yyaccept;
+        goto yyloop;
+    }
+    yyn = yygindex[yym];
+	 if (yyn != 0
+        && ((yyn += yystate), ((unsigned)yyn <= (unsigned)YYTABLESIZE))
+        && yycheck[yyn] == yystate)
+        yystate = yytable[yyn];
+    else
+        yystate = yydgoto[yym];
+#if YYDEBUG
+    if (yydebug)
+        printf("yydebug: after reduction, shifting from state %d \
+to state %d\n", *yyssp, yystate);
+#endif
+    goto yypush;
+yyoverflow:
+    yyerror("yacc stack overflow");
+yyabort:
+    return (1);
+yyaccept:
+    return (0);
+}
diff --git a/src/tools/lcc/lburg/gram.y b/src/tools/lcc/lburg/gram.y
new file mode 100644
index 0000000..1ecd8a9
--- /dev/null
+++ b/src/tools/lcc/lburg/gram.y
@@ -0,0 +1,202 @@
+%{
+#include <stdio.h>
+#include "lburg.h"
+static char rcsid[] = "$Id: gram.y 145 2001-10-17 21:53:10Z timo $";
+/*lint -e616 -e527 -e652 -esym(552,yynerrs) -esym(563,yynewstate,yyerrlab) */
+static int yylineno = 0;
+%}
+%union {
+	int n;
+	char *string;
+	Tree tree;
+}
+%term TERMINAL
+%term START
+%term PPERCENT
+
+%token  <string>        ID TEMPLATE CODE
+%token  <n>             INT
+%type	<string>	nonterm cost
+%type   <tree>          tree
+%%
+spec	: decls PPERCENT rules		{ yylineno = 0; }
+	| decls				{ yylineno = 0; }
+	;
+
+decls	: /* lambda */
+	| decls decl
+	;
+
+decl	: TERMINAL  blist '\n'
+	| START nonterm '\n'		{
+		if (nonterm($2)->number != 1)
+			yyerror("redeclaration of the start symbol\n");
+		}
+	| '\n'
+	| error '\n'			{ yyerrok; }
+	;
+
+blist	: /* lambda */
+	| blist ID '=' INT      	{ term($2, $4); }
+	;
+
+rules	: /* lambda */
+	| rules nonterm ':' tree TEMPLATE cost '\n'	{ rule($2, $4, $5, $6); }
+	| rules '\n'
+	| rules error '\n'		{ yyerrok; }
+	;
+
+nonterm	: ID				{ nonterm($$ = $1); }
+	;
+
+tree	: ID                            { $$ = tree($1,  0,  0); }
+	| ID '(' tree ')'               { $$ = tree($1, $3,  0); }
+	| ID '(' tree ',' tree ')'      { $$ = tree($1, $3, $5); }
+	;
+
+cost	: CODE				{ if (*$1 == 0) $$ = "0"; }
+	;
+%%
+#include <assert.h>
+#include <stdarg.h>
+#include <ctype.h>
+#include <string.h>
+#include <limits.h>
+
+int errcnt = 0;
+FILE *infp = NULL;
+FILE *outfp = NULL;
+static char buf[BUFSIZ], *bp = buf;
+static int ppercent = 0;
+static int code = 0;
+
+static int get(void) {
+	if (*bp == 0) {
+		bp = buf;
+		*bp = 0;
+		if (fgets(buf, sizeof buf, infp) == NULL)
+			return EOF;
+		yylineno++;
+		while (buf[0] == '%' && buf[1] == '{' && buf[2] == '\n') {
+			for (;;) {
+				if (fgets(buf, sizeof buf, infp) == NULL) {
+					yywarn("unterminated %{...%}\n");
+					return EOF;
+				}
+				yylineno++;
+				if (strcmp(buf, "%}\n") == 0)
+					break;
+				fputs(buf, outfp);
+			}
+			if (fgets(buf, sizeof buf, infp) == NULL)
+				return EOF;
+			yylineno++;
+		}
+	}
+	return *bp++;
+}
+
+void yyerror(char *fmt, ...) {
+	va_list ap;
+
+	va_start(ap, fmt);
+	if (yylineno > 0)
+		fprintf(stderr, "line %d: ", yylineno);
+	vfprintf(stderr, fmt, ap);
+	if (fmt[strlen(fmt)-1] != '\n')
+		 fprintf(stderr, "\n");
+	errcnt++;
+	va_end(ap);
+}
+
+int yylex(void) {
+	int c;
+
+	if (code) {
+		char *p;
+		bp += strspn(bp, " \t\f");
+		p = strchr(bp, '\n');
+		if (p == NULL)
+			p = strchr(bp, '\n');
+		while (p > bp && isspace(p[-1]))
+			p--;
+		yylval.string = alloc(p - bp + 1);
+		strncpy(yylval.string, bp, p - bp);
+		yylval.string[p - bp] = 0;
+		bp = p;
+		code--;
+		return CODE;
+	}
+	while ((c = get()) != EOF) {
+		switch (c) {
+		case ' ': case '\f': case '\t':
+			continue;
+		case '\n':
+		case '(': case ')': case ',':
+		case ':': case '=':
+			return c;
+		}
+		if (c == '%' && *bp == '%') {
+			bp++;
+			return ppercent++ ? 0 : PPERCENT;
+		} else if (c == '%' && strncmp(bp, "term", 4) == 0
+		&& isspace(bp[4])) {
+			bp += 4;
+			return TERMINAL;
+		} else if (c == '%' && strncmp(bp, "start", 5) == 0
+		&& isspace(bp[5])) {
+			bp += 5;
+			return START;
+		} else if (c == '"') {
+			char *p = strchr(bp, '"');
+			if (p == NULL) {
+				yyerror("missing \" in assembler template\n");
+				p = strchr(bp, '\n');
+				if (p == NULL)
+					p = strchr(bp, '\0');
+			}
+			assert(p);
+			yylval.string = alloc(p - bp + 1);
+			strncpy(yylval.string, bp, p - bp);
+			yylval.string[p - bp] = 0;
+			bp = *p == '"' ? p + 1 : p;
+			code++;
+			return TEMPLATE;
+		} else if (isdigit(c)) {
+			int n = 0;
+			do {
+				int d = c - '0';
+				if (n > (INT_MAX - d)/10)
+					yyerror("integer greater than %d\n", INT_MAX);
+				else
+					n = 10*n + d;
+				c = get();
+			} while (c != EOF && isdigit(c));
+			bp--;
+			yylval.n = n;
+			return INT;
+		} else if (isalpha(c)) {
+			char *p = bp - 1;
+			while (isalpha(*bp) || isdigit(*bp) || *bp == '_')
+				bp++;
+			yylval.string = alloc(bp - p + 1);
+			strncpy(yylval.string, p, bp - p);
+			yylval.string[bp - p] = 0;
+			return ID;
+		} else if (isprint(c))
+			yyerror("invalid character `%c'\n", c);
+		else
+			yyerror("invalid character `\\%03o'\n", (unsigned char)c);
+	}
+	return 0;
+}
+
+void yywarn(char *fmt, ...) {
+	va_list ap;
+
+	va_start(ap, fmt);
+	if (yylineno > 0)
+		fprintf(stderr, "line %d: ", yylineno);
+	fprintf(stderr, "warning: ");
+	vfprintf(stderr, fmt, ap);
+}
diff --git a/src/tools/lcc/lburg/lburg.1 b/src/tools/lcc/lburg/lburg.1
new file mode 100644
index 0000000..8cf7250
--- /dev/null
+++ b/src/tools/lcc/lburg/lburg.1
@@ -0,0 +1,179 @@
+.TH LBURG 1 "local \- 11/30/94"
+.\" $Id: lburg.1 145 2001-10-17 21:53:10Z timo $
+.SH NAME
+lburg \- lcc's code-generator generator
+.SH SYNOPSIS
+.B lburg
+[
+.I option
+]...
+[ [
+.I input
+]
+.I output
+]
+.br
+.SH DESCRIPTION
+.PP
+.I lburg
+reads an lcc-style BURG specification from
+.I input
+and writes a pattern-matching code generator to
+.IR output .
+If
+.I input
+is `\-' or is omitted,
+.I lburg
+reads the standard input;
+If
+.I output
+is `\-' or is omitted,
+.I lburg
+writes to the standard output.
+.PP
+.I lburg
+accepts specifications that conform to the following EBNF grammar.
+Terminals are enclosed in single quotes or are
+given in uppercase, all other symbols are nonterminals or English phrases,
+{X} denotes zero or more instances of X, and [X] denotes an optional X.
+.PP
+.nf
+.RS
+.ft CW
+spec:     `%{' configuration `%}' { dcl } `%%' { rule }
+               [ `%%' C code ]
+
+dcl:      `%start' nonterm
+          `%term' { ID `=' INT }
+
+rule:     nonterm `:' tree template [ C expression ]
+
+tree:     term `(' tree `,' tree `)'
+          term `(' tree `)'
+          term
+          nonterm
+
+nonterm:  ID
+
+template: `"' { any character except double quote } `"'
+.RE
+.fi
+.PP
+Specifications are structurally similar to
+.IR yacc 's.
+Text between
+`\f(CW%{\fP'
+and
+`\f(CW%}\fP'
+is called the configuration section; there may be several such segments.
+All are concatenated and copied verbatim into the head of the output.
+Text after the second
+`\f(CW%%\fP',
+if any, is also copied verbatim into the output, at the end.
+.PP
+Specifications consist of declarations, a
+`\f(CW%%\fP'
+separator, and rules.
+Input is line-oriented; each declaration and rule must appear on a separate line,
+and declarations must begin in column 1.
+Declarations declare terminals \(em the operators in subject
+trees \(em and associate a unique, positive external symbol
+number with each one.
+Nonterminals are declared by their presence
+on the left side of rules.  The
+\f(CW%start\fP
+declaration optionally declares a nonterminal as the start symbol.
+In the grammar above,
+\f(CWterm\fP
+and
+\f(CWnonterm\fP
+denote identifiers that are terminals and nonterminals.
+.PP
+Rules define tree patterns in a fully parenthesized prefix
+form. Every nonterminal denotes a tree.
+Each operator has a fixed
+arity, which is inferred from the rules in which it is used.
+A chain rule is a rule whose pattern is another nonterminal.
+If no start symbol is declared, the nonterminal defined by the first rule is used.
+.PP
+Each rule ends with an expression that computes the cost of matching
+that rule; omitted costs
+default to zero. Costs of chain rules must be constants.
+.PP
+The configuration section configures the output
+for the trees being parsed and the client's environment.
+As shown, this section must define
+\f(CWNODEPTR_TYPE\fP
+to be a visible typedef symbol for a pointer to a
+node in the subject tree.
+The labeller invokes
+\f(CWOP_LABEL(p)\fP,
+\f(CWLEFT\_CHILD(p)\fP, and
+\f(CWRIGHT\_CHILD(p)\fP
+to read the operator and children from the node pointed to by \f(CWp\fP.
+If the configuration section defines these operations as macros, they are implemented in-line;
+otherwise, they must be implemented as functions.
+.PP
+The matcher
+computes and stores a single integral state in each node of the subject tree.
+The configuration section must define a macro
+\f(CWSTATE_LABEL(p)\fP
+to access the state field of the node pointed to
+by \f(CWp\fP. It must be large enough to hold a pointer, and
+a macro is required because it is used as an lvalue.
+.PP
+.SH OPTIONS
+.TP
+.BI \-p \ prefix
+.br
+.ns
+.TP
+.BI \-p prefix
+Use
+.I prefix
+as the disambiquating prefix for visible names and fields.
+The default is `\f(CW_\fP'.
+.TP
+.B \-T
+Arrange for
+.sp
+.nf
+.ft CW
+    void _trace(NODEPTR_TYPE p, int eruleno,
+                    int cost, int bestcost);
+.sp
+.fi
+.ft R
+to be called at each successful match.
+\f(CWp\fP
+identifies the node and
+\f(CWeruleno\fP
+identifies the matching rule; the rules are numbered
+beginning at 1 in the order they appear in the input.
+\f(CWcost\fP
+is the cost of the match and
+\f(CWbestcost\fP
+is the cost of the best previous match. The current match
+wins only if
+\f(CWcost\fP
+is less than \f(CWbestcost\fP.
+32767 represents the infinite cost of no previous match.
+\f(CW_trace\fP must be declared in the configuration section.
+.SH "SEE ALSO"
+.IR lcc (1)
+.PP
+C. W. Fraser and D. R. Hanson,
+.IR A Retargetable C Compiler: Design and Implementation ,
+Benjamin/Cummings, Redwood City, CA, 1995,
+ISBN 0-8053-1670-1. Chapter 14.
+.PP
+C. W. Fraser, D. R. Hanson and T. A. Proebsting,
+`Engineering a simple, efficient code generator generator,'
+.I
+ACM Letters on Programming Languages and Systems
+.BR 1 ,
+3 (Sep. 1992), 213-226.
+.br
+.SH BUGS
+Mail bug reports along with the shortest input
+that exposes them to drh@cs.princeton.edu.
diff --git a/src/tools/lcc/lburg/lburg.c b/src/tools/lcc/lburg/lburg.c
new file mode 100644
index 0000000..c43c96a
--- /dev/null
+++ b/src/tools/lcc/lburg/lburg.c
@@ -0,0 +1,671 @@
+#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[] = "lburg.c - faked rcsid";
+
+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': fputs(va_arg(ap, Term)->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);
+	}
+}
diff --git a/src/tools/lcc/lburg/lburg.h b/src/tools/lcc/lburg/lburg.h
new file mode 100644
index 0000000..b67e802
--- /dev/null
+++ b/src/tools/lcc/lburg/lburg.h
@@ -0,0 +1,65 @@
+#ifndef BURG_INCLUDED
+#define BURG_INCLUDED
+
+/* iburg.c: */
+extern void *alloc(int nbytes);
+
+typedef enum { TERM=1, NONTERM } Kind;
+typedef struct rule *Rule;
+typedef struct term *Term;
+struct term {		/* terminals: */
+	char *name;		/* terminal name */
+	Kind kind;		/* TERM */
+	int esn;		/* external symbol number */
+	int arity;		/* operator arity */
+	Term link;		/* next terminal in esn order */
+	Rule rules;		/* rules whose pattern starts with term */
+};
+
+typedef struct nonterm *Nonterm;
+struct nonterm {	/* nonterminals: */
+	char *name;		/* nonterminal name */
+	Kind kind;		/* NONTERM */
+	int number;		/* identifying number */
+	int lhscount;		/* # times nt appears in a rule lhs */
+	int reached;		/* 1 iff reached from start nonterminal */
+	Rule rules;		/* rules w/nonterminal on lhs */
+	Rule chain;		/* chain rules w/nonterminal on rhs */
+	Nonterm link;		/* next terminal in number order */
+};
+extern Nonterm nonterm(char *id);
+extern Term term(char *id, int esn);
+
+typedef struct tree *Tree;
+struct tree {		/* tree patterns: */
+	void *op;		/* a terminal or nonterminal */
+	Tree left, right;	/* operands */
+	int nterms;		/* number of terminal nodes in this tree */
+};
+extern Tree tree(char *op, Tree left, Tree right);
+
+struct rule {		/* rules: */
+	Nonterm lhs;		/* lefthand side nonterminal */
+	Tree pattern;		/* rule pattern */
+	int ern;		/* external rule number */
+	int packed;		/* packed external rule number */
+	int cost;		/* cost, if a constant */
+	char *code;		/* cost, if an expression */
+	char *template;		/* assembler template */
+	Rule link;		/* next rule in ern order */
+	Rule next;		/* next rule with same pattern root */
+	Rule chain;		/* next chain rule with same rhs */
+	Rule decode;		/* next rule with same lhs */
+	Rule kids;		/* next rule with same _kids pattern */
+};
+extern Rule rule(char *id, Tree pattern, char *template, char *code);
+
+/* gram.y: */
+void yyerror(char *fmt, ...);
+int yyparse(void);
+void yywarn(char *fmt, ...);
+extern int errcnt;
+extern FILE *infp;
+extern FILE *outfp;
+
+#endif