Celestin Apprentice 2/Apprentice-Release2.iso/Source Code/C/Snippets/Expression Parser/expr_parser.c

C/C++ Source or Header | 1994-11-04 | 4.2 KB | 260 lines | [TEXT/MMCC]

/*
 * expr_parser.c - a recursive-descent parser for simple mathematical expressions
 *
 * The grammar is:
 *
 *   expr -> expr '+' term | expr '-' term | term
 *   term -> term '*' factor | term '/' factor | factor
 *   factor -> '(' expr ')' | '-' factor | NUMBER
 *
 * or, equivalently (to eliminate left recursion):
 *
 *   expr  -> term expr'
 *   expr' -> '+' term expr' | '-' term expr' | e
 *   term  -> factor term'
 *   term' -> '*' factor term' | '/' factor term' | e
 *   factor -> '(' expr ')' | '-' factor | NUMBER
 */

/** includes **/

#include <stdio.h>

/** type definitions **/

typedef enum {
    NUMBER = 1,
    PLUS,
    MINUS,
    TIMES,
    DIVIDED_BY,
    LPAREN,
    RPAREN
} TOKEN_TYPE;

typedef struct {
    TOKEN_TYPE    type;
    float        value;
} TOKEN;

/** global variables **/

Boolean        eoln;            /* TRUE if the end of line has been reached */
Boolean        err;            /* TRUE if an error was encounted during parsing */
Boolean        unget;            /* TRUE if getc() should return the last char */
char        *buf;            /* the character buffer */
char        last;            /* last character fetched */

/** prototypes **/

float parse_expr(char *s);

static float expr(void);
static float expr2(void);
static float term(void);
static float term2(void);
static float factor(void);
static void get_token(TOKEN *t);
static char get_char(void);
static void unget_char(void);

/* test routine for expression parser */

int main(int argc, char *argv[])
{
    float    result;
    char    s[100];

    for (;;) {
        printf("enter an expression: ");
        scanf("%s", s);

        result = parse_expr(s);
        if (!err)
            printf("result = %g\n\n", result);
        else
            printf("bad expression\n\n");
    }
}

/* parse_expr() is the main routine for the parser */
/* it expects a C string (null-terminated) as its argument */

float parse_expr(char *s)
{
    eoln = err = unget = FALSE;
    buf = s;

    return (expr());
}


static float expr(void)
{
    return (term() + expr2());
}


static float expr2(void)
{
    TOKEN    t;

    get_token(&t);

    if (t.type == PLUS)
        return (term() + expr2());
    else if (t.type == MINUS)
        return (-(term() + expr2()));
    else {
        unget_char();
        return (0);
    }
}


static float term(void)
{
    return (factor() * term2());
}


static float term2(void)
{
    TOKEN    t;

    get_token(&t);

    if (t.type == TIMES)
        return (factor() * term2());
    else if (t.type == DIVIDED_BY)
        return (1 / (factor() / term2()));
    else {
        unget_char();
        return (1);
    }
}


static float factor(void)
{
    float    e;
    TOKEN    t;

    get_token(&t);

    if (eoln)
        err = TRUE;
    else if (t.type == LPAREN) {
        e = expr();

        get_token(&t);
        if (t.type == RPAREN)
            return (e);
        else {
            err = TRUE;
            return (0);
        }
    }
    else if (t.type == MINUS)
        return (-factor());
    else if (t.type == NUMBER)
        return (t.value);
    else {
        err = TRUE;
        return (0);
    }
}

/* get_token() is the lexical analyzer */
/* it returns the next token in the input stream */
/* it sets the eoln flag if the end of the line is reached */

static void get_token(TOKEN *t)
{
    register char    c;

    while ((c = get_char()) == ' ')    /* ignore spaces */
        ;

    switch (c) {
        case '\0':
            eoln = TRUE;            /* we've reached the end of the line */
            break;
        case '+':
            t->type = PLUS;
            break;
        case '-':
            t->type = MINUS;
            break;
        case '*':
            t->type = TIMES;
            break;
        case '/':
            t->type = DIVIDED_BY;
            break;
        case '(':
            t->type = LPAREN;
            break;
        case ')':
            t->type = RPAREN;
            break;
        default:
            if (c >= '0' && c <= '9' || c == '.') {
                float    value;
                float    dec;

                if (c == '.') {
                    value = 0;
                    dec = 10;
                }
                else {
                    value = c - '0';
                    dec = 0;
                }

                while ((c = get_char()) >= '0' && c <= '9' || c == '.') {
                    if (c == '.') {
                        if (dec == 0)
                            dec = 10;
                        else {
                            err = TRUE;
                            break;
                        }
                    }
                    else if (dec == 0) {
                        value *= 10;
                        value += (c - '0');
                    }
                    else {
                        value += (c - '0') / dec;
                        dec *= 10;
                    }
                }

                unget_char();                /* unget the last character read */

                t->value = value;
                t->type = NUMBER;
            }
            else
                err = TRUE;                    /* bad character in input */
            break;
    }
}


static char get_char(void)
{
    if (unget)
        unget = FALSE;
    else
        last = *buf++;
    return (last);
}


static void unget_char(void)
{
    unget = TRUE;
}