
# line 3 "expr.ym"
/*
    expr.ym

    This file defines the grammar for parsing expressions.  To fully understand
    this code you will need to understand yacc.  The basic idea is that
    the parse tree is built from the bottom up as larger and larger
    sub-expressions are recognized by the grammar.  The nodes of the tree
    are created by the alloc* functions at the end of the file.  These
    functions are called by the rules of the grammar as various types of
    sub-expressions are recognized.  The one entry point to this file,
    _EXPParseExpression() encapsulates all the lex and yacc glue necessary
    to parse an expression.
*/

#import <stdlib.h>
#import <string.h>
#import <stdio.h>
#import "exprDefs.h"

static Term *allocBinaryOpTerm(char op, Term *t1, Term *t2);
static Term *allocVarTerm(char *name);
static Term *allocConstantTerm(float value, BOOL isInt);
static Term *allocFuncTerm(char *name, TermList *args);
static void addAllocedTerm(Term *t);
static void yyerror(char *s);
extern yylex(), yyparse();

/* globals used to build up results of the parse */
static NXHashTable *ValidFuncTerms;	/* list of funcs we allow */
static NXHashTable *VarTerms;		/* vars found in expression */
static Term *CompleteExpr;		/* top of parse tree */
static BOOL ParseError;			/* was there a parse error? */
static Term **TermsAlloced;		/* terms alloced during parse */
static int NumTermsAlloced;		/* #terms alloced during parse */
static NXZone *ParseZone;		/* zone to allocate parse results in */

/* initial size of TermsAlloced ptr array */
#define STACK_TERMS	200


# line 46 "expr.ym"
typedef union  {
    Term *node;
    TermList *list;
    float real;
    int integer;
    char *string;
    char character;
} YYSTYPE;
# define IDENTIFIER 257
# define NUMBER 258
# define INTEGER 259
# define BADCHAR 260
# define UMINUS 261
#define yyclearin yychar = -1
#define yyerrok yyerrflag = 0
extern int yychar;
extern short yyerrflag;
#ifndef YYMAXDEPTH
#define YYMAXDEPTH 150
#endif
YYSTYPE yylval, yyval;
# define YYERRCODE 256

# line 121 "expr.ym"


/*
 * The main entry point into this file.  This routine sets up some globals
 * and calls yyparse(), a routine generated by yacc, to do the actual parse.
 * If the parse succeeds, the results are found in the globals, and are
 * returned to the caller.
 *
 * Note because of the globals this files uses to communicate between this
 * routine and the parsing guts, this is not thread safe (the yacc and lex
 * internals probably aren't thread safe either).  One easy solution to this
 * would be to put a mutex lock around the whole parse.
 *
 * If there is a parse error, since the tree is built bottom up it can be
 * difficult to free the data structures allocated before the error is
 * detected.  To solve this problem we keep a global buffer of pointers to
 * the parse tree nodes as they are allocated.  In the event of an error
 * we can then easily free them all regardless of the state of the parse tree.
 * Its also very important to empty the varTerms hash table in this case, so
 * it is not returned full of freed nodes.
 */
BOOL _EXPParseExpression(const char *text, NXHashTable *validTerms, Term **parseTree, NXHashTable *varTerms, NXZone *zone)
{
    int parseRet;
    Term *termsAllocedStackSpace[STACK_TERMS];
    int i;

    CompleteExpr = NULL;	/* set globals to prepare for parsing */
    VarTerms = varTerms;
    ParseError = NO;
    ValidFuncTerms = validTerms;
    TermsAlloced = termsAllocedStackSpace;
    NumTermsAlloced = 0;
    ParseZone = zone;
    _EXPPrepareToScan(text);	/* sets up lex to scan the string */
    parseRet = yyparse();
    if (parseRet == 1 || ParseError) {
	for (i = 0; i < NumTermsAlloced; i++)
	    _EXPFreeTerm(NULL, TermsAlloced[i]);
	*parseTree = NULL;
	NXEmptyHashTable(varTerms);
    } else
	*parseTree = CompleteExpr;
    if (NumTermsAlloced > STACK_TERMS)
	NXZoneFree(NXDefaultMallocZone(), TermsAlloced);
    return !(parseRet == 1 || ParseError);
}

/* allocates a new binary operator term */
static Term *allocBinaryOpTerm(char op, Term *t1, Term *t2)
{
    Term *newTerm;

    newTerm = _EXPAllocTerm(ParseZone, binOpTerm, 2, t1, t2);
    newTerm->data.binOp.op = op;
    addAllocedTerm(newTerm);
    return newTerm;
}

/*
 * Allocates a new variable term.  We first check to see if the variable has
 * already been seen in this parse, and if so return the existing variable
 * term.  Otherwise we go ahead and allocate a new one.
 */
static Term *allocVarTerm(char *name)
{
    Term *newTerm;
    Term key;

    key.tag = varTerm;
    key.data.var.name = name;
    newTerm = NXHashGet(VarTerms, &key);
    if (!newTerm) {
	newTerm = _EXPAllocTerm(ParseZone, varTerm, 0);
	newTerm->data.var.name = NXCopyStringBufferFromZone(name, ParseZone);
	NXHashInsert(VarTerms, newTerm);
	addAllocedTerm(newTerm);
    }
    free(name);
    return newTerm;
}

/* allocates a new constant term */
static Term *allocConstantTerm(float value, BOOL isInt)
{
    Term *newTerm;

    newTerm = _EXPAllocTerm(ParseZone, constantTerm, 0);
    newTerm->data.constant.val = value;
    newTerm->data.constant.isInt = isInt;
    addAllocedTerm(newTerm);
    return newTerm;
}

/*
 * Allocates a new function term.  It looks up the function by name to see
 * if it is one we know how to parse.  If so, it makes sure the number of
 * arguments being passed is correct for the function.  If the function is
 * unknown or the number of arguments is wrong, we record the fact that
 * we've had a parse error in a global.
 */
static Term *allocFuncTerm(char *name, TermList *args)
{
    Term *newTerm;
    Function *func;
    Function key;
    TermList noArgs;

    if (!args) {
	args = &noArgs;
	args->num = 0;
    }
    key.name = (char *)name;
    func = NXHashGet(ValidFuncTerms, &key);
    newTerm = _EXPAllocTerm(ParseZone, funcTerm, args->num);
    bcopy(args->terms, newTerm->subterms, args->num * sizeof(Term *));
    newTerm->data.func.type = func;
    if (!func || args->num < func->minArgs ||
		(args->num > func->maxArgs && func->maxArgs != -1))
	ParseError = YES;
    NXZoneFree(NXDefaultMallocZone(), args);
    free(name);
    addAllocedTerm(newTerm);
    return newTerm;
}

/*
 * Adds a term to the list of terms that we have allocated during this parse.
 * This routine allocates more space for Term pointers if necessary.  It knows
 * not to free the initial buffer of these pointers, since that buffer is
 * allocated on the stack by _EXPParseExpression().
 */
static void addAllocedTerm(Term *t)
{
    Term **newSpace;

    if (!(NumTermsAlloced % STACK_TERMS) && NumTermsAlloced > 0) {
	newSpace = NXZoneMalloc(NXDefaultMallocZone(),
			(NumTermsAlloced + STACK_TERMS) * sizeof(Term *));
	bcopy(TermsAlloced, newSpace, NumTermsAlloced * sizeof(Term *));
	if (NumTermsAlloced > STACK_TERMS)
	    NXZoneFree(NXDefaultMallocZone(), TermsAlloced);
	TermsAlloced = newSpace;
    }
    TermsAlloced[NumTermsAlloced++] = t;
}

/* a piece of yacc glue called when there is a parse error */
static void yyerror(char *s)
{
}
short yyexca[] ={
-1, 1,
	0, -1,
	-2, 0,
	};
# define YYNPROD 18
# define YYLAST 223
short yyact[]={

   3,  25,  14,   3,  17,   4,  13,  26,   4,   5,
  24,  11,   9,  13,  10,  13,  12,   1,  11,   9,
  11,  10,   0,  12,  28,  12,   2,  29,   0,   0,
  15,  16,   0,   0,   0,   0,  18,  19,  20,  21,
  22,  23,   0,   0,  27,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,  30,   0,   0,   0,
   0,   0,   0,  14,   0,   0,   0,   0,   0,   0,
  14,   0,  14,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
   0,   0,   0,   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,   7,   8,
   6,   7,   8 };
short yypact[]={

 -37,-1000, -24, -37, -37,-1000, -36,-1000,-1000, -37,
 -37, -37, -37, -37, -37, -31, -92, -40, -22, -22,
 -92, -92, -92, -92,-1000,-1000, -17, -24,-1000, -37,
 -24 };
short yypgo[]={

   0,  17,  26,   9,   7 };
short yyr1[]={

   0,   1,   2,   2,   2,   2,   2,   2,   2,   2,
   2,   2,   2,   2,   3,   3,   4,   4 };
short yyr2[]={

   0,   1,   3,   3,   3,   3,   3,   3,   3,   2,
   1,   1,   1,   1,   3,   4,   1,   3 };
short yychk[]={

-1000,  -1,  -2,  40,  45,  -3, 257, 258, 259,  43,
  45,  42,  47,  37,  94,  -2,  -2,  40,  -2,  -2,
  -2,  -2,  -2,  -2,  41,  41,  -4,  -2,  41,  44,
  -2 };
short yydef[]={

   0,  -2,   1,   0,   0,  10,  11,  12,  13,   0,
   0,   0,   0,   0,   0,   0,   9,   0,   3,   4,
   5,   6,   7,   8,   2,  14,   0,  16,  15,   0,
  17 };
# line 1 "/usr/lib/yaccpar"
#ifndef lint
static char yaccpar_sccsid[] = "@(#)yaccpar	4.1	(Berkeley)	2/11/83";
#endif not lint

# define YYFLAG -1000
# define YYERROR goto yyerrlab
# define YYACCEPT return(0)
# define YYABORT return(1)

/*	parser for yacc output	*/

#ifdef YYDEBUG
int yydebug = 0; /* 1 for debugging */
#endif
YYSTYPE yyv[YYMAXDEPTH]; /* where the values are stored */
int yychar = -1; /* current input token number */
int yynerrs = 0;  /* number of errors */
short yyerrflag = 0;  /* error recovery flag */

yyparse() {

	short yys[YYMAXDEPTH];
	short yyj, yym;
	register YYSTYPE *yypvt;
	register short yystate, *yyps, yyn;
	register YYSTYPE *yypv;
	register short *yyxi;

	yystate = 0;
	yychar = -1;
	yynerrs = 0;
	yyerrflag = 0;
	yyps= &yys[-1];
	yypv= &yyv[-1];

 yystack:    /* put a state and value onto the stack */

#ifdef YYDEBUG
	if( yydebug  ) printf( "state %d, char 0%o\n", yystate, yychar );
#endif
		if( ++yyps>= &yys[YYMAXDEPTH] ) { yyerror( "yacc stack overflow" ); return(1); }
		*yyps = yystate;
		++yypv;
		*yypv = yyval;

 yynewstate:

	yyn = yypact[yystate];

	if( yyn<= YYFLAG ) goto yydefault; /* simple state */

	if( yychar<0 ) if( (yychar=yylex())<0 ) yychar=0;
	if( (yyn += yychar)<0 || yyn >= YYLAST ) goto yydefault;

	if( yychk[ yyn=yyact[ yyn ] ] == yychar ){ /* valid shift */
		yychar = -1;
		yyval = yylval;
		yystate = yyn;
		if( yyerrflag > 0 ) --yyerrflag;
		goto yystack;
		}

 yydefault:
	/* default state action */

	if( (yyn=yydef[yystate]) == -2 ) {
		if( yychar<0 ) if( (yychar=yylex())<0 ) yychar = 0;
		/* look through exception table */

		for( yyxi=yyexca; (*yyxi!= (-1)) || (yyxi[1]!=yystate) ; yyxi += 2 ) ; /* VOID */

		while( *(yyxi+=2) >= 0 ){
			if( *yyxi == yychar ) break;
			}
		if( (yyn = yyxi[1]) < 0 ) return(0);   /* accept */
		}

	if( yyn == 0 ){ /* error */
		/* error ... attempt to resume parsing */

		switch( yyerrflag ){

		case 0:   /* brand new error */

			yyerror( "syntax error" );
		yyerrlab:
			++yynerrs;

		case 1:
		case 2: /* incompletely recovered error ... try again */

			yyerrflag = 3;

			/* find a state where "error" is a legal shift action */

			while ( yyps >= yys ) {
			   yyn = yypact[*yyps] + YYERRCODE;
			   if( yyn>= 0 && yyn < YYLAST && yychk[yyact[yyn]] == YYERRCODE ){
			      yystate = yyact[yyn];  /* simulate a shift of "error" */
			      goto yystack;
			      }
			   yyn = yypact[*yyps];

			   /* the current yyps has no shift onn "error", pop stack */

#ifdef YYDEBUG
			   if( yydebug ) printf( "error recovery pops state %d, uncovers %d\n", *yyps, yyps[-1] );
#endif
			   --yyps;
			   --yypv;
			   }

			/* there is no state on the stack with an error shift ... abort */

	yyabort:
			return(1);


		case 3:  /* no shift yet; clobber input char */

#ifdef YYDEBUG
			if( yydebug ) printf( "error recovery discards char %d\n", yychar );
#endif

			if( yychar == 0 ) goto yyabort; /* don't discard EOF, quit */
			yychar = -1;
			goto yynewstate;   /* try again in the same state */

			}

		}

	/* reduction by production yyn */

#ifdef YYDEBUG
		if( yydebug ) printf("reduce %d\n",yyn);
#endif
		yyps -= yyr2[yyn];
		yypvt = yypv;
		yypv -= yyr2[yyn];
		yyval = yypv[1];
		yym=yyn;
			/* consult goto table to find next state */
		yyn = yyr1[yyn];
		yyj = yypgo[yyn] + *yyps + 1;
		if( yyj>=YYLAST || yychk[ yystate = yyact[yyj] ] != -yyn ) yystate = yyact[yypgo[yyn]];
		switch(yym){
			
case 1:
# line 72 "expr.ym"
{ CompleteExpr = yyval.node; } break;
case 2:
# line 76 "expr.ym"
{ yyval.node = yypvt[-1].node; } break;
case 3:
# line 78 "expr.ym"
{ yyval.node = allocBinaryOpTerm('+', yypvt[-2].node, yypvt[-0].node); } break;
case 4:
# line 80 "expr.ym"
{ yyval.node = allocBinaryOpTerm('-', yypvt[-2].node, yypvt[-0].node); } break;
case 5:
# line 82 "expr.ym"
{ yyval.node = allocBinaryOpTerm('*', yypvt[-2].node, yypvt[-0].node); } break;
case 6:
# line 84 "expr.ym"
{ yyval.node = allocBinaryOpTerm('/', yypvt[-2].node, yypvt[-0].node); } break;
case 7:
# line 86 "expr.ym"
{ yyval.node = allocBinaryOpTerm('%', yypvt[-2].node, yypvt[-0].node); } break;
case 8:
# line 88 "expr.ym"
{ yyval.node = allocBinaryOpTerm('^', yypvt[-2].node, yypvt[-0].node); } break;
case 9:
# line 90 "expr.ym"
{ yyval.node = _EXPAllocTerm(ParseZone, binOpTerm, 1, yypvt[-0].node); 
		  yyval.node->data.binOp.op = '-';
		} break;
case 11:
# line 95 "expr.ym"
{ yyval.node = allocVarTerm(yypvt[-0].string); } break;
case 12:
# line 97 "expr.ym"
{ yyval.node = allocConstantTerm(yypvt[-0].real, NO); } break;
case 13:
# line 99 "expr.ym"
{ yyval.node = allocConstantTerm(yypvt[-0].integer, YES); } break;
case 14:
# line 103 "expr.ym"
{ yyval.node = allocFuncTerm(yypvt[-2].string, NULL); } break;
case 15:
# line 105 "expr.ym"
{ yyval.node = allocFuncTerm(yypvt[-3].string, yypvt[-1].list); } break;
case 16:
# line 109 "expr.ym"
{ yyval.list = NXZoneMalloc(NXDefaultMallocZone(), sizeof(TermList));
		  yyval.list->terms[0] = yypvt[-0].node;
		  yyval.list->num = 1;
		} break;
case 17:
# line 114 "expr.ym"
{ yyval.list = NXZoneRealloc(NXDefaultMallocZone(), yypvt[-2].list,
				sizeof(TermList) + yypvt[-2].list->num*sizeof(Term *));
		  yyval.list->terms[yyval.list->num] = yypvt[-0].node;
		  yyval.list->num++;
		} break;
# line 148 "/usr/lib/yaccpar"

		}
		goto yystack;  /* stack new state and value */

	}
