Module: qeval.cpp

Flat functions
 

isdigitstatic short isdigit(char c)
isoctdigitstatic short isoctdigit(char c)
ishexdigitstatic short ishexdigit(char c)
isbindigitstatic short isbindigit(char c)
hextointstatic short hextoint(char c) /* From ASCII to int */
calchexstatic long calchex(void) /* htol */
calcbinstatic long calcbin(void) /* binary */
calcdecstatic long calcdec(void) /* Calc decimal */
calcoctstatic long calcoct(void) /* Calc octal */
lexanstatic short lexan(void)

/* Lexical analyser; removes white spaces, tokenizes */

emitstatic void emit(short t) /* Push result on postfix stack */
emittxtstatic emittxt(s1,s2,s3,s4,s5) /* Emit tekst */
exprstatic void expr(void);

static void unaryop(void);

matchstatic void match(short t)
numstatic void num(void)

/*
Evaluates constant
*/

unaryopstatic void unaryop(void)
factorstatic void factor(void)
termstatic void term(void)
andopstatic void andop(void)
oropstatic void orop(void)
exprstatic void expr(void)
parsestatic void parse(void)
pushstatic void push(long val)
popstatic long pop(void)
topstatic long top(void)
evalstatic long eval(void)

/* Evaluate created postfix array */

Evalint Eval(cstring s) /* Expression evaluator */


/*
 * Expression evaluator (infix->postfix->value)
 * Using the following grammar (from Compilers principles, techniques....)

 Priorities:  |		(lowest)
              &
              +,-
              *,/	(highest)

 start       -> expr
              | 
 expr        -> orop moreorops
 moreorops   -> | orop moreorops
              | 
 orop        -> andop moreandops
 moreandops  -> & andop moreandops
              | ^ andop moreandops ; priority of ^ right?
              | 
 andop       -> term moreterms
 moreterms   -> + term moreterms
              | - term moreterms
              | 
 term        -> factor morefactors
 morefactors -> * factor morefactors (SGI: x too)
              | / factor morefactors
              | % factor morefactors
              | 
 factor      -> (expr)                     (brackets are primary operators)
              | id
              | num
 id          ->                           (no default id's defined yet)
 num         -> $ hexnum
              | # binnum
              | 0 octnum
              | 0x hexnum
              | unaryop num
              | 1-9                        (decimal number)
              |                           (actually an error)
 unaryop     -> ~ num                      (one's complement)
              | - num                      (unary negation)
              | + num                      (unary positive)

 * 29-10-89: Created! Handles decimal, hex, binary (#), +,-,/,*. Never gives an
 * error, so it works on all expressions, but faulty on faulty expressions.
 * Protected against division by zero...
 * 27-02-90: Now numbers may be prefixed by unary operators. Version before
 * this said that -5==0! Also &,| built in with priorities like in C. Slight
 * change in handling lookahead.
 * 06-02-91: Expanded (because of Arp which uses $) to handle '$' as well as
 * '0x' and octal reps (033 etc.). Fixed bug when dealing with large numbers
 * (e.g. 300000/12 went wrong).
 * 26-01-96: ASSERTed, cut back on static data (40 instead of 256 tokens).
 * Added %, ^ (not too sure about the ^ priority, though!)
 * 09-10-98: SGI.
 * 22-09-99: Finally! Unary minus implemented.
 * BUGS:
 * - ^ priority may not match C.
 * (C) MG/Dave Mentos/RVG
 */

#include <qlib/debug.h>
DEBUG_ENABLE

#define DONE		256		/* End of Expression */
#define T_CONST		257		/* Token types */
#define T_UNARYMINUS	258		// -(4+3) for example
#define T_XOR		259		// ~10 (bitwise invert)

#define MAX_TOKEN	40		// Max. expression complexity

struct Token { short token; long val; };

/*****************************
* INFIX TO POSTFIX CONVERTER *
*****************************/
static struct Token dest[MAX_TOKEN];
//static char  *src,srcindex,destindex;
static cstring src;
static char  srcindex,destindex;
static short lookahead;
static long  tokenval;

/**********
* COMMONS *
**********/
static short isdigit(char c)
{ if(c>='0'&&c<='9')return 1; return 0; }
static short isoctdigit(char c)
{ if(c>='0'&&c<='7')return 1; return 0; }
static short ishexdigit(char c)
{ if((c>='0'&&c<='9')||(c>='A'&&c<='F')||(c>='a'&&c<='f'))return 1; return 0; }
static short isbindigit(char c)
{ if(c=='0'||c=='1')return 1; return 0; }
static short hextoint(char c)		/* From ASCII to int */
{ if(c>='0'&&c<='9')return (short)(c-'0');
  if(c>='A'&&c<='F')return (short)(c-'A'+10);
  if(c>='a'&&c<='f')return (short)(c-'a'+10);
  return 0;
}
static long calchex(void)	/* htol */
{ long val=0;
  while(ishexdigit(src[srcindex]))
  { val=val*16+hextoint(src[srcindex]); srcindex++; }
  return val;
}
static long calcbin(void)		/* binary */
{ long val=0;
  while(isbindigit(src[srcindex])){ val=val*2+src[srcindex]-'0'; srcindex++; }
  return val;
}
static long calcdec(void)	/* Calc decimal */
{ long val=0;
  while(isdigit(src[srcindex])){ val=val*10+src[srcindex]-'0'; srcindex++; }
  return val;
}
static long calcoct(void)	/* Calc octal */
{ long val=0;
  while(isoctdigit(src[srcindex]))
  { val=val*8+src[srcindex]-'0'; srcindex++; }
  return val;
}

/*******************
* LEXICAL ANALYSER *
*******************/
static short lexan(void)
/* Lexical analyser; removes white spaces, tokenizes */
{ char c;
 fetch:
  srcindex++;
  if(srcindex==strlen(src))return DONE;
  c=src[srcindex];
  if(c==' ')goto fetch;
  return (short)c;
}

/**********
* EMITTER *
**********/
static void emit(short t)	/* Push result on postfix stack */
{
//qdbg("emit(%d, %c) tokenval=%d\n",t,t,tokenval);
  dest[destindex].token=t;
  if(t==T_CONST)dest[destindex].val=tokenval;
  else          dest[destindex].val=0;
  destindex++;
}
#ifdef NOTDEF
static emittxt(s1,s2,s3,s4,s5)	/* Emit tekst */
{ printf(s1,s2,s3,s4,s5); printf("\n"); }
#endif

/*********
* PARSER *
*********/
static void expr(void);
static void unaryop(void);

static void match(short t)
{ if(lookahead==t)lookahead=lexan();
  else lookahead=DONE;		/* Syntax error */
}

static void num(void)
/*
   Evaluates constant
*/
{
//qdbg("num\n");
  switch(lookahead)
  { case '$':
      match('$'); tokenval=calchex(); emit(T_CONST); return;
    case '0':
      match('0');
      switch(lookahead)
      { case 'x':
        case 'X':
          match(lookahead); tokenval=calchex(); emit(T_CONST); return;
        default:
          tokenval=calcoct(); emit(T_CONST); return;
      }
    case '#':
      match('#'); tokenval=calcbin(); emit(T_CONST); return;
    case '1': case '2': case '3': case '4': case '5':
    case '6': case '7': case '8': case '9':
      tokenval=calcdec(); emit(T_CONST); return;
    default : unaryop(); return;
  }
}
static void unaryop(void)
{
//qdbg("unaryop: lookahead=%c\n",lookahead);
  switch(lookahead)
  { case '~': match(lookahead); expr(); emit(T_XOR); break;
    case '-': match(lookahead); expr(); emit(T_UNARYMINUS); break;
    case '+': match(lookahead); expr(); break;
    default : break;
  }
}
static void factor(void)
{
//qdbg("factor\n");
  switch(lookahead)
  { case '(': match('('); expr(); match(')'); break;
    default : num(); if(srcindex>0)srcindex--;
//qdbg("Factor: lookahead=%d\n",lookahead);
              match(lookahead); break;
  }
}
static void term(void)
{ short t;
//qdbg("term\n");
  factor();
  while(1)
    switch(lookahead)
    { case '*':
      case 'x': t=lookahead; match(t); factor(); emit('*'); break;
      case '/': t=lookahead; match(t); factor(); emit(t); break;
      case '%': t=lookahead; match(t); factor(); emit(t); break;
      default : return;
    }
}
static void andop(void)
{ short t;
//qdbg("andop\n");
  term();
  while(1)
    switch(lookahead)
    { case '+': t=lookahead; match(t); term(); emit(t); break;
      case '-': t=lookahead; match(t); term(); emit(t); break;
      default : return;
    }
}
static void orop(void)
{ short t;
  andop();
  while(1)
    switch(lookahead)
    { case '&': t=lookahead; match(t); andop(); emit(t); break;
      case '^': t=lookahead; match(t); andop(); emit(t); break;
      default : return;
    }
//qdbg("andop RET\n");
}
static void expr(void)
{ short t;
  orop();
  while(1)
    switch(lookahead)
    { case '|': t=lookahead; match(t); orop(); emit(t); break;
      default : return;
    }
//qdbg("orop RET\n");
}
static void parse(void)
{
//qdbg("parse\n");
  lookahead=lexan();
  if(lookahead!=DONE)expr();
//qdbg("parse RET\n");
}

/********************
* POSTFIX EVALUATOR *
********************/
static long   pfstack[MAX_TOKEN];
static short  pfindex;

static void push(long val)
{ pfstack[pfindex]=val;
  if(pfindex<MAX_TOKEN-1)pfindex++;
  // else expr too complex error!
}
static long pop(void)
{ if(pfindex>0)pfindex--;	// Check first because expr might be too complex
//qdbg("pop() returns %d\n",pfstack[pfindex]);
  return pfstack[pfindex];
}
static long top(void)
{ if(pfindex>0)return pfstack[pfindex-1];
  else         return 0;
}

static long eval(void)
/* Evaluate created postfix array */
{ short i;
  long v1,v2;
  pfindex=0;
  for(i=0;i<destindex;i++)
  { switch(dest[i].token)
    { case T_CONST     : push(dest[i].val); break;
      case T_UNARYMINUS: push(-pop()); break;
      case T_XOR       : push(~pop()); break;
      case '&':     push(pop()&pop()); break;
      case '^':     push(pop()^pop()); break;
      case '|':     push(pop()|pop()); break;
      case '+':     push(pop()+pop()); break;
      //case '-':     push(-pop()+pop()); break;
      //case '-':     v2=pop(); v1=pop(); push(v1-v2); break;
      case '-':
//printf("eval: -, pfindex=%d\n",pfindex);
        v2=pop(); v1=pop();
//printf("eval: -, v1=%d, v2=%d\n",v1,v2);
        push(v1-v2); break;
      case '*':     push(pop()*pop()); break;
      case '/':     v2=pop(); v1=pop(); if(v2)push(v1/v2); else push(0); break;
      case '%':     v2=pop(); v1=pop(); if(v2)push(v1%v2); else push(0); break;
      default:      break;
    }
  }
  if(pfindex!=1)qdbg("eval: pfindex!=1 at end\n");
  return top();
}
int Eval(cstring s)		/* Expression evaluator */
{ QASSERT(s);
  src=s;
  srcindex=-1;
  destindex=0;
  parse();
//qdbg("sizeof(long)=%d\n",sizeof(long));
//qdbg("sizeof(int)=%d\n",sizeof(int));
  return (int)eval();
}