parse.c

ngspice又一个电子CAD仿真软件代码.功能更全

/**********
Copyright 1990 Regents of the University of California.  All rights reserved.
Author: 1985 Wayne A. Christopher, U. C. Berkeley CAD Group
$Id: parse.c,v 1.15 2005/05/26 19:51:33 sjborley Exp $
**********/

/*
 * A simple operator-precedence parser for algebraic expressions.
 * This also handles relational and logical expressions.
 */

#include <ngspice.h>
#include <bool.h>
#include <fteparse.h>
#include <fteext.h>
#include <sim.h>

#include "parse.h"


/* static declarations */
static bool checkvalid(struct pnode *pn);
static struct element * lexer(void);
static struct pnode * parse(void);
static struct pnode * makepnode(struct element *elem);
static struct pnode * mkbnode(int opnum, struct pnode *arg1, struct pnode *arg2);
static struct pnode * mkunode(int op, struct pnode *arg);
static struct pnode * mkfnode(char *func, struct pnode *arg);
static struct pnode * mknnode(double number);
static struct pnode * mksnode(char *string);
/*static void   print_elem(struct element *elem); / va: for debugging /
static char * get_token_name(int e_token); / va, for debugging */


static int lasttoken = END, lasttype;
static char *sbuf;

struct pnode *
ft_getpnames(wordlist *wl, bool check)
{
    struct pnode *pn = NULL, *lpn = NULL, *p;
    char *xsbuf;
    char buf[BSIZE_SP], *thisone, *s;

    if (!wl) {
        fprintf(cp_err, "Warning: NULL arithmetic expression\n");
        return (NULL);
    }

    lasttoken = END;
    xsbuf = sbuf = wl_flatten(wl);
    thisone = sbuf;
    while (*sbuf != '\0') {
        if (!(p = parse())) {
	    tfree(xsbuf);
            return (NULL);
	}

        /* Now snag the name... Much trouble... */
        while (isspace(*thisone))
            thisone++;
        for (s = buf; thisone < sbuf; s++, thisone++)
            *s = *thisone;
        *s = '\0';
        p->pn_name = copy(buf);

        if (pn) {
            lpn->pn_next = p;
	    pn->pn_next->pn_use++;
            lpn = p;
        } else
            pn = lpn = p;
    }
    tfree(xsbuf);
    if (check)
        if (!checkvalid(pn))
            return (NULL);
    return (pn);
}

/* See if there are any variables around which have length 0 and are
 * not named 'list'. There should really be another flag for this...
 */

static bool
checkvalid(struct pnode *pn)
{
    while (pn) {
        if (pn->pn_value) {
            if ((pn->pn_value->v_length == 0) && 
                !eq(pn->pn_value->v_name, "list")) {
                if (eq(pn->pn_value->v_name, "all"))
                    fprintf(cp_err,
                    "Error: %s: no matching vectors.\n",
                        pn->pn_value->v_name);
                else
                    fprintf(cp_err,
                        "Error: %s: no such vector.\n",
                        pn->pn_value->v_name);
                return (FALSE);
            }
        } else if (pn->pn_func || 
                (pn->pn_op && (pn->pn_op->op_arity == 1))) {
            if (!checkvalid(pn->pn_left))
                return (FALSE);
        } else if (pn->pn_op && (pn->pn_op->op_arity == 2)) {
            if (!checkvalid(pn->pn_left))
                return (FALSE);
            if (!checkvalid(pn->pn_right))
                return (FALSE);
        } else
            fprintf(cp_err, 
                "checkvalid: Internal Error: bad node\n");
        pn = pn->pn_next;
    }
    return (TRUE);
}

/* Everything else is a string or a number. Quoted strings are kept in 
 * the form "string", and the lexer strips off the quotes...
 */
/* va: the structure returned is static, e_string is a copy 
       (in case of e_token==VALUE,e_type==STRING) */
static struct element *
lexer(void)
{
    double *td;
    int j = 0;
    static struct element el;
    static struct element end = { END };
    static char *specials = " \t%()-^+*,/|&<>~=";
    static bool bracflag = FALSE;
    char *ss, *s;
    int atsign;

    if (bracflag) {
        bracflag = FALSE;
        el.e_token = LPAREN;
        goto done;
    }

    el.e_token = END;
    while ((*sbuf == ' ') || (*sbuf == '\t'))
        sbuf++;
    if (*sbuf == '\0')
        goto done;

    switch (*sbuf) {

        case '-':
        if ((lasttoken == VALUE) || (lasttoken == RPAREN))
            el.e_token = MINUS;
        else
            el.e_token = UMINUS;
        sbuf++;
        break;

        case '+':
        el.e_token = PLUS; 
        sbuf++;
        break;

        case ',':
        el.e_token = COMMA;
        sbuf++;
        break;

        case '*':
        el.e_token = TIMES; 
        sbuf++;
        break;

        case '%':
        el.e_token = MOD; 
        sbuf++;
        break;

        case '/':
        el.e_token = DIVIDE; 
        sbuf++;
        break;

        case '^':
        el.e_token = POWER; 
        sbuf++;
        break;

        case '[':
        if (sbuf[1] == '[') {
            el.e_token = RANGE;
            sbuf += 2;
        } else {
            el.e_token = INDX;
            sbuf++;
        }
        bracflag = TRUE;
        break;

        case '(':
        if (((lasttoken == VALUE) && ((lasttype == NUM))) || (lasttoken
                == RPAREN)) {
            el = end;
            goto done;
        } else {
            el.e_token = LPAREN; 
            sbuf++;
            break;
        }

        case ']':
        el.e_token = RPAREN; 
        if (sbuf[1] == ']')
            sbuf += 2;
        else
            sbuf++;
        break;

        case ')':
        el.e_token = RPAREN; 
        sbuf++;
        break;

        case '=':
        el.e_token = EQ;
        sbuf++;
        break;

        case '>':
        case '<':
        for (j = 0; isspace(sbuf[j]); j++)
            ; /* The lexer makes <> into < > */
        if (((sbuf[j] == '<') || (sbuf[j] == '>')) &&
                (sbuf[0] != sbuf[j])) {
            /* Allow both <> and >< for NE. */
            el.e_token = NE;
            sbuf += 2 + j;
        } else if (sbuf[1] == '=') {
            if (sbuf[0] == '>')
                el.e_token = GE;
            else
                el.e_token = LE;
            sbuf += 2;
        } else {
            if (sbuf[0] == '>')
                el.e_token = GT;
            else
                el.e_token = LT;
            sbuf++;
        }
        break;

        case '&':
        el.e_token = AND;
        sbuf++;
        break;

        case '|':
        el.e_token = OR;
        sbuf++;
        break;

        case '~':
        el.e_token = NOT;
        sbuf++;
        break;

        case '"':
        if ((lasttoken == VALUE) || (lasttoken == RPAREN)) {
            el = end;
            goto done;
        }
        el.e_token = VALUE;
        el.e_type = STRING;
        el.e_string = copy(++sbuf);
        for (s = el.e_string; *s && (*s != '"'); s++, sbuf++)
            ;
        *s = '\0';
        sbuf++;
        break;
    }

    if (el.e_token != END)
        goto done;

    ss = sbuf;
    td = ft_numparse(&ss, FALSE);
    if ((!ss || *ss != ':') && td) {
        if ((lasttoken == VALUE) || (lasttoken == RPAREN)) {
            el = end;
            goto done;
        }
        el.e_double = *td;
        el.e_type = NUM;
        el.e_token = VALUE;
        sbuf = ss;
        if (ft_parsedb)
            fprintf(stderr, "lexer: double %G\n",
                    el.e_double);
    } else {
        /* First, let's check for eq, ne, and so on. */
        if ((sbuf[0] == 'g') && (sbuf[1] == 't') && 
               strchr(specials, sbuf[2])) {
            el.e_token = GT;
            sbuf += 2;
        } else if ((sbuf[0] == 'l') && (sbuf[1] == 't') && 
               strchr(specials, sbuf[2])) {
            el.e_token = LT;
            sbuf += 2;
        } else if ((sbuf[0] == 'g') && (sbuf[1] == 'e') && 
               strchr(specials, sbuf[2])) {
            el.e_token = GE;
            sbuf += 2;
        } else if ((sbuf[0] == 'l') && (sbuf[1] == 'e') && 
               strchr(specials, sbuf[2])) {
            el.e_token = LE;
            sbuf += 2;
        } else if ((sbuf[0] == 'n') && (sbuf[1] == 'e') && 
               strchr(specials, sbuf[2])) {
            el.e_token = NE;
            sbuf += 2;
        } else if ((sbuf[0] == 'e') && (sbuf[1] == 'q') && 
               strchr(specials, sbuf[2])) {
            el.e_token = EQ;
            sbuf += 2;
        } else if ((sbuf[0] == 'o') && (sbuf[1] == 'r') && 
               strchr(specials, sbuf[2])) {
            el.e_token = OR;
            sbuf += 2;
        } else if ((sbuf[0] == 'a') && (sbuf[1] == 'n') && 
                (sbuf[2] == 'd') &&strchr(specials, sbuf[3])) {
            el.e_token = AND;
            sbuf += 3;
        } else if ((sbuf[0] == 'n') && (sbuf[1] == 'o') && 
                (sbuf[2] == 't') &&strchr(specials, sbuf[3])) {
            el.e_token = NOT;
            sbuf += 3;
        } else {
            if ((lasttoken == VALUE) || (lasttoken == RPAREN)) {
                el = end;
                goto done;
            }
            el.e_string = copy(sbuf);	/* XXXX !!!! */
            /* It is bad how we have to recognise '[' -- sometimes
             * it is part of a word, when it defines a parameter
             * name, and otherwise it isn't.
	     * va, ']' too
             */
	    atsign = 0;
            for (s = el.e_string; *s && !index(specials, *s); s++, sbuf++) {
                if (*s == '@')
		    atsign = 1;
                else if (!atsign && ( *s == '[' || *s == ']' ) )
                    break;
	    }
            if (*s)
                *s = '\0';
            el.e_type = STRING;
            el.e_token = VALUE;
            if (ft_parsedb)
                fprintf(stderr, "lexer: string %s\n",
                        el.e_string);
        }
    }
done:
    lasttoken = el.e_token;
    lasttype = el.e_type;
    if (ft_parsedb)
        fprintf(stderr, "lexer: token %d\n", el.e_token);
    return (&el);
}

/* The operator-precedence parser. */

#define G 1 /* Greater than. */
#define L 2 /* Less than. */
#define E 3 /* Equal. */
#define R 4 /* Error. */

#define STACKSIZE 200

static char prectable[23][23] = {
       /* $  +  -  *  %  /  ^  u- (  )  ,  v  =  >  <  >= <= <> &  |  ~ IDX R */
/* $ */ { R, L, L, L, L, L, L, L, L, R, L, L, L, L, L, L, L, L, L, L, L, L, L },
/* + */ { G, G, G, L, L, L, L, L, L, G, G, L, G, G, G, G, G, G, G, G, G, L, L },
/* - */ { G, G, G, L, L, L, L, L, L, G, G, L, G, G, G, G, G, G, G, G, G, L, L },
/* * */ { G, G, G, G, G, G, L, L, L, G, G, L, G, G, G, G, G, G, G, G, G, L, L },
/* % */ { G, G, G, G, G, G, L, L, L, G, G, L, G, G, G, G, G, G, G, G, G, L, L },
/* / */ { G, G, G, G, G, G, L, L, L, G, G, L, G, G, G, G, G, G, G, G, G, L, L },
/* ^ */ { G, G, G, G, G, G, L, L, L, G, G, L, G, G, G, G, G, G, G, G, G, L, L },
/* u-*/ { G, G, G, G, G, G, G, G, L, G, G, L, G, G, G, G, G, G, G, G, G, L, L },
/* ( */ { R, L, L, L, L, L, L, L, L, E, L, L, L, L, L, L, L, L, L, L, L, L, L },
/* ) */ { G, G, G, G, G, G, G, G, R, G, G, R, G, G, G, G, G, G, G, G, G, G, G },
/* , */ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, G, L, L },
/* v */ { G, G, G, G, G, G, G, G, G, G, G, R, G, G, G, G, G, G, G, G, G, G, G },
/* = */ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, L, L, L },
/* > */ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, L, L, L },
/* < */ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, L, L, L },
/* >=*/ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, L, L, L },
/* <=*/ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, L, L, L },
/* <>*/ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, L, L, L },
/* & */ { G, L, L, L, L, L, L, L, L, G, L, L, L, L, L, L, L, L, G, G, L, L, L },
/* | */ { G, L, L, L, L, L, L, L, L, G, L, L, L, L, L, L, L, L, L, G, L, L, L },
/* ~ */ { G, L, L, L, L, L, L, L, L, G, L, L, G, G, G, G, G, G, G, G, G, L, L },
/*INDX*/{ G, G, G, G, G, G, G, G, L, G, G, L, G, G, G, G, G, G, G, G, G, G, L },
/*RAN*/ { G, G, G, G, G, G, G, G, L, G, G, L, G, G, G, G, G, G, G, G, G, G, G }
} ;

/* Return an expr. */
static struct pnode *
parse(void)
{
    struct element stack[STACKSIZE];
    int sp = 0, st, i, spmax=0; /* va: spmax = maximal used stack */
    struct element *top, *next;
    struct pnode *pn, *lpn, *rpn;
    char rel;
    char * parse_string=sbuf; /* va, duplicate sbuf's pointer for error message only, no tfree */

    stack[0].e_token = END;
    next = lexer();

    while ((sp > 1) || (next->e_token != END)) {
        /* Find the top-most terminal. */
        /* va: no stack understepping, because stack[0].e_token==END */
        i = sp;
        do {
            top = &stack[i--];
        } while (top->e_token == VALUE && i>=0); /* va: do not understep stack */
        if (top->e_token == VALUE) {
            fprintf(cp_err, "Error: in parse.c(parse) stack understep.\n");
            return (NULL);
        }
/*for (i=0; i<=sp; i++) print_elem(stack+i); printf("next: "); print_elem(next); printf("\n");*/ 

        rel = prectable[top->e_token][next->e_token];
        switch (rel) {
            case L:
            case E:
            /* Push the token read. */
            if (sp == (STACKSIZE - 1)) {
                fprintf(cp_err, "Error: stack overflow\n");
                return (NULL);
            }
            bcopy((char *) next, (char *) &stack[++sp],
                    sizeof (struct element));
            if (spmax<sp) spmax=sp; /* va: maximal used stack increased */
            next = lexer();
            continue;

            case R:
            fprintf(cp_err, "Syntax error: parsing expression '%s'.\n", parse_string);
            return (NULL);

            case G:
            /* Reduce. Make st and sp point to the elts on the
             * stack at the end and beginning of the junk to
             * reduce, then try and do some stuff. When scanning
             * back for a <, ignore VALUES.
             */

            st = sp;
            if (stack[sp].e_token == VALUE)
                sp--;
            while (sp > 0) {
                if (stack[sp - 1].e_token == VALUE)
                    i = 2;  /* No 2 pnodes together... */
                else
                    i = 1;
                if (prectable[stack[sp - i].e_token]
                         [stack[sp].e_token] == L)
                    break;
                else
                    sp = sp - i;
            }
            if (stack[sp - 1].e_token == VALUE)
                sp--;
            /* Now try and see what we can make of this.
             * The possibilities are: unop node