From d4b977d0904a1dea37922dac60d3bb37f9769230 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Thu, 5 Jan 2012 04:47:56 +1000 Subject: Add a simple flex + btyacc stub. Will be fleshed out soon with LSL grammer. --- .gitignore | 5 + LuaSL/build.sh | 27 +- LuaSL/src/LuaSL_LSL_tree.c | 63 +++ LuaSL/src/LuaSL_LSL_tree.h | 55 +++ LuaSL/src/LuaSL_lexer.l | 31 ++ LuaSL/src/LuaSL_parser.c | 86 ++++ LuaSL/src/LuaSL_parser_param.h | 38 ++ LuaSL/src/LuaSL_type_parser.h | 29 ++ LuaSL/src/LuaSL_yaccer.y | 36 ++ LuaSL/src/btyacc-c.ske | 939 +++++++++++++++++++++++++++++++++++++++++ 10 files changed, 1308 insertions(+), 1 deletion(-) create mode 100644 LuaSL/src/LuaSL_LSL_tree.c create mode 100644 LuaSL/src/LuaSL_LSL_tree.h create mode 100644 LuaSL/src/LuaSL_lexer.l create mode 100644 LuaSL/src/LuaSL_parser.c create mode 100644 LuaSL/src/LuaSL_parser_param.h create mode 100644 LuaSL/src/LuaSL_type_parser.h create mode 100644 LuaSL/src/LuaSL_yaccer.y create mode 100644 LuaSL/src/btyacc-c.ske diff --git a/.gitignore b/.gitignore index f9743a0..8555fd6 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,8 @@ *.edj *.o LuaSL/LuaSL +LuaSL/LuaSL_parser +LuaSL/src/*.tab.* +LuaSL/src/LuaSL_lexer.c +LuaSL/src/LuaSL_lexer.h + diff --git a/LuaSL/build.sh b/LuaSL/build.sh index 6aba3a0..9f2420b 100755 --- a/LuaSL/build.sh +++ b/LuaSL/build.sh @@ -51,7 +51,7 @@ names="LuaSL_main LuaSL_compile LuaSL_utilities" EDJE_FLAGS="-id images -fd fonts" -rm -f LuaSL *.o *.edj +rm -f ../LuaSL ../LuaSL_parser *.o *.edj LuaSL_lexer.h LuaSL_lexer.c LuaSL_yaccer.h LuaSL_yaccer.tab.c command="edje_cc $EDJE_FLAGS LuaSL.edc ../LuaSL.edj" echo $command $command @@ -69,3 +69,28 @@ command="gcc $CFLAGS -o ../LuaSL $objects $LDFLAGS $libs" echo $command $command + + +names="LuaSL_parser LuaSL_LSL_tree LuaSL_lexer LuaSL_yaccer.tab" + +command="flex --outfile=LuaSL_lexer.c --header-file=LuaSL_lexer.h LuaSL_lexer.l" +echo $command +$command + +command="btyacc -d -b LuaSL_yaccer -S btyacc-c.ske LuaSL_yaccer.y" +echo $command +$command + +objects="" +for i in $names +do + command="gcc $CFLAGS -c -o ../$i.o $i.c" + echo $command + $command + objects="$objects ../$i.o" +done + +command="gcc $CFLAGS -o ../LuaSL_parser $objects $LDFLAGS $libs" +echo $command +$command + diff --git a/LuaSL/src/LuaSL_LSL_tree.c b/LuaSL/src/LuaSL_LSL_tree.c new file mode 100644 index 0000000..78da8e7 --- /dev/null +++ b/LuaSL/src/LuaSL_LSL_tree.c @@ -0,0 +1,63 @@ +/* + * Implementation of functions used to build the abstract syntax tree. + */ + +#include "LuaSL_LSL_tree.h" +#include + +/** + * @brief Allocates space for expression + * @return The expression or NULL if not enough memory + */ +static SExpression* allocateExpression() +{ + SExpression* b = malloc(sizeof *b); + + if( b == NULL ) return NULL; + + b->type = eVALUE; + b->value = 0; + + b->left = NULL; + b->right = NULL; + + return b; +} + +SExpression* createNumber(int value) +{ + SExpression* b = allocateExpression(); + + if( b == NULL ) return NULL; + + b->type = eVALUE; + b->value = value; + + return b; +} + +SExpression *createOperation( + EOperationType type, + SExpression *left, + SExpression *right) +{ + SExpression* b = allocateExpression(); + + if( b == NULL ) return NULL; + + b->type = type; + b->left = left; + b->right = right; + + return b; +} + +void deleteExpression(SExpression *b) +{ + if (b == NULL) return; + + deleteExpression(b->left); + deleteExpression(b->right); + + free(b); +} diff --git a/LuaSL/src/LuaSL_LSL_tree.h b/LuaSL/src/LuaSL_LSL_tree.h new file mode 100644 index 0000000..6d89672 --- /dev/null +++ b/LuaSL/src/LuaSL_LSL_tree.h @@ -0,0 +1,55 @@ +/* + * Definition of the structure used to build the abstract syntax tree. + */ +#ifndef __EXPRESSION_H__ +#define __EXPRESSION_H__ + +/** + * @brief The operation type + */ +typedef enum tagEOperationType +{ + eVALUE, + eMULTIPLY, + ePLUS +}EOperationType; + +/** + * @brief The expression structure + */ +typedef struct tagSExpression +{ + EOperationType type;///< type of operation + + int value;///< valid only when type is eVALUE + struct tagSExpression* left; ///< left side of the tree + struct tagSExpression* right;///< right side of the tree +}SExpression; + +/** + * @brief It creates an identifier + * @param value The number value + * @return The expression or NULL in case of no memory + */ +SExpression* createNumber(int value); + +/** + * @brief It creates an operation + * @param type The operation type + * @param left The left operand + * @param right The right operand + * @return The expression or NULL in case of no memory + */ +SExpression* createOperation( + EOperationType type, + SExpression *left, + SExpression *right); + +/** + * @brief Deletes a expression + * @param b The expression + */ +void deleteExpression(SExpression *b); + +#endif // __EXPRESSION_H__ + diff --git a/LuaSL/src/LuaSL_lexer.l b/LuaSL/src/LuaSL_lexer.l new file mode 100644 index 0000000..f55d458 --- /dev/null +++ b/LuaSL/src/LuaSL_lexer.l @@ -0,0 +1,31 @@ +%{ + +#include "LuaSL_type_parser.h" +#include "LuaSL_yaccer.tab.h" + +%} + +%option reentrant noyywrap never-interactive nounistd +%option bison-bridge + +LPAREN "(" +RPAREN ")" +PLUS "+" +MULTIPLY "*" + +NUMBER [0-9]+ +WS [ \r\n\t]* + +%% + +{WS} { /* Skip blanks. */ } +{NUMBER} { sscanf(yytext,"%d",&yylval->value); return TOKEN_NUMBER; } + +{MULTIPLY} { return TOKEN_MULTIPLY; } +{PLUS} { return TOKEN_PLUS; } +{LPAREN} { return TOKEN_LPAREN; } +{RPAREN} { return TOKEN_RPAREN; } +. { } + +%% + diff --git a/LuaSL/src/LuaSL_parser.c b/LuaSL/src/LuaSL_parser.c new file mode 100644 index 0000000..9e1d3ca --- /dev/null +++ b/LuaSL/src/LuaSL_parser.c @@ -0,0 +1,86 @@ +#include "LuaSL_parser_param.h" +#include "LuaSL_yaccer.tab.h" + + +int yyparse(void *param); + +static int initParserParam(SParserParam* param) +{ + int ret = 0; + + ret = yylex_init(¶m->scanner); + param->expression = NULL; + + return ret; +} + +static int destroyParserParam(SParserParam* param) +{ + return yylex_destroy(param->scanner); +} + +SExpression *getAST(const char *expr) +{ + SParserParam p; + YY_BUFFER_STATE state; + + if ( initParserParam(&p) ) + { + // couldn't initialize + return NULL; + } + + state = yy_scan_string(expr, p.scanner); + + if ( yyparse(&p) ) + { + // error parsing + return NULL; + } + + yy_delete_buffer(state, p.scanner); + + destroyParserParam(&p); + + return p.expression; +} + +int evaluate(SExpression *e) +{ + switch(e->type) + { + case eVALUE: + return e->value; + case eMULTIPLY: + return evaluate(e->left) * evaluate(e->right); + case ePLUS: + return evaluate(e->left) + evaluate(e->right); + default: + // shouldn't be here + return 0; + } +} + +int yyerror(const char *msg) +{ + fprintf(stderr,"Error:%s\n",msg); return 0; +} + +int main(void) +{ + SExpression *e = NULL; + char test[]=" 4 + 2*10 + 3*( 5 + 1 )"; + int result = 0; + + e = getAST(test); + + result = evaluate(e); + + printf("Result of '%s' is %d\n", test, result); + + deleteExpression(e); + + return 0; +} + + diff --git a/LuaSL/src/LuaSL_parser_param.h b/LuaSL/src/LuaSL_parser_param.h new file mode 100644 index 0000000..944a671 --- /dev/null +++ b/LuaSL/src/LuaSL_parser_param.h @@ -0,0 +1,38 @@ +/* + * ParserParam.h + * Definitions of the parameters for the reentrant functions + * of flex (yylex) and bison (yyparse) + */ + +// Since in this sample we use the reentrant version of both flex and yacc we are forced to provide parameters for the yylex function, when called from yyparse. + +#ifndef __PARSERPARAM_H__ +#define __PARSERPARAM_H__ + +#ifndef YY_NO_UNISTD_H +#define YY_NO_UNISTD_H 1 +#endif // YY_NO_UNISTD_H + +#include "LuaSL_type_parser.h" +#include "LuaSL_lexer.h" +#include "LuaSL_LSL_tree.h" + +/** + * @brief structure given as argument to the reentrant 'yyparse' function. + */ +typedef struct tagSParserParam +{ + yyscan_t scanner; + SExpression *expression; +}SParserParam; + +// the parameter name (of the reentrant 'yyparse' function) +// data is a pointer to a 'SParserParam' structure +#define YYPARSE_PARAM data + +// the argument for the 'yylex' function +#define YYLEX_PARAM ((SParserParam*)data)->scanner + +#endif // __PARSERPARAM_H__ + + diff --git a/LuaSL/src/LuaSL_type_parser.h b/LuaSL/src/LuaSL_type_parser.h new file mode 100644 index 0000000..66c3f5d --- /dev/null +++ b/LuaSL/src/LuaSL_type_parser.h @@ -0,0 +1,29 @@ +/* + * TypeParser.h + * Definition of the structure used internally by the parser and lexer + * to exchange data. + */ + +#ifndef __TYPE_PARSER_H__ +#define __TYPE_PARSER_H__ + +#include "LuaSL_LSL_tree.h" + +/** + * @brief The structure used by flex and bison + */ +typedef union tagTypeParser +{ + SExpression *expression; + int value; +}STypeParser; + +// define the type for flex and bison +#define YYSTYPE STypeParser + +int yyerror(const char *msg); + + +#endif // __TYPE_PARSER_H__ + + diff --git a/LuaSL/src/LuaSL_yaccer.y b/LuaSL/src/LuaSL_yaccer.y new file mode 100644 index 0000000..07f1fd7 --- /dev/null +++ b/LuaSL/src/LuaSL_yaccer.y @@ -0,0 +1,36 @@ +%{ + +#include "LuaSL_parser_param.h" +#include "LuaSL_yaccer.tab.h" + +%} + +%define api.pure + +%left '+' TOKEN_PLUS +%left '*' TOKEN_MULTIPLY + +%token TOKEN_LPAREN +%token TOKEN_RPAREN +%token TOKEN_PLUS +%token TOKEN_MULTIPLY + +%token TOKEN_NUMBER + +%type expr + +%% + +input: + expr { ((SParserParam*)data)->expression = $1; } + ; + +expr: + expr TOKEN_PLUS expr { $$ = createOperation( ePLUS, $1, $3 ); } + | expr TOKEN_MULTIPLY expr { $$ = createOperation( eMULTIPLY, $1, $3 ); } + | TOKEN_LPAREN expr TOKEN_RPAREN { $$ = $2; } + | TOKEN_NUMBER { $$ = createNumber($1); } +; + +%% + diff --git a/LuaSL/src/btyacc-c.ske b/LuaSL/src/btyacc-c.ske new file mode 100644 index 0000000..ac0fcd5 --- /dev/null +++ b/LuaSL/src/btyacc-c.ske @@ -0,0 +1,939 @@ +/* -*- C -*- + + The banner used here should be replaced with an #ident directive if + the target C compiler supports #ident directives. + + If the skeleton is changed, the banner should be changed so that + the altered version can easily be distinguished from the original. */ + +%% banner +/* -*- C -*- + + @(#)btyaccpar, based on byacc 1.8 (Berkeley), modified for rentrant flex. + +*/ +#define YYBTYACC 1 + +#include +#include +#include + +typedef int Yshort; + +%% tables + +#ifndef _YACC_EXTERN_ +# define _YACC_EXTERN_ "C" +#endif + +extern _YACC_EXTERN_ Yshort yylhs[]; +extern _YACC_EXTERN_ Yshort yylen[]; + +/* idx: current state; entry: non-zero if to reduce regardless of lookahead*/ +extern _YACC_EXTERN_ Yshort yydefred[]; + +extern _YACC_EXTERN_ Yshort yydgoto[]; + +/* idx: current state; entry: non-zero if shifting|reducing possible + in this state - in that case, yycheck[entry + lookahead] indicates + whether to perform the action for this lookahead. */ +extern _YACC_EXTERN_ Yshort yysindex[]; +extern _YACC_EXTERN_ Yshort yyrindex[]; + +/* yycindex idx: current state; entry: non-zero if shift/reduce + conflicts for this state - in that case, yycheck[entry + lookahead] + indicates whether there's a conflict for this lookahead */ +extern _YACC_EXTERN_ Yshort yycindex[]; +extern _YACC_EXTERN_ Yshort yycheck[]; + +extern _YACC_EXTERN_ Yshort yygindex[]; +extern _YACC_EXTERN_ Yshort yytable[]; +extern _YACC_EXTERN_ Yshort yyctable[]; + +#if YYDEBUG +/* idx: token code; entry: spelling of token */ +extern _YACC_EXTERN_ char *yyname[]; + +extern _YACC_EXTERN_ char *yyrule[]; +#endif + +%% header + +/* YYPOSN is user-defined text position type. */ +#ifndef YYPOSN +# define YYPOSN int +#endif + +#ifdef YYREDUCEPOSNFUNC +# define YYCALLREDUCEPOSN(e) \ + if(reduce_posn) { \ + YYREDUCEPOSNFUNC(yyps->pos, &(yyps->psp)[1-yym], &(yyps->vsp)[1-yym],\ + yym, yyps->psp - yyps->ps, yychar, yyposn, e); \ + reduce_posn = 0; \ + } + +# ifndef YYCALLREDUCEPOSNARG +# define YYCALLREDUCEPOSNARG (yyps->val) +# endif + + +# define YYPOSNARG(n) ((yyps->psp)[1-yym+(n)-1]) +# define YYPOSNOUT (yyps->pos) +#endif + +/* If delete function is not defined by the user, do not delete. */ +#ifndef YYDELETEVAL +# define YYDELETEVAL(v, t) +#endif + +/* If delete function is not defined by the user, do not delete. */ +#ifndef YYDELETEPOSN +# define YYDELETEPOSN(v, t) +#endif + +#define YYEMPTY (-1) +#define yyclearin (yychar=YYEMPTY) + +#define yyerrok (yyps->errflag=0) + +#ifndef YYSTACKGROWTH +# define YYSTACKGROWTH 32 +#endif + +#ifndef YYDEFSTACKSIZE +# define YYDEFSTACKSIZE 12 +#endif + +#ifdef YYDEBUG +int yydebug = 0; +#endif + +int yynerrs; + +/* These value/posn are taken from the lexer */ +YYSTYPE yylval; +YYPOSN yyposn; + +/* These value/posn of the root non-terminal are returned to the caller */ +YYSTYPE yyretlval; +YYPOSN yyretposn; + +#define YYABORT goto yyabort +#define YYACCEPT goto yyaccept +#define YYERROR goto yyerrlab +#define YYVALID do { if (yyps->save) goto yyvalid; } while(0) +#define YYVALID_NESTED do { if (yyps->save && \ + yyps->save->save==0) goto yyvalid; } while(0) + +struct YYParseState_s { + struct YYParseState_s *save; /* Previously saved parser state */ + int state; + int errflag; + Yshort *ssp; /* state stack pointer */ + YYSTYPE *vsp; /* value stack pointer */ + YYPOSN *psp; /* position stack pointer */ + YYSTYPE val; /* value as returned by actions */ + YYPOSN pos; /* position as returned by universal action */ + Yshort *ss; /* state stack base */ + YYSTYPE *vs; /* values stack base */ + YYPOSN *ps; /* position stack base */ + int lexeme; /* index of conflict lexeme in lexical queue */ + unsigned int stacksize; /* current maximum stack size */ + Yshort ctry; /* index in yyctable[] for this conflict */ +}; +typedef struct YYParseState_s YYParseState; + +/* Current parser state */ +static YYParseState *yyps = 0; + +/* yypath!=NULL: do the full parse, starting at *yypath parser state. */ +static YYParseState *yypath = 0; + +/* Base of the lexical value queue */ +static YYSTYPE *yylvals = 0; + +/* Current position at lexical value queue */ +static YYSTYPE *yylvp = 0; + +/* End position of lexical value queue */ +static YYSTYPE *yylve = 0; + +/* The last allocated position at the lexical value queue */ +static YYSTYPE *yylvlim = 0; + +/* Base of the lexical position queue */ +static YYPOSN *yylpsns = 0; + +/* Current position at lexical position queue */ +static YYPOSN *yylpp = 0; + +/* End position of lexical position queue */ +static YYPOSN *yylpe = 0; + +/* The last allocated position at the lexical position queue */ +static YYPOSN *yylplim = 0; + +/* Current position at lexical token queue */ +static Yshort *yylexp = 0; + +static Yshort *yylexemes = 0; + +/* For use in generated program */ +#define yytrial (yyps->save) +#define yyvsp (yyps->vsp) +#define yyval (yyps->val) +#define yydepth (yyps->ssp - yyps->ss) + + +/* Local prototypes. */ +int yyparse(void *YYPARSE_PARAM); + +static int yyLex1(yyscan_t scanner); +static int yyExpand(); +static void yySCopy(YYSTYPE *to, YYSTYPE *from, int size); +static void yyPCopy(YYPOSN *to, YYPOSN *from, int size); +static void yyMoreStack(YYParseState *yyps); +static YYParseState *yyNewState(int size); +static void yyFreeState(YYParseState *p); + + +%% body + + +/* Parser function. Roughly looks like this: + int yyparse(void *YYPARSE_PARAM) { + yyloop: + if (reduce_possible) goto yyreduce; + read_token; + if (conflict) { + handle_conflict; + goto yyshift; or goto yyreduce; + } + if (shift_possible) { + yyshift: + do_shift; + goto yyloop; + } + if (reduce_possible) goto yyreduce; + + (error handling); + goto yyloop; + + yyreduce: + BIG_CHUNK_OF_RULE_ACTIONS; + goto yyloop; + + (more error handling); + }*/ +int yyparse(void *YYPARSE_PARAM) { + int yym, yyn, yystate, yychar, yynewerrflag; + YYParseState *yyerrctx = 0; + int reduce_posn; + +# if YYDEBUG + char *yys; + + if ((yys = getenv("YYDEBUG"))) { + yyn = *yys; + if (yyn >= '0' && yyn <= '9') + yydebug = yyn - '0'; + } + if (yydebug) { + fputs("btyacc[,]\n", + stderr); + } +# endif + + yyps = yyNewState(YYDEFSTACKSIZE); + yyps->save = 0; + yynerrs = 0; + yyps->errflag = 0; + yychar = (YYEMPTY); + + yyps->ssp = yyps->ss; + yyps->vsp = yyps->vs; + yyps->psp = yyps->ps; + *(yyps->ssp) = yystate = 0; + + + /* Main parsing loop */ + yyloop: + if ((yyn = yydefred[yystate])) { + goto yyreduce; + } + + /* Read one token */ + if (yychar < 0) { + yychar = yyLex1(YYLEX_PARAM); + if (yychar < 0) yychar = 0; +# if YYDEBUG + if (yydebug) { + yys = 0; + if (yychar <= YYMAXTOKEN) yys = yyname[yychar]; + if (!yys) yys = "illegal-symbol"; + fprintf(stderr, "btyacc[%3d,%2d%s]: read token %d (%s)", + yystate, yydepth, (yytrial ? ",trial" : ""), yychar, yys); +# ifdef YYDBPR + fputc('<', stderr); + YYDBPR(yylval); + fputc('>', stderr); +# endif + fputc('\n', stderr); + } +# endif + } + + /* Do we have a conflict? */ + yyn = yycindex[yystate]; + if (yyn != 0 && (yyn += yychar) >= 0 + && yyn <= YYTABLESIZE && yycheck[yyn] == yychar) { + int ctry; + + if (yypath) { + YYParseState *save; +# if YYDEBUG + if (yydebug) { + fprintf(stderr, "btyacc[%3d,%2d%s]: CONFLICT: following successful " + "trial parse\n", yystate, yydepth, (yytrial ? ",trial" :"")); + } +# endif + /* Switch to the next conflict context */ + save = yypath; + yypath = save->save; + ctry = save->ctry; + if (save->state != yystate) + goto yyabort; + yyFreeState(save); + + } else { + + /* Unresolved conflict - start/continue trial parse */ + YYParseState *save; +# if YYDEBUG + if (yydebug) { + fprintf(stderr, "btyacc[%3d,%2d%s]: CONFLICT. ", + yystate, yydepth, (yytrial ? ",trial" : "")); + if(yyps->save) + fputs("ALREADY in conflict, continuing trial parse.\n", stderr); + else + fputs("starting trial parse.\n", stderr); + } +# endif + save = yyNewState(yyps->ssp - yyps->ss); + save->save = yyps->save; + save->state = yystate; + save->errflag = yyps->errflag; + save->ssp = save->ss + (yyps->ssp - yyps->ss); + save->vsp = save->vs + (yyps->vsp - yyps->vs); + save->psp = save->ps + (yyps->psp - yyps->ps); + memcpy(save->ss, yyps->ss, (yyps->ssp - yyps->ss + 1)*sizeof(Yshort)); + yySCopy(save->vs, yyps->vs, (yyps->ssp - yyps->ss + 1)); + yyPCopy(save->ps, yyps->ps, (yyps->ssp - yyps->ss + 1)); + ctry = yytable[yyn]; + if (yyctable[ctry] == -1) { +# if YYDEBUG + if (yydebug && yychar >= 0) + fputs("btyacc[trial]: backtracking 1 token\n", stderr); +# endif + ctry++; + } + save->ctry = ctry; + if (yyps->save == 0) { + /* If this is a first conflict in the stack, start saving lexemes */ + if (!yylexemes) { +# ifdef __cplusplus + yylexemes = new Yshort[YYSTACKGROWTH]; + yylvals = new YYSTYPE[YYSTACKGROWTH]; + yylvlim = yylvals + YYSTACKGROWTH; + yylpsns = new YYPOSN[YYSTACKGROWTH]; + yylplim = yylpsns + YYSTACKGROWTH; +# else + yylexemes = (Yshort*)malloc((YYSTACKGROWTH) * sizeof(Yshort)); + yylvals = (YYSTYPE*)malloc((YYSTACKGROWTH) * sizeof(YYSTYPE)); + yylvlim = yylvals + YYSTACKGROWTH; + yylpsns = (YYPOSN*)malloc((YYSTACKGROWTH) * sizeof(YYPOSN)); + yylplim = yylpsns + YYSTACKGROWTH; +# endif + } + if (yylvp == yylve) { + yylvp = yylve = yylvals; + yylpp = yylpe = yylpsns; + yylexp = yylexemes; + if (yychar >= 0) { + *yylve++ = yylval; + *yylpe++ = yyposn; + *yylexp = yychar; + yychar = YYEMPTY; + } + } + } + if (yychar >= 0) { + yylvp--, yylpp--, yylexp--; + yychar = YYEMPTY; + } + save->lexeme = yylvp - yylvals; + yyps->save = save; + } + + if (yytable[yyn] == ctry) { +# if YYDEBUG + if (yydebug) + fprintf(stderr, "btyacc[%3d,%2d%s]: shifting to state %d\n", + yystate, yydepth, (yytrial ? ",trial" : ""), yyctable[ctry]); +# endif + if (yychar < 0) { + yylvp++; yylpp++; yylexp++; + } + yychar = YYEMPTY; + if (yyps->errflag > 0) --yyps->errflag; + yystate = yyctable[ctry]; + goto yyshift; + } else { + yyn = yyctable[ctry]; + goto yyreduce; + } + } /* End of code dealing with conflicts */ + + + /* Is action a shift? */ + yyn = yysindex[yystate]; + if (yyn != 0 && (yyn += yychar) >= 0 + && yyn <= YYTABLESIZE && yycheck[yyn] == yychar) { +# if YYDEBUG + if (yydebug) + fprintf(stderr, "btyacc[%3d,%2d%s]: shifting to state %d\n", + yystate, yydepth, (yytrial ? ",trial" : ""), yytable[yyn]); +# endif + yychar = YYEMPTY; + if (yyps->errflag > 0) --yyps->errflag; + yystate = yytable[yyn]; + + yyshift: + if (yyps->ssp >= yyps->ss + yyps->stacksize - 1) { + yyMoreStack(yyps); + } + *++(yyps->ssp) = yystate; + *++(yyps->vsp) = yylval; + *++(yyps->psp) = yyposn; + goto yyloop; + } + if ((yyn = yyrindex[yystate]) && + (yyn += yychar) >= 0 && + yyn <= YYTABLESIZE && + yycheck[yyn] == yychar) { + yyn = yytable[yyn]; + goto yyreduce; + } + + /* According to the tables, neither shift nor reduce is OK here - error! */ + if (yyps->errflag) goto yyinrecovery; + yynewerrflag = 1; + goto yyerrhandler; +yyerrlab: + yynewerrflag = 0; +yyerrhandler: + while (yyps->save) { + int ctry; + YYParseState *save = yyps->save; +# if YYDEBUG + if (yydebug) + fprintf(stderr, "btyacc[%3d,%2d%s]: ERROR, " + "CONFLICT BACKTRACKING to state %d, %d tokens\n", + yystate, yydepth, (yytrial ? ",trial" : ""), + yyps->save->state, yylvp - yylvals - yyps->save->lexeme); +# endif + /* Memorize most forward-looking error state in case + it's really an error. */ + if(yyerrctx==0 || yyerrctx->lexemessp - yyps->ss); + yyerrctx->save = yyps->save; + yyerrctx->state = yystate; + yyerrctx->errflag = yyps->errflag; + yyerrctx->ssp = yyerrctx->ss + (yyps->ssp - yyps->ss); + yyerrctx->vsp = yyerrctx->vs + (yyps->vsp - yyps->vs); + yyerrctx->psp = yyerrctx->ps + (yyps->psp - yyps->ps); + memcpy (yyerrctx->ss, yyps->ss, + (yyps->ssp - yyps->ss + 1) * sizeof(Yshort)); + yySCopy(yyerrctx->vs, yyps->vs, (yyps->ssp - yyps->ss + 1)); + yyPCopy(yyerrctx->ps, yyps->ps, (yyps->ssp - yyps->ss + 1)); + yyerrctx->lexeme = yylvp - yylvals; + } + yylvp = yylvals + save->lexeme; + yylpp = yylpsns + save->lexeme; + yylexp = yylexemes + save->lexeme; + yychar = YYEMPTY; + yyps->ssp = yyps->ss + (save->ssp - save->ss); + yyps->vsp = yyps->vs + (save->vsp - save->vs); + yyps->psp = yyps->ps + (save->psp - save->ps); + memcpy (yyps->ss, save->ss, (yyps->ssp - yyps->ss + 1) * sizeof(Yshort)); + yySCopy(yyps->vs, save->vs, yyps->vsp - yyps->vs + 1); + yyPCopy(yyps->ps, save->ps, yyps->psp - yyps->ps + 1); + ctry = ++save->ctry; + yystate = save->state; + /* We tried shift, try reduce now */ + if ((yyn = yyctable[ctry]) >= 0) { + goto yyreduce; + } + yyps->save = save->save; + yyFreeState(save); + + /* Nothing left on the stack -- error */ + if (!yyps->save) { +# if YYDEBUG + if (yydebug) { + fputs("btyacc[trial]: trial parse FAILED, entering ERROR mode\n", + stderr); + } +# endif + /* Restore state as it was in the most forward-advanced error */ + yylvp = yylvals + yyerrctx->lexeme; + yylpp = yylpsns + yyerrctx->lexeme; + yylexp = yylexemes + yyerrctx->lexeme; + yychar = yylexp[-1]; + yylval = yylvp[-1]; + yyposn = yylpp[-1]; + yyps->ssp = yyps->ss + (yyerrctx->ssp - yyerrctx->ss); + yyps->vsp = yyps->vs + (yyerrctx->vsp - yyerrctx->vs); + yyps->psp = yyps->ps + (yyerrctx->psp - yyerrctx->ps); + memcpy (yyps->ss, yyerrctx->ss, + (yyps->ssp - yyps->ss + 1) * sizeof(Yshort)); + yySCopy(yyps->vs, yyerrctx->vs, yyps->vsp - yyps->vs + 1); + yyPCopy(yyps->ps, yyerrctx->ps, yyps->psp - yyps->ps + 1); + yystate = yyerrctx->state; + yyFreeState(yyerrctx); + yyerrctx = 0; + } + yynewerrflag = 1; + } + if (yynewerrflag) { +# ifdef YYERROR_DETAILED + yyerror_detailed("parse error", yychar, yylval, yyposn); +# else + yyerror("parse error"); +# endif + } + ++yynerrs; + yyinrecovery: + if (yyps->errflag < 3) { + yyps->errflag = 3; + for (;;) { + if ((yyn = yysindex[*(yyps->ssp)]) + && (yyn += YYERRCODE) >= 0 + && yyn <= YYTABLESIZE + && yycheck[yyn] == YYERRCODE) { +# if YYDEBUG + if (yydebug) + fprintf(stderr, "btyacc[%3d,%2d%s]: ERROR recovery shifts to " + "state %d\n", + *(yyps->ssp), yydepth, (yytrial ? ",trial" : ""), + yytable[yyn]); +# endif + /* Use label yyerrlab, so that compiler does not warn */ + if(yyps->errflag != yyps->errflag) goto yyerrlab; + yystate = yytable[yyn]; + goto yyshift; + } else { +# if YYDEBUG + if (yydebug) + fprintf(stderr, + "btyacc[%3d,%2d%s]: ERROR recovery discards this state\n", + *(yyps->ssp), yydepth, (yytrial ? ",trial" : "")); +# endif + if (yyps->ssp <= yyps->ss) { + goto yyabort; + } + if(!yytrial) { + YYDELETEVAL(yyps->vsp[0],1); + YYDELETEPOSN(yyps->psp[0],1); + } + --(yyps->ssp); + --(yyps->vsp); + --(yyps->psp); + } + } + } else { + if (yychar == 0) goto yyabort; +# if YYDEBUG + if (yydebug) { + yys = 0; + if (yychar <= YYMAXTOKEN) yys = yyname[yychar]; + if (!yys) yys = "illegal-symbol"; + fprintf(stderr, "btyacc[%3d,%2d%s]: ERROR recovery discards token " + "%d (%s)\n", + yystate, yydepth, (yytrial ? ",trial" : ""), yychar, yys); + } +# endif + if(!yytrial) { + YYDELETEVAL(yylval,0); + YYDELETEPOSN(yyposn,0); + } + yychar = (YYEMPTY); + goto yyloop; + } + + /* Reduce the rule */ +yyreduce: + yym = yylen[yyn]; +# if YYDEBUG + if (yydebug) { + fprintf(stderr, "btyacc[%3d,%2d%s]: reducing by rule %d (%s)", + yystate, yydepth, (yytrial ? ",trial" : ""), yyn, yyrule[yyn]); +# ifdef YYDBPR + if (yym) { + int i; + fputc('<', stderr); + for (i=yym; i>0; i--) { + if (i!=yym) printf(", "); + YYDBPR((yyps->vsp)[1-i]); + } + fputc('>', stderr); + } +# endif + fputc('\n', stderr); + } +# endif + if (yyps->ssp + 1 - yym >= yyps->ss + yyps->stacksize) { + yyMoreStack(yyps); + } + +# ifdef _YACC_DEFAULT_ACTION_ + /* "$$ = NULL" default action */ + memset(&yyps->val, 0, sizeof(yyps->val)); +# else + /* RA: bison compatibility: default action is '$$ = $1;' */ + if (yym > 0) yyps->val = (yyps->vsp)[1 - yym]; +# endif + + /* Default reduced position is NULL -- no position at all. No + position will be assigned at trial time and if no position + handling is present */ + memset(&yyps->pos, 0, sizeof(yyps->pos)); + + reduce_posn = 1; + + switch (yyn) { + +%% trailer + + default: + break; + } + +# if YYDEBUG && defined(YYDBPR) + if (yydebug) { + fputs("btyacc[trial]: reduced, result is ", stderr); + YYDBPR(yyps->val); + fputc('\n', stderr); + } +# endif + + /* Perform user-defined position reduction */ +# ifdef YYREDUCEPOSNFUNC + if(!yytrial) { + YYCALLREDUCEPOSN(YYREDUCEPOSNFUNCARG); + } +# endif + + yyps->ssp -= yym; + yystate = *(yyps->ssp); + yyps->vsp -= yym; + yyps->psp -= yym; + + yym = yylhs[yyn]; + if (yystate == 0 && yym == 0) { +# if YYDEBUG + if (yydebug) { + fprintf(stderr, + "btyacc[ 0,%2d%s]: reduced, shifting to final state %d\n", + yydepth, (yytrial ? ",trial" : ""), YYFINAL); + } +# endif + yystate = YYFINAL; + *++(yyps->ssp) = YYFINAL; + *++(yyps->vsp) = yyps->val; + yyretlval = yyps->val; /* return value of root non-terminal to yylval */ + *++(yyps->psp) = yyps->pos; + yyretposn = yyps->pos; /* return value of root position to yyposn */ + if (yychar < 0) { + if ((yychar = yyLex1(YYLEX_PARAM)) < 0) { + yychar = 0; + } +# if YYDEBUG + if (yydebug) { + yys = 0; + if (yychar <= YYMAXTOKEN) yys = yyname[yychar]; + if (!yys) yys = "illegal-symbol"; + fprintf(stderr, "btyacc[%3d,%2d%s]: read %d (%s)\n", + YYFINAL, yydepth, (yytrial ? ",trial" : ""), yychar, yys); + } +# endif + } + if (yychar == 0) goto yyaccept; + goto yyloop; + } + + if ((yyn = yygindex[yym]) && (yyn += yystate) >= 0 && + yyn <= YYTABLESIZE && yycheck[yyn] == yystate) { + yystate = yytable[yyn]; + } else { + yystate = yydgoto[yym]; + } +# if YYDEBUG + if (yydebug) + fprintf(stderr, "btyacc[%3d,%2d%s]: reduced, shifting to state %d\n", + *(yyps->ssp), yydepth, (yytrial ? ",trial" : ""), yystate); +# endif + if (yyps->ssp >= yyps->ss + yyps->stacksize - 1) { + yyMoreStack(yyps); + } + *++(yyps->ssp) = yystate; + *++(yyps->vsp) = yyps->val; + *++(yyps->psp) = yyps->pos; + goto yyloop; + + + /* Reduction declares that this path is valid. + Set yypath and do a full parse */ +yyvalid: + if (yypath) { + goto yyabort; + } + while (yyps->save) { + YYParseState *save = yyps->save; + yyps->save = save->save; + save->save = yypath; + yypath = save; + } +# if YYDEBUG + if (yydebug) + fprintf(stderr, "btyacc[%3d,%2d%s]: CONFLICT trial successful, " + "backtracking to state %d, %d tokens\n", + yystate, yydepth, (yytrial ? ",trial" : ""), + yypath->state, yylvp - yylvals - yypath->lexeme); +# endif + if(yyerrctx) { + yyFreeState(yyerrctx); yyerrctx = 0; + } + yychar = YYEMPTY; + yyps->ssp = yyps->ss + (yypath->ssp - yypath->ss); + yyps->vsp = yyps->vs + (yypath->vsp - yypath->vs); + yyps->psp = yyps->ps + (yypath->psp - yypath->ps); + memcpy (yyps->ss, yypath->ss, (yyps->ssp - yyps->ss + 1) * sizeof(Yshort)); + yySCopy(yyps->vs, yypath->vs, yyps->vsp - yyps->vs + 1); + yyPCopy(yyps->ps, yypath->ps, yyps->psp - yyps->ps + 1); + yylvp = yylvals + yypath->lexeme; + yylpp = yylpsns + yypath->lexeme; + yylexp = yylexemes + yypath->lexeme; + yystate = yypath->state; + goto yyloop; + + +yyabort: + { + YYSTYPE *pv; + YYPOSN *pp; + + if(yyerrctx) { + yyFreeState(yyerrctx); yyerrctx = 0; + } + + for(pv=yyps->vs; pvvsp; pv++) { + YYDELETEVAL(*pv,2); + } + + for(pp=yyps->ps; pppsp; pp++) { + YYDELETEPOSN(*pp,2); + } + + while (yyps) { + YYParseState *save = yyps; + yyps = save->save; + yyFreeState(save); + } + while (yypath) { + YYParseState *save = yypath; + yypath = save->save; + yyFreeState(save); + } + return (1); + } + +yyaccept: + if (yyps->save) goto yyvalid; + if(yyerrctx) { + yyFreeState(yyerrctx); yyerrctx = 0; + } + while (yyps) { + YYParseState *save = yyps; + yyps = save->save; + yyFreeState(save); + } + while (yypath) { + YYParseState *save = yypath; + yypath = save->save; + yyFreeState(save); + } + return (0); +} + + +/* Call yylex() unless the token has already been read. */ +static int yyLex1(yyscan_t scanner) { + if(yylvp < yylve) { + /* we're currently re-reading tokens */ + yylval = *yylvp++; + yyposn = *yylpp++; + return *yylexp++; + } else if(yyps->save) { + /* in trial mode; save scanner results for future parse attempts */ + if(yylvp == yylvlim) + yyExpand(); + *yylexp = yylex(&yylval, scanner); + *yylvp++ = yylval; + yylve++; + *yylpp++ = yyposn; + yylpe++; + return *yylexp++; + } else { /* normal operation, no conflict encountered */ + return yylex(&yylval, scanner); + } +} + +/* Enlarge lexical value queue */ +static int yyExpand() { + int p = yylvp - yylvals; + int s = yylvlim - yylvals; + s += YYSTACKGROWTH; + { + Yshort *tl = yylexemes; + YYSTYPE *tv = yylvals; + YYPOSN *tp = yylpsns; +# ifdef __cplusplus + yylvals = new YYSTYPE[s]; + yylpsns = new YYPOSN[s]; + yylexemes = new Yshort[s]; + memcpy(yylexemes, tl, (s-YYSTACKGROWTH)*sizeof(Yshort)); + yySCopy(yylvals, tv, s-YYSTACKGROWTH); + yyPCopy(yylpsns, tp, s-YYSTACKGROWTH); + delete[] tl; + delete[] tv; + delete[] tp; +# else + yylvals = (YYSTYPE*)malloc(s * sizeof(YYSTYPE)); + yylpsns = (YYPOSN*)malloc(s * sizeof(YYPOSN)); + yylexemes = (Yshort*)malloc(s * sizeof(Yshort)); + memcpy(yylexemes, tl, (s - YYSTACKGROWTH)*sizeof(Yshort)); + yySCopy(yylvals, tv, s - YYSTACKGROWTH); + yyPCopy(yylpsns, tp, s - YYSTACKGROWTH); + free(tl); + free(tv); + free(tp); +# endif + } + yylvp = yylve = yylvals + p; + yylvlim = yylvals + s; + yylpp = yylpe = yylpsns + p; + yylplim = yylpsns + s; + yylexp = yylexemes + p; + return 0; +} + +static void yySCopy(YYSTYPE *to, YYSTYPE *from, int size) { + int i; + for (i = size-1; i >= 0; i--) { + to[i] = from[i]; + } +} + +static void yyPCopy(YYPOSN *to, YYPOSN *from, int size) { + int i; + for (i = size-1; i >= 0; i--) { + to[i] = from[i]; + } +} + +static void yyMoreStack(YYParseState *yyps) { + int p = yyps->ssp - yyps->ss; + Yshort *tss = yyps->ss; + YYSTYPE *tvs = yyps->vs; + YYPOSN *tps = yyps->ps; + int newSize = yyps->stacksize + YYSTACKGROWTH; + +# ifdef __cplusplus + yyps->ss = new Yshort [newSize]; + yyps->vs = new YYSTYPE[newSize]; + yyps->ps = new YYPOSN [newSize]; + memcpy(yyps->ss, tss, yyps->stacksize * sizeof(Yshort)); + yySCopy(yyps->vs, tvs, yyps->stacksize); + yyPCopy(yyps->ps, tps, yyps->stacksize); + yyps->stacksize += YYSTACKGROWTH; + delete[] tss; + delete[] tvs; + delete[] tps; +# else + yyps->ss = (Yshort*) malloc(newSize * sizeof(Yshort)); + yyps->vs = (YYSTYPE*)malloc(newSize * sizeof(YYSTYPE)); + yyps->ps = (YYPOSN*) malloc(newSize * sizeof(YYPOSN)); + memcpy(yyps->ss, tss, yyps->stacksize * sizeof(Yshort)); + yySCopy(yyps->vs, tvs, yyps->stacksize); + yyPCopy(yyps->ps, tps, yyps->stacksize); + yyps->stacksize += YYSTACKGROWTH; + free(tss); + free(tvs); + free(tps); +# endif + yyps->ssp = yyps->ss + p; + yyps->vsp = yyps->vs + p; + yyps->psp = yyps->ps + p; +# if YYDEBUG + if (yydebug) + fprintf(stderr, "btyacc: stack size increased to %d\n", yyps->stacksize); +# endif +} + + +#ifdef __cplusplus + +static YYParseState *yyNewState(int size) { + YYParseState *p = new YYParseState; + p->stacksize = size+4; + p->ss = new Yshort [size + 4]; + p->vs = new YYSTYPE[size + 4]; + p->ps = new YYPOSN [size + 4]; + memset(&p->vs[0], 0, (size+4)*sizeof(YYSTYPE)); + memset(&p->ps[0], 0, (size+4)*sizeof(YYPOSN)); + return p; +} + +static void yyFreeState(YYParseState *p) { + delete[] p->ss; + delete[] p->vs; + delete[] p->ps; + delete p; +} + +#else /* not __cplusplus */ + +static YYParseState *yyNewState(int size) { + YYParseState *p = (YYParseState*)malloc(sizeof(YYParseState)); + + p->stacksize = size+4; + p->ss = (Yshort*) malloc((size + 4) * sizeof(Yshort)); + p->vs = (YYSTYPE*)malloc((size + 4) * sizeof(YYSTYPE)); + p->ps = (YYPOSN*) malloc((size + 4) * sizeof(YYPOSN)); + memset(&p->vs[0], 0, (size+4)*sizeof(YYSTYPE)); + memset(&p->ps[0], 0, (size+4)*sizeof(YYPOSN)); + return p; +} + +static void yyFreeState(YYParseState *p) { + free(p->ss); + free(p->vs); + free(p->ps); + free(p); +} + +#endif -- cgit v1.1