From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- lcc/lburg/gram.c | 1360 ++++++++++++++++++++++++++--------------------------- lcc/lburg/gram.y | 404 ++++++++-------- lcc/lburg/lburg.1 | 358 +++++++------- lcc/lburg/lburg.c | 1342 ++++++++++++++++++++++++++-------------------------- lcc/lburg/lburg.h | 130 ++--- 5 files changed, 1797 insertions(+), 1797 deletions(-) (limited to 'lcc/lburg') diff --git a/lcc/lburg/gram.c b/lcc/lburg/gram.c index b484e57..6e1f6e4 100755 --- a/lcc/lburg/gram.c +++ b/lcc/lburg/gram.c @@ -1,680 +1,680 @@ -#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 -#endif -#ifdef __cplusplus -#include /* for malloc/realloc/free */ -#endif -#line 2 "lburg/gram.y" -#include -#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 () -{ - int old_stacksize = yystacksize; - 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 -#include -#include -#include -#include - -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; -#endif -yynewerror: - yyerror("syntax error"); -#ifdef lint - goto yyerrlab; -#endif -yyerrlab: - ++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); -} +#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 +#endif +#ifdef __cplusplus +#include /* for malloc/realloc/free */ +#endif +#line 2 "lburg/gram.y" +#include +#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 () +{ + int old_stacksize = yystacksize; + 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 +#include +#include +#include +#include + +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; +#endif +yynewerror: + yyerror("syntax error"); +#ifdef lint + goto yyerrlab; +#endif +yyerrlab: + ++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/lcc/lburg/gram.y b/lcc/lburg/gram.y index 860d22a..1ecd8a9 100755 --- a/lcc/lburg/gram.y +++ b/lcc/lburg/gram.y @@ -1,202 +1,202 @@ -%{ -#include -#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 ID TEMPLATE CODE -%token INT -%type nonterm cost -%type 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 -#include -#include -#include -#include - -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); -} +%{ +#include +#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 ID TEMPLATE CODE +%token INT +%type nonterm cost +%type 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 +#include +#include +#include +#include + +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/lcc/lburg/lburg.1 b/lcc/lburg/lburg.1 index d633e6b..8cf7250 100755 --- a/lcc/lburg/lburg.1 +++ b/lcc/lburg/lburg.1 @@ -1,179 +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. +.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/lcc/lburg/lburg.c b/lcc/lburg/lburg.c index a34e4e7..c43c96a 100755 --- a/lcc/lburg/lburg.c +++ b/lcc/lburg/lburg.c @@ -1,671 +1,671 @@ -#include -#include -#include -#include -#include -#include -#include -#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); - } -} +#include +#include +#include +#include +#include +#include +#include +#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/lcc/lburg/lburg.h b/lcc/lburg/lburg.h index 238fe98..b67e802 100755 --- a/lcc/lburg/lburg.h +++ b/lcc/lburg/lburg.h @@ -1,65 +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 +#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 -- cgit v1.2.3