Add a simple flex + btyacc stub.

Will be fleshed out soon with LSL grammer.

10 files changed, 1308 insertions, 1 deletions

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 <stdlib.h>
+ 
+/**
+ * @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(&param->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 <value> TOKEN_NUMBER
+
+%type <expression> 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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+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[<current state>,<nr of symbols on state stack>]\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->lexeme<yylvp-yylvals) {
+      /* Free old saved error context state */
+      if(yyerrctx) yyFreeState(yyerrctx);
+      /* Create and fill out new saved error context state */
+      yyerrctx = yyNewState(yyps->ssp - 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; pv<yyps->vsp; pv++) {
+      YYDELETEVAL(*pv,2);
+    }
+
+    for(pp=yyps->ps; pp<yyps->psp; 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