Category : C Source Code
Archive   : POPI.ZIP
Filename : EXPR.C

/* @(#)expr.c 1.9 89/12/11
*
* Parser routines used by the popi program.
*
* Popi was originally written by Gerard J. Holzmann - AT&T Bell Labs.
* This version is based on the code in his Prentice Hall book,
* "Beyond Photography - the digital darkroom," ISBN 0-13-074410-7,
* which is copyright (c) 1988 by Bell Telephone Laboratories, Inc.
*
* Permission is given to distribute these extensions, as long as these
* introductory messages are not removed, and no monies are exchanged.
*
* No responsibility is taken for any errors or inaccuracies inherent
* either to the comments or the code of this program, but if reported
* (see README file) then an attempt will be made to fix them.
*/

#include
#include
#include "popi.h"

int lat; /* look ahead token */
int prs = 0;
parse_t parsed[MAXTOKENS];
int RangeCheck = 1;

/* prototypes for local functions */
void expr P((void)),
level P((int)),
factor P((void)),
fileref P((int, int)),
expect P((int)),
emit P((int));

#define MAX_SAME_PREC 5 /* max length row of op[], +1 */

static int op[][MAX_SAME_PREC] =
{
{ POW },
{ '*', }, /* Do mul before div, to avoid int underflow */
{ '/', '%' },
{ '+', '-' },
{ LSHIFT, RSHIFT },
{ '>', '<', GE, LE },
{ EQ, NE },
{ '&' },
{ '^' },
{ '|' },
{ AND },
{ OR },
};

/* I was using NELS(op) here (see popi.h) but Microsoft Quick C
* gets this wrong (it thinks sizeof *op == sizeof op).
*/
/*#define PREC_LEVELS NELS(op) /**/
#define PREC_LEVELS (sizeof op / sizeof (int [MAX_SAME_PREC]))

static void
emit(what)
int what;
{
DEBUG((Debug,
what < 127 && isprint(what)
? "emit('%c' (%d))\n"
: "emit(%d)\n",
what, what
));

if (prs >= MAXTOKENS)
{
SPRINTF(ErrBuf, "expression too long");
error(ERR_PARSE);
}
parsed[prs++] = what;
}

/*
* Token is either CLVAL or CRVAL, indicating
* an lvalue or an rvalue. We actually
* determine if the coordinates are polar or cartesian.
*
*/
static void
fileref(val, tok)
int val, tok;
{
DEBUG((Debug, "fileref(val=%d, tok=%d)\n", val, tok));

if (val < 0 || val >= nsrc || src[val].str == (char *) 0)
{
SPRINTF(ErrBuf, "bad file number: %d", val - 1);
error(ERR_PARSE);
}

emit(VALUE);
emit(val);
if (lat == '[')
{
/* cartesian coordinate reference */
lex();
expr();
expect(',');
expr();
expect(']'); /* [x, y] */
emit(tok);
return;
}

if (lat == '{')
{
/* polar coordinate reference */
lex();
expr();
expect(',');
expr();
expect('}'); /* {r, a} */
emit(tok == CLVAL ? PLVAL : PRVAL);
return;
}

/* default (no index specified) is [x, y] */
emit('x');
emit('y');
emit(tok);
}


/*
* factor = '(' expr ')'
* | UNARYOP factor
* | FNCALL1 '(' expr ')'
* | FNCALL2 '(' expr ',' expr ')'
*
* UNARYOP = '!'
* | '~'
*
* FNCALL1 = 'sin'
* | 'cos'
* | 'log'
* | 'sqrt'
* | 'abs'
*
* FNCALL2 = 'atan'
*/
static void
factor()
{
int n;
int token;

DEBUG((Debug, "factor() lat='%c'\n", lat));

switch (token = lat)
{
case '(':
lex();
expr();
expect(')');
break;

case '-':
lex();
factor();
if (parsed[prs-2] == VALUE) /* constant evaluation */
parsed[prs-1] = -parsed[prs-1];
else
emit(UMIN);
break;

case '!':
lex();
factor();
if (parsed[prs-2] == VALUE)
parsed[prs-1] = !parsed[prs-1];
else
emit(token);
break;

case '~':
lex();
factor();
if (parsed[prs-2] == VALUE)
parsed[prs-1] = ~parsed[prs-1];
else
emit(token);
break;

case INAME:
n = lexval;
lex();
fileref(n+1, CRVAL);
break;

case '$':
lex();
expect(VALUE);
fileref(lexval+1, CRVAL);
break;

case VALUE:
emit(VALUE);
emit(lexval);
lex();
break;

case 'r':
case 'a':
MakePolar(); /* Create polar coordinate lookup tables */
/* fall through */
case 'y':
case 'x':
emit(lat);
lex();
break;

case RAND:
lex();
expect('(');
expect(')');
emit(RAND);
break;

case SIN:
case COS:
case LOG:
case SQRT:
case ABS:
lex();
expect('(');
expr();
expect(')');
if (parsed[prs-2] == VALUE)
{
switch (token)
{
case SIN:
parsed[prs-1] = (parse_t) sin((double) DtoR(parsed[prs-1]));
break;
case COS:
parsed[prs-1] = (parse_t) cos((double) DtoR(parsed[prs-1]));
break;
case LOG:
parsed[prs-1] = (parse_t) log((double)parsed[prs-1]);
break;
case SQRT:
parsed[prs-1] = (parse_t) sqrt((double)parsed[prs-1]);
break;
case ABS:
if (parsed[prs-1] < 0)
parsed[prs-1] = -parsed[prs-1];
break;
}
}
else
emit(token);
break;

case ATAN:
case HYPOT:
lex();
expect('(');
expr();
expect(',');
expr();
expect(')');
emit(token);
break;

default:
SPRINTF(ErrBuf, "expr: syntax error (expected factor)");
error(ERR_PARSE);
break;
}
}


/*
* Recursive descent parser for binary operators as specified
* in the op[] array above.
*
* term = factor BINARYOP term
*/
static void
level(nr)
int nr;
{
int i;
extern int noerr;

DEBUG((Debug, "level(%d) lat='%c'\n", nr, lat));

if (nr < 0)
{
factor();
return;
}

level(nr-1);

for (i = 0; op[nr][i] != 0 && noerr; i++)
if (lat == op[nr][i])
{
/* LHS of op is already on parse string;
* process RHS and then emit the operator
*/
lex();
level(nr);
/*
* Do a little compile-time constant evaluation here
*
* If the parse string looks like this:
* <= prs
* + value (prs - 1) RHS
* ^ VALUE (prs - 2)
* v value (prs - 3) LHS
* - VALUE (prs - 4)
* then instead of emitting the operation, we can evaluate.
*/
if (prs >= 4 && parsed[prs-2] == VALUE && parsed[prs-4] == VALUE)
{
parse_t *dest = &parsed[prs-3],
*src = &parsed[prs-1];

DEBUG((Debug, "Optimise: %ld %ld '%c'(%d) ", *dest, *src, lat, lat));
switch(op[nr][i])
{
case POW:
*dest = (parse_t) pow((double) *dest, (double) *src);
break;

case '*':
*dest *= *src;
break;

case '/':
if (*src == 0)
*dest = Zmax;
else
*dest /= *src;
break;

case '%':
if (*src != 0)
*dest %= *src;
break;

case '+':
*dest += *src;
break;

case '-':
*dest -= *src;
break;

case LSHIFT:
*dest <<= *src;
break;

case RSHIFT:
*dest >>= *src;
break;

case '>':
*dest = *dest > *src;
break;

case '<':
*dest = *dest < *src;
break;

case GE:
*dest = *dest >= *src;
break;

case LE:
*dest = *dest <= *src;
break;

case EQ:
*dest = *dest == *src;
break;

case NE:
*dest = *dest != *src;
break;

case '&':
*dest &= *src;
break;

case '^':
*dest ^= *src;
break;

case '|':
*dest |= *src;
break;

case AND:
*dest = *dest && *src;
break;

case OR:
*dest = *dest || *src;
break;

default:
SPRINTF(ErrBuf,
"Unrecognised token (%d) found during optimisation",
lat);
error(ERR_SNARK);
break;
}
prs -= 2;
DEBUG((Debug, "=> %ld\n", *dest));
}
else
emit(op[nr][i]);
break;
}
}

#ifndef __MSC__ /* MSC gets scope rules wrong */
static
#endif /* __MSC__ */
void
expr()
{
extern int prs;
int remem1,
remem2;

DEBUG((Debug, "expr() lat='%c'\n", lat));
DEBUG((Debug, "levels of precedence: %d\n", PREC_LEVELS));

level(PREC_LEVELS - 1);

if (lat == '?')
{
lex();
emit('?');
remem1 = prs;
emit(0);
expr();
expect(':');
emit(':');
remem2 = prs;
emit(0);
parsed[remem1] = prs-1;
expr();
parsed[remem2] = prs-1;
}
}


void
expect(t)
int t;
{
DEBUG((Debug, "expect('%c')\n", t));

if (lat == t)
lex();
else
{
if (t < 127)
SPRINTF(ErrBuf, "expected token '%c' (%d)", t, t);
else
SPRINTF(ErrBuf, "expected token (%d)", t);
error(ERR_PARSE);
}
}

/*
* Transform = NEW '[' index ']' '=' expr
* | NEW '=' expr
* | expr
*/
void
transform()
{
extern int prs;

DEBUG((Debug, "transform() lat='%c'\n", lat));

prs = 0 ; /* initial length of parse string */
if (lat != NEW)
{
expr();
emit('@');
}
else
{
lex();
if (lat == '[')
{
fileref(CURNEW, CLVAL);
expect('=');
expr();
emit('=');
}
else
{
expect('=');
expr();
emit('@');
}
}
if (lat != '\n')
{
SPRINTF(ErrBuf,
"syntax error - expected operator or end of expression");
error(ERR_PARSE);
}
assert(lat == '\n');
}