4.2. En expression parser

En kalkulator er et program, som kan fodres med beregningsudtryk og som derefter beregner resultatet. Som regel skrives resultatet på en computerskærm, men det kan jo lige så godt være på en papirstrimmel eller i et felt i et regneark. Et udtryk kaldes på engelsk et expression.

Hvis man vil forstå, hvordan en oversætter/compiler virker, så er en kalkulator et godt sted at begynde. En kalkulator består af analysator, som kaldes en expression parser, og en beregningsdel. Expression parseren har til opgave at analysere input og se, hvad der skal gøres.

En sådan expression parser findes også i en oversætter. I stedet for at foretage beregning, så udskriver oversætteren assembler kode, der vil kunne foretage beregningen.

En væsentlig del af kunsten at skrive en oversætter består i at skille tingene ad. Det kræver stor forståelse for opgaven, en stor abstraktionsevne, for kode-generator delen er jo flettet ind, så at sige, i analysen. Hver gang man kommer til et delresultat, skal det omsættes til kode. Endvidere kræves der også en forståelse for assembler koden. Derfor er det meget godt at begynde med en kalkulator. Den er simplere at skrive, nemmere at forstå, men rummer de samme problemstillinger.

I en compiler har man brug for en expression parser, hver gang der er et statement. Et statement eller en (programsprog-)sætning kan i simple tilfælde blot være et beregningsudtryk efterfulgt af et semikolon. I mere komplicerede tilfælde er det fx. keywordet if efterfulgt af en betingelse og så et eller andet stykke kode, som styres af if'et . Betingelsen er, i C sproget, et expression (altså et udtryk). Den efterfølgende sætning vil i mange tilfælde være et funktionskald (også et udtryk, strengt taget) eller en tildeling som i C sproget også er et udtryk.

Så en expression parser er en vigtig del af computer-software. Her kommer et eksempel på en kalkulator, som beregner ganske almindelige regnestykker som 2+3 eller mere komplicerede, hvori der indgår aritmetiske funktioner og en enkelt variabel, X, som er resultatet af foregående beregning. Ideen her er hentet fra gode gamle Compas Pascal, men det er altså C-kode, dette her.

En lignende kalkulator i C++ er en god opgave for viderekomne. (Jeg vil senere prøve at komme med nogle sammenligninger med Stroustrups eksempel, Stroustrup[1997] p. 108.)

Eksempel på input:


calcu '200 * sin(0.444)'
85.911

calcu <<SLUT
2 + 3
5 * X
SLUT

Calc:      5.0000
Calc:     25.0000
Calc:

calcu
Calc: 32/square(2)
         ^Error

Programmet benytter til den viste fejlmeddelelse en særlig slem variant af printf format specification, som skriver et antal spaces ud styret af en variabel: printf("En padded string: %*s\n",lengde,string); Meget smart - men første gang lidt vanskeligt at læse og forstå. Det styrer angivelsen af error positionen.

Programmet er i sin nuværende form ganske anvendeligt, fordi det kan fungere som erstatning for expr programmet, der stiller alt for mange krav til spaces og anden formatering til de expressions, som skal evalueres. Men programmet kan simpelt hen også anvendes til beregning af prislister (det har det faktisk været!)

Eksempel 4-1. Calculator, recursive descent expression parsing


/* file calcu.c */
/* (c) Donald Axel GPL - license */
/* ANSI - C program demonstration, command line calculator */
/* Recursive descent parser */
/* Improve: Make a HELP command. Add more variables.       */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>



#define MAXL 8196
char gs[MAXL];
char *cp;
char *errorp;
double oldval;

/* local prototypes: */
int calcu();
int evaluate(char *line, double *prev_result);
int stricmp(const char *s1, const char *s2);
int strnicmp(const char *s1, const char *s2, int len);


int main(int argc, char *argv[])
{
    int rv, jj;

    jj = 0;
    while (++jj < argc) {
        strcat(gs, argv[jj]);
    }
    if (argc == 1)
        return calcu();
    strcat(gs, "\n");
    rv = evaluate(gs, &oldval);
    if (!rv)
        printf("%g\n", oldval);
    else
        printf("Calcu:%s\n%*s\n", gs, rv, "^Error");
    return rv;
}


/* Description: */
/* calcu() sets up a string which is then evaluated as an expression  */
/* If (argc>1) main sets up string for evaluate() and prints result.  */
/* stricmp does not stop at '\n' - so we have to compare with "xx\n"  */
/* gettok() could solve that problem. TRY to use gettok().            */



int nextchar()
{
    ++cp;
    while (*cp == ' ')
        ++cp;
    return *cp;
}


int eatspace()
{
    while (*cp == ' ')
        ++cp;
    return *cp;
}


int calcu()
{
    FILE *ifil;
    char line[MAXL];
    int rpos;
    double r;

    ifil = stdin;
    while (1) {
        errorp = NULL;
        printf("Calc:");
        if (!fgets(line, MAXL, ifil))
            break;
        if (strlen(line) && strnicmp(line,"QUIT",4)
&& stricmp(line,"Q\n"))
            rpos = evaluate(line, &r);
        else
            break;
        if (!rpos) {
            printf("%-18g\n", r);
            oldval = r;
        } else {                /* prints Error in field min. 12 wide */
            printf("%*s\n", rpos, "^Error");
        }
    }
    return rpos;                /* if interactive rpos should always be 0 */
}


/* More local prototypes. This could, of course, be a separate file. */
double expression();
double product();
double potens();
double signedfactor();
double factor();
double stdfunc();


int evaluate(char *s, double *r)
{
    cp = s;
    eatspace();
    *r = expression();
    eatspace();
    if (*cp == '\n' && !errorp)
        return (0);
    else
        return (cp - s) + 11;
}


double expression()
{
    double e;
    int opera2;

    /* printf("test arg:%s\n",cp); */

    e = product();
    while ((opera2 = *cp) == '+' || opera2 == '-') {
        nextchar();
        if (opera2 == '+')
            e += product();
        else
            e -= product();
    }
    eatspace();
    return e;
}


double product()
{
    double dp;
    int ope;

    dp = potens();
    while ((ope = *cp) == '*' || ope == '/') {
        nextchar();
        if (ope == '*')
            dp *= potens();
        else
            dp /= potens();
    }
    eatspace();
    return dp;
}


double potens()
{
    double dpo;

    dpo = signedfactor();
    while (*cp == '^') {
        nextchar();
        dpo = exp(log(dpo) * signedfactor());
    }
    eatspace();
    return dpo;
}


double signedfactor()
{
    double ds;
    if (*cp == '-') {
        nextchar();
        ds = -factor();
    } else
        ds = factor();
    eatspace();
    return ds;
}


double factor()
{
    double df;

    /* while (*cp!='\n') {
       putchar(*cp++);
       } 
     */

    switch (*cp) {
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
        df = strtod(cp, &cp);
        break;
    case '(':
        nextchar();
        df = expression();
        if (*cp == ')')
            nextchar();
        else
            errorp = cp;
        break;
    case 'X':
        nextchar();
        df = oldval;
        break;

    default:
        df = stdfunc();
    }
    /* printf("ddt: df = %lf, *cp = %c\n",df,*cp); */

    eatspace();
    return df;
}


char *functionname[] =
{
    "abs", "sqrt", "sin", "cos", "atan", "log", "exp", "\0"
};

double stdfunc()
{
    double dsf;
    char **fnptr;
    int jj;

    eatspace();
    jj = 0;
    fnptr = functionname;
    while (**fnptr) {
        /* printf("%s\n",*fnptr); */
        if (strncmp(*fnptr, cp, strlen(*fnptr)) == 0)
            break;

        ++fnptr;
        ++jj;
    }
    if (!**fnptr) {
        errorp = cp;
        return 1;
    }
    cp += (strlen(*fnptr) - 1);
    nextchar();
    dsf = factor();
    switch (jj) {
    case 0: dsf = abs(dsf);  break;
    case 1: dsf = sqrt(dsf); break;
    case 2: dsf = sin(dsf);  break;
    case 3: dsf = cos(dsf);  break;
    case 4: dsf = atan(dsf); break;
    case 5: dsf = log(dsf);  break;
    case 6: dsf = exp(dsf);  break;
    default:{
            errorp = cp;
            return 4;
        }
    }
    eatspace();
    return dsf;
}


/* end calcu.c */