_GENERATING PARSERS WITH PCYACC_
by Alex Lane
[LISTING ONE]
yacc specification
/* TEST.Y
This specification is based largely on the yacc
specification for a simple desk calculator from "Compilers:
Principles, Techniques and Tools," by Aho, et al. (p. 259,
Addison-Wesley, 1986).
2/2/89 a.lane
*/
%{
#include <stdio.h>
#include <ctype.h>
%}
%token DIGIT
%left '+'
%left '*'
%%
line : /* nothing */
| expr '\n' { printf("%d\n", $1); }
;
expr : expr '+' term { $$ = $1 + $3; }
| term
;
term : term '*' factor { $$ = $1 * $3; }
| factor
;
factor: '(' expr ')' { $$ = $2; }
| DIGIT
;
%%
main() {
yyparse();
}
yylex() {
int c;
if ( isdigit( ( c = getchar() ) ) ) {
yylval = c - '0';
return DIGIT;
}
return c;
}
yyerror(s)
char *s;
{
fprintf(stderr, "PYERR: %s\n", s);
}
[LISTING TWO]
# line 11 "test.y"
#include <stdio.h>
#include <ctype.h>
#define DIGIT 257
#ifndef YYSTYPE
#define YYSTYPE int
#endif
YYSTYPE yylval, yyval;
#define YYERRCODE 256
# line 33 "test.y"
main() {
yyparse();
}
yylex() {
int c;
if ( isdigit( ( c = getchar() ) ) ) {
yylval = c - '0';
return DIGIT;
}
return c;
}
yyerror(s)
char *s;
{
fprintf(stderr, "PYERR: %s\n", s);
}
FILE *yytfilep;
char *yytfilen;
int yytflag = 0;
int svdprd[2];
char svdnams[2][2];
int yyexca[] = {
-1, 1,
0, -1,
-2, 0,
0,
};
#define YYNPROD 9
#define YYLAST 218
int yyact[] = {
5, 7, 13, 4, 8, 9, 3, 1,
2, 0, 0, 0, 0, 12, 10, 11,
4, 0, 3, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 8, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 6,
};
int yypact[] = {
-40, -1000, -9, -37, -1000, -40, -1000, -1000,
-40, -40, -39, -37, -1000, -1000,
};
int yypgo[] = {
0, 7, 8, 6, 3,
};
int yyr1[] = {
0, 1, 1, 2, 2, 3, 3, 4,
4,
};
int yyr2[] = {
2, 0, 2, 3, 1, 3, 1, 3,
1,
};
int yychk[] = {
-1000, -1, -2, -3, -4, 40, 257, 10,
43, 42, -2, -3, -4, 41,
};
int yydef[] = {
1, -2, 0, 4, 6, 0, 8, 2,
0, 0, 0, 3, 5, 7,
};
int *yyxi;
/*****************************************************************/
/* PCYACC LALR parser driver routine -- a table driven procedure */
/* for recognizing sentences of a language defined by the */
/* grammar that PCYACC analyzes. An LALR parsing table is then */
/* constructed for the grammar and the skeletal parser uses the */
/* table when performing syntactical analysis on input source */
/* programs. The actions associated with grammar rules are */
/* inserted into a switch statement for execution. */
/*****************************************************************/
#ifndef YYMAXDEPTH
#define YYMAXDEPTH 200
#endif
#ifndef YYREDMAX
#define YYREDMAX 1000
#endif
#define PCYYFLAG -1000
#define WAS0ERR 0
#define WAS1ERR 1
#define WAS2ERR 2
#define WAS3ERR 3
#define yyclearin pcyytoken = -1
#define yyerrok pcyyerrfl = 0
YYSTYPE yyv[YYMAXDEPTH]; /* value stack */
int pcyyerrct = 0; /* error count */
int pcyyerrfl = 0; /* error flag */
int redseq[YYREDMAX];
int redcnt = 0;
int pcyytoken = -1; /* input token */
yyparse()
{
int statestack[YYMAXDEPTH]; /* state stack */
int j, m; /* working index */
YYSTYPE *yypvt;
int tmpstate, tmptoken, *yyps, n;
YYSTYPE *yypv;
tmpstate = 0;
pcyytoken = -1;
#ifdef YYDEBUG
tmptoken = -1;
#endif
pcyyerrct = 0;
pcyyerrfl = 0;
yyps = &statestack[-1];
yypv = &yyv[-1];
enstack: /* push stack */
#ifdef YYDEBUG
printf("at state %d, next token %d\n", tmpstate, tmptoken);
#endif
if (++yyps - &statestack[YYMAXDEPTH] > 0) {
yyerror("pcyacc internal stack overflow");
return(1);
}
*yyps = tmpstate;
++yypv;
*yypv = yyval;
newstate:
n = yypact[tmpstate];
if (n <= PCYYFLAG) goto defaultact; /* a simple state */
if (pcyytoken < 0) if ((pcyytoken=yylex()) < 0) pcyytoken = 0;
if ((n += pcyytoken) < 0 || n >= YYLAST) goto defaultact;
if (yychk[n=yyact[n]] == pcyytoken) { /* a shift */
#ifdef YYDEBUG
tmptoken = pcyytoken;
#endif
pcyytoken = -1;
yyval = yylval;
tmpstate = n;
if (pcyyerrfl > 0) --pcyyerrfl;
goto enstack;
}
defaultact:
if ((n=yydef[tmpstate]) == -2) {
if (pcyytoken < 0) if ((pcyytoken=yylex())<0) pcyytoken = 0;
for (yyxi=yyexca; (*yyxi!= (-1)) || (yyxi[1]!=tmpstate); yyxi += 2);
while (*(yyxi+=2) >= 0) if (*yyxi == pcyytoken) break;
if ((n=yyxi[1]) < 0) { /* an accept action */
if (yytflag) {
int ti; int tj;
yytfilep = fopen(yytfilen, "w");
if (yytfilep == NULL) {
fprintf(stderr, "Can't open t file: %s\n", yytfilen);
return(0); }
for (ti=redcnt-1; ti>=0; ti--) {
tj = svdprd[redseq[ti]];
while (strcmp(svdnams[tj], "$EOP"))
fprintf(yytfilep, "%s ", svdnams[tj++]);
fprintf(yytfilep, "\n");
}
fclose(yytfilep);
}
return (0);
}
}
if (n == 0) { /* error situation */
switch (pcyyerrfl) {
case WAS0ERR: /* an error just occurred */
yyerror("syntax error");
yyerrlab:
++pcyyerrct;
case WAS1ERR:
case WAS2ERR: /* try again */
pcyyerrfl = 3;
/* find a state for a legal shift action */
while (yyps >= statestack) {
n = yypact[*yyps] + YYERRCODE;
if (n >= 0 && n < YYLAST && yychk[yyact[n]] == YYERRCODE) {
tmpstate = yyact[n]; /* simulate a shift of "error" */
goto enstack;
}
n = yypact[*yyps];
/* the current yyps has no shift on "error", pop stack */
#ifdef YYDEBUG
printf("error: pop state %d, recover state %d\n", *yyps, yyps[-
1]);
#endif
--yyps;
--yypv;
}
yyabort:
if (yytflag) {
int ti; int tj;
yytfilep = fopen(yytfilen, "w");
if (yytfilep == NULL) {
fprintf(stderr, "Can't open t file: %s\n", yytfilen);
return(1); }
for (ti=1; ti<redcnt; ti++) {
tj = svdprd[redseq[ti]];
while (strcmp(svdnams[tj], "$EOP"))
fprintf(yytfilep, "%s ", svdnams[tj++]);
fprintf(yytfilep, "\n");
}
fclose(yytfilep);
}
return(1);
case WAS3ERR: /* clobber input char */
#ifdef YYDEBUG
printf("error: discard token %d\n", pcyytoken);
#endif
if (pcyytoken == 0) goto yyabort; /* quit */
pcyytoken = -1;
goto newstate; } /* switch */
} /* if */
/* reduction, given a production n */
#ifdef YYDEBUG
printf("reduce with rule %d\n", n);
#endif
if (yytflag && redcnt<YYREDMAX) redseq[redcnt++] = n;
yyps -= yyr2[n];
yypvt = yypv;
yypv -= yyr2[n];
yyval = yypv[1];
m = n;
/* find next state from goto table */
n = yyr1[n];
j = yypgo[n] + *yyps + 1;
if (j>=YYLAST || yychk[ tmpstate = yyact[j] ] != -n) tmpstate =
yyact[yypgo[n]];
switch (m) { /* actions associated with grammar rules */
case 2:
# line 22 "test.y"
{ printf("%d\n", yypvt[-1]); } break;
case 3:
# line 24 "test.y"
{ yyval = yypvt[-2] + yypvt[-0]; } break;
case 5:
# line 27 "test.y"
{ yyval = yypvt[-2] * yypvt[-0]; } break;
case 7:
# line 30 "test.y"
{ yyval = yypvt[-1]; } break; }
goto enstack;
}