Created
December 10, 2013 19:11
-
-
Save sebkirche/7896350 to your computer and use it in GitHub Desktop.
a simple expression parser generated from an ancient Yacc
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%token NAME NUMBER LPAREN RPAREN EQUAL PLUS MINUS | |
%token TIMES DIVIDE IF THEN ELSE | |
/* associativity and precedence: in order of increasing precedence */ | |
%nonassoc LOW /* dummy token to suggest shift on ELSE */ | |
%nonassoc ELSE /* higher than LOW */ | |
%nonassoc EQUAL | |
%left PLUS MINUS | |
%left TIMES DIVIDE | |
%left UMINUS /* dummy token to use as precedence marker */ | |
%% | |
stmt : IF exp THEN stmt %prec LOW | |
| IF exp THEN stmt ELSE stmt /* shift will be selected */ | |
| /* other types of statements would come here */ | |
; | |
exp : exp PLUS exp | |
| exp MINUS exp | |
| exp TIMES exp | |
| exp DIVIDE exp | |
| exp EQUAL exp | |
| LPAREN exp RPAREN | |
| MINUS exp %prec UMINUS /* this will force a reduce */ | |
| NAME | |
| NUMBER | |
; | |
%% | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# define NAME 257 | |
# define NUMBER 258 | |
# define LPAREN 259 | |
# define RPAREN 260 | |
# define EQUAL 261 | |
# define PLUS 262 | |
# define MINUS 263 | |
# define TIMES 264 | |
# define DIVIDE 265 | |
# define IF 266 | |
# define THEN 267 | |
# define ELSE 268 | |
# define LOW 269 | |
# define UMINUS 270 | |
#define yyclearin yychar = -1 | |
#define yyerrok yyerrflag = 0 | |
extern int yychar; | |
extern int yyerrflag; | |
#ifndef YYMAXDEPTH | |
#define YYMAXDEPTH 150 | |
#endif | |
#ifndef YYSTYPE | |
#define YYSTYPE int | |
#endif | |
YYSTYPE yylval, yyval; | |
typedef int yytabelem; | |
# define YYERRCODE 256 | |
# line 32 "exp.y" | |
yytabelem yyexca[] ={ | |
-1, 1, | |
0, -1, | |
-2, 0, | |
-1, 21, | |
261, 0, | |
-2, 8, | |
}; | |
# define YYNPROD 13 | |
# define YYLAST 42 | |
yytabelem yyact[]={ | |
13, 9, 10, 11, 12, 23, 8, 22, 13, 9, | |
10, 11, 12, 9, 10, 11, 12, 1, 2, 11, | |
12, 6, 7, 4, 3, 0, 16, 5, 0, 14, | |
15, 0, 0, 0, 17, 18, 19, 20, 21, 0, | |
0, 24 }; | |
yytabelem yypact[]={ | |
-248, -1000, -236, -261, -236, -236, -1000, -1000, -248, -236, | |
-236, -236, -236, -236, -253, -1000, -263, -245, -245, -1000, | |
-1000, -249, -1000, -248, -1000 }; | |
yytabelem yypgo[]={ | |
0, 17, 24 }; | |
yytabelem yyr1[]={ | |
0, 1, 1, 1, 2, 2, 2, 2, 2, 2, | |
2, 2, 2 }; | |
yytabelem yyr2[]={ | |
0, 8, 12, 0, 6, 6, 6, 6, 6, 6, | |
4, 2, 2 }; | |
yytabelem yychk[]={ | |
-1000, -1, 266, -2, 259, 263, 257, 258, 267, 262, | |
263, 264, 265, 261, -2, -2, -1, -2, -2, -2, | |
-2, -2, 260, 268, -1 }; | |
yytabelem yydef[]={ | |
3, -2, 0, 0, 0, 0, 11, 12, 3, 0, | |
0, 0, 0, 0, 0, 10, 1, 4, 5, 6, | |
7, -2, 9, 3, 2 }; | |
typedef struct { char *t_name; int t_val; } yytoktype; | |
#ifndef YYDEBUG | |
# define YYDEBUG 0 /* don't allow debugging */ | |
#endif | |
#if YYDEBUG | |
yytoktype yytoks[] = | |
{ | |
"NAME", 257, | |
"NUMBER", 258, | |
"LPAREN", 259, | |
"RPAREN", 260, | |
"EQUAL", 261, | |
"PLUS", 262, | |
"MINUS", 263, | |
"TIMES", 264, | |
"DIVIDE", 265, | |
"IF", 266, | |
"THEN", 267, | |
"ELSE", 268, | |
"LOW", 269, | |
"UMINUS", 270, | |
"-unknown-", -1 /* ends search */ | |
}; | |
char * yyreds[] = | |
{ | |
"-no such reduction-", | |
"stmt : IF exp THEN stmt", | |
"stmt : IF exp THEN stmt ELSE stmt", | |
"stmt : /* empty */", | |
"exp : exp PLUS exp", | |
"exp : exp MINUS exp", | |
"exp : exp TIMES exp", | |
"exp : exp DIVIDE exp", | |
"exp : exp EQUAL exp", | |
"exp : LPAREN exp RPAREN", | |
"exp : MINUS exp", | |
"exp : NAME", | |
"exp : NUMBER", | |
}; | |
#endif /* YYDEBUG */ | |
/* @(#)yaccpar 1.9 */ | |
/* | |
** Skeleton parser driver for yacc output | |
*/ | |
/* | |
** yacc user known macros and defines | |
*/ | |
#define YYERROR goto yyerrlab | |
#define YYACCEPT return(0) | |
#define YYABORT return(1) | |
#define YYBACKUP( newtoken, newvalue )\ | |
{\ | |
if ( yychar >= 0 || ( yyr2[ yytmp ] >> 1 ) != 1 )\ | |
{\ | |
yyerror( "syntax error - cannot backup" );\ | |
goto yyerrlab;\ | |
}\ | |
yychar = newtoken;\ | |
yystate = *yyps;\ | |
yylval = newvalue;\ | |
goto yynewstate;\ | |
} | |
#define YYRECOVERING() (!!yyerrflag) | |
#ifndef YYDEBUG | |
# define YYDEBUG 1 /* make debugging available */ | |
#endif | |
/* | |
** user known globals | |
*/ | |
int yydebug; /* set to 1 to get debugging */ | |
/* | |
** driver internal defines | |
*/ | |
#define YYFLAG (-1000) | |
/* | |
** global variables used by the parser | |
*/ | |
YYSTYPE yyv[ YYMAXDEPTH ]; /* value stack */ | |
int yys[ YYMAXDEPTH ]; /* state stack */ | |
YYSTYPE *yypv; /* top of value stack */ | |
int *yyps; /* top of state stack */ | |
int yystate; /* current state */ | |
int yytmp; /* extra var (lasts between blocks) */ | |
int yynerrs; /* number of errors */ | |
int yyerrflag; /* error recovery flag */ | |
int yychar; /* current input token number */ | |
/* | |
** yyparse - return 0 if worked, 1 if syntax error not recovered from | |
*/ | |
int | |
yyparse() | |
{ | |
register YYSTYPE *yypvt; /* top of value stack for $vars */ | |
/* | |
** Initialize externals - yyparse may be called more than once | |
*/ | |
yypv = &yyv[-1]; | |
yyps = &yys[-1]; | |
yystate = 0; | |
yytmp = 0; | |
yynerrs = 0; | |
yyerrflag = 0; | |
yychar = -1; | |
goto yystack; | |
{ | |
register YYSTYPE *yy_pv; /* top of value stack */ | |
register int *yy_ps; /* top of state stack */ | |
register int yy_state; /* current state */ | |
register int yy_n; /* internal state number info */ | |
/* | |
** get globals into registers. | |
** branch to here only if YYBACKUP was called. | |
*/ | |
yynewstate: | |
yy_pv = yypv; | |
yy_ps = yyps; | |
yy_state = yystate; | |
goto yy_newstate; | |
/* | |
** get globals into registers. | |
** either we just started, or we just finished a reduction | |
*/ | |
yystack: | |
yy_pv = yypv; | |
yy_ps = yyps; | |
yy_state = yystate; | |
/* | |
** top of for (;;) loop while no reductions done | |
*/ | |
yy_stack: | |
/* | |
** put a state and value onto the stacks | |
*/ | |
#if YYDEBUG | |
/* | |
** if debugging, look up token value in list of value vs. | |
** name pairs. 0 and negative (-1) are special values. | |
** Note: linear search is used since time is not a real | |
** consideration while debugging. | |
*/ | |
if ( yydebug ) | |
{ | |
register int yy_i; | |
printf( "State %d, token ", yy_state ); | |
if ( yychar == 0 ) | |
printf( "end-of-file\n" ); | |
else if ( yychar < 0 ) | |
printf( "-none-\n" ); | |
else | |
{ | |
for ( yy_i = 0; yytoks[yy_i].t_val >= 0; | |
yy_i++ ) | |
{ | |
if ( yytoks[yy_i].t_val == yychar ) | |
break; | |
} | |
printf( "%s\n", yytoks[yy_i].t_name ); | |
} | |
} | |
#endif /* YYDEBUG */ | |
if ( ++yy_ps >= &yys[ YYMAXDEPTH ] ) /* room on stack? */ | |
{ | |
yyerror( "yacc stack overflow" ); | |
YYABORT; | |
} | |
*yy_ps = yy_state; | |
*++yy_pv = yyval; | |
/* | |
** we have a new state - find out what to do | |
*/ | |
yy_newstate: | |
if ( ( yy_n = yypact[ yy_state ] ) <= YYFLAG ) | |
goto yydefault; /* simple state */ | |
#if YYDEBUG | |
/* | |
** if debugging, need to mark whether new token grabbed | |
*/ | |
yytmp = yychar < 0; | |
#endif | |
if ( ( yychar < 0 ) && ( ( yychar = yylex() ) < 0 ) ) | |
yychar = 0; /* reached EOF */ | |
#if YYDEBUG | |
if ( yydebug && yytmp ) | |
{ | |
register int yy_i; | |
printf( "Received token " ); | |
if ( yychar == 0 ) | |
printf( "end-of-file\n" ); | |
else if ( yychar < 0 ) | |
printf( "-none-\n" ); | |
else | |
{ | |
for ( yy_i = 0; yytoks[yy_i].t_val >= 0; | |
yy_i++ ) | |
{ | |
if ( yytoks[yy_i].t_val == yychar ) | |
break; | |
} | |
printf( "%s\n", yytoks[yy_i].t_name ); | |
} | |
} | |
#endif /* YYDEBUG */ | |
if ( ( ( yy_n += yychar ) < 0 ) || ( yy_n >= YYLAST ) ) | |
goto yydefault; | |
if ( yychk[ yy_n = yyact[ yy_n ] ] == yychar ) /*valid shift*/ | |
{ | |
yychar = -1; | |
yyval = yylval; | |
yy_state = yy_n; | |
if ( yyerrflag > 0 ) | |
yyerrflag--; | |
goto yy_stack; | |
} | |
yydefault: | |
if ( ( yy_n = yydef[ yy_state ] ) == -2 ) | |
{ | |
#if YYDEBUG | |
yytmp = yychar < 0; | |
#endif | |
if ( ( yychar < 0 ) && ( ( yychar = yylex() ) < 0 ) ) | |
yychar = 0; /* reached EOF */ | |
#if YYDEBUG | |
if ( yydebug && yytmp ) | |
{ | |
register int yy_i; | |
printf( "Received token " ); | |
if ( yychar == 0 ) | |
printf( "end-of-file\n" ); | |
else if ( yychar < 0 ) | |
printf( "-none-\n" ); | |
else | |
{ | |
for ( yy_i = 0; | |
yytoks[yy_i].t_val >= 0; | |
yy_i++ ) | |
{ | |
if ( yytoks[yy_i].t_val | |
== yychar ) | |
{ | |
break; | |
} | |
} | |
printf( "%s\n", yytoks[yy_i].t_name ); | |
} | |
} | |
#endif /* YYDEBUG */ | |
/* | |
** look through exception table | |
*/ | |
{ | |
register int *yyxi = yyexca; | |
while ( ( *yyxi != -1 ) || | |
( yyxi[1] != yy_state ) ) | |
{ | |
yyxi += 2; | |
} | |
while ( ( *(yyxi += 2) >= 0 ) && | |
( *yyxi != yychar ) ) | |
; | |
if ( ( yy_n = yyxi[1] ) < 0 ) | |
YYACCEPT; | |
} | |
} | |
/* | |
** check for syntax error | |
*/ | |
if ( yy_n == 0 ) /* have an error */ | |
{ | |
/* no worry about speed here! */ | |
switch ( yyerrflag ) | |
{ | |
case 0: /* new error */ | |
yyerror( "syntax error" ); | |
goto skip_init; | |
yyerrlab: | |
/* | |
** get globals into registers. | |
** we have a user generated syntax type error | |
*/ | |
yy_pv = yypv; | |
yy_ps = yyps; | |
yy_state = yystate; | |
yynerrs++; | |
skip_init: | |
case 1: | |
case 2: /* incompletely recovered error */ | |
/* try again... */ | |
yyerrflag = 3; | |
/* | |
** find state where "error" is a legal | |
** shift action | |
*/ | |
while ( yy_ps >= yys ) | |
{ | |
yy_n = yypact[ *yy_ps ] + YYERRCODE; | |
if ( yy_n >= 0 && yy_n < YYLAST && | |
yychk[yyact[yy_n]] == YYERRCODE) { | |
/* | |
** simulate shift of "error" | |
*/ | |
yy_state = yyact[ yy_n ]; | |
goto yy_stack; | |
} | |
/* | |
** current state has no shift on | |
** "error", pop stack | |
*/ | |
#if YYDEBUG | |
# define _POP_ "Error recovery pops state %d, uncovers state %d\n" | |
if ( yydebug ) | |
printf( _POP_, *yy_ps, | |
yy_ps[-1] ); | |
# undef _POP_ | |
#endif | |
yy_ps--; | |
yy_pv--; | |
} | |
/* | |
** there is no state on stack with "error" as | |
** a valid shift. give up. | |
*/ | |
YYABORT; | |
case 3: /* no shift yet; eat a token */ | |
#if YYDEBUG | |
/* | |
** if debugging, look up token in list of | |
** pairs. 0 and negative shouldn't occur, | |
** but since timing doesn't matter when | |
** debugging, it doesn't hurt to leave the | |
** tests here. | |
*/ | |
if ( yydebug ) | |
{ | |
register int yy_i; | |
printf( "Error recovery discards " ); | |
if ( yychar == 0 ) | |
printf( "token end-of-file\n" ); | |
else if ( yychar < 0 ) | |
printf( "token -none-\n" ); | |
else | |
{ | |
for ( yy_i = 0; | |
yytoks[yy_i].t_val >= 0; | |
yy_i++ ) | |
{ | |
if ( yytoks[yy_i].t_val | |
== yychar ) | |
{ | |
break; | |
} | |
} | |
printf( "token %s\n", | |
yytoks[yy_i].t_name ); | |
} | |
} | |
#endif /* YYDEBUG */ | |
if ( yychar == 0 ) /* reached EOF. quit */ | |
YYABORT; | |
yychar = -1; | |
goto yy_newstate; | |
} | |
}/* end if ( yy_n == 0 ) */ | |
/* | |
** reduction by production yy_n | |
** put stack tops, etc. so things right after switch | |
*/ | |
#if YYDEBUG | |
/* | |
** if debugging, print the string that is the user's | |
** specification of the reduction which is just about | |
** to be done. | |
*/ | |
if ( yydebug ) | |
printf( "Reduce by (%d) \"%s\"\n", | |
yy_n, yyreds[ yy_n ] ); | |
#endif | |
yytmp = yy_n; /* value to switch over */ | |
yypvt = yy_pv; /* $vars top of value stack */ | |
/* | |
** Look in goto table for next state | |
** Sorry about using yy_state here as temporary | |
** register variable, but why not, if it works... | |
** If yyr2[ yy_n ] doesn't have the low order bit | |
** set, then there is no action to be done for | |
** this reduction. So, no saving & unsaving of | |
** registers done. The only difference between the | |
** code just after the if and the body of the if is | |
** the goto yy_stack in the body. This way the test | |
** can be made before the choice of what to do is needed. | |
*/ | |
{ | |
/* length of production doubled with extra bit */ | |
register int yy_len = yyr2[ yy_n ]; | |
if ( !( yy_len & 01 ) ) | |
{ | |
yy_len >>= 1; | |
yyval = ( yy_pv -= yy_len )[1]; /* $$ = $1 */ | |
yy_state = yypgo[ yy_n = yyr1[ yy_n ] ] + | |
*( yy_ps -= yy_len ) + 1; | |
if ( yy_state >= YYLAST || | |
yychk[ yy_state = | |
yyact[ yy_state ] ] != -yy_n ) | |
{ | |
yy_state = yyact[ yypgo[ yy_n ] ]; | |
} | |
goto yy_stack; | |
} | |
yy_len >>= 1; | |
yyval = ( yy_pv -= yy_len )[1]; /* $$ = $1 */ | |
yy_state = yypgo[ yy_n = yyr1[ yy_n ] ] + | |
*( yy_ps -= yy_len ) + 1; | |
if ( yy_state >= YYLAST || | |
yychk[ yy_state = yyact[ yy_state ] ] != -yy_n ) | |
{ | |
yy_state = yyact[ yypgo[ yy_n ] ]; | |
} | |
} | |
/* save until reenter driver code */ | |
yystate = yy_state; | |
yyps = yy_ps; | |
yypv = yy_pv; | |
} | |
/* | |
** code supplied by user is placed in this switch | |
*/ | |
switch( yytmp ) | |
{ | |
} | |
goto yystack; /* reset registers in driver code */ | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment