Post Reply 
Social Buttons
 
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Aritmetic evaluator - FB
04-17-2018, 08:55 PM
Post: #1
Aritmetic evaluator - FB
include parser..

Code:
'Arithmetic evaluation
'
'Create a program which parses and evaluates arithmetic expressions.
'
'Requirements
'
'    * An abstract-syntax tree (AST) for the expression must be created from parsing the
'      input.
'    * The AST must be used in evaluation, also, so the input may not be directly evaluated
'      (e.g. by calling eval or a similar language feature.)
'    * The expression will be a string or list of symbols like "(1+3)*7".
'    * The four symbols + - * / must be supported as binary operators with conventional
'      precedence rules.
'    * Precedence-control parentheses must also be supported.
'
'Standard mathematical precedence should be followed:
'
'    Parentheses
'    Multiplication/Division (left to right)
'    Addition/Subtraction (left to right)
'
'  test cases:
'  2*-3--4+-0.25 : returns -2.25
'  1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10 : returns 71

enum
    false = 0
    true = -1
end enum

enum Symbol
    unknown_sym
    minus_sym
    plus_sym
    lparen_sym
    rparen_sym
    number_sym
    mul_sym
    div_sym
    unary_minus_sym
    unary_plus_sym
    done_sym
    eof_sym
end enum

type Tree
    as Tree ptr leftp, rightp
    op as Symbol
    value as double
end type

dim shared sym as Symbol
dim shared tokenval as double
dim shared usr_input as string

declare function expr(byval p as integer) as Tree ptr

function isdigit(byval ch as string) as long
    return ch <> "" and Asc(ch) >= Asc("0") and Asc(ch) <= Asc("9")
end function

sub error_msg(byval msg as string)
    print msg
    system
end sub

' tokenize the input string
sub getsym()
    do
        if usr_input = "" then
            line input usr_input
            usr_input += chr(10)
        endif
        dim as string ch = mid(usr_input, 1, 1) ' get the next char
        usr_input = mid(usr_input, 2)           ' remove it from input

        sym = unknown_sym
        select case ch
            case " ":     continue do
            case chr(10), "": sym = done_sym: return
            case "+":     sym = plus_sym:     return
            case "-":     sym = minus_sym:    return
            case "*":     sym = mul_sym:      return
            case "/":     sym = div_sym:      return
            case "(":     sym = lparen_sym:   return
            case ")":     sym = rparen_sym:   return
            case else
                if isdigit(ch) then
                    dim s as string = ""
                    dim dot as integer = 0
                    do
                        s += ch
                        if ch = "." then dot += 1
                        ch = mid(usr_input, 1, 1)       ' get the next char
                        usr_input = mid(usr_input, 2)   ' remove it from input
                    loop while isdigit(ch) orelse ch = "."
                    if ch = "." or dot > 1 then error_msg("bogus number")
                    usr_input = ch + usr_input          ' prepend the char to input
                    tokenval = val(s)
                    sym = number_sym
                end if
                return
        end select
    loop
end sub

function make_node(byval op as Symbol, byval leftp as Tree ptr, byval rightp as Tree ptr) as Tree ptr
    dim t as Tree ptr

    t = callocate(len(Tree))
    t->op = op
    t->leftp = leftp
    t->rightp = rightp
    return t
end function

function is_binary(byval op as Symbol) as integer
    select case op
        case mul_sym, div_sym, plus_sym, minus_sym: return true
        case else: return false
    end select
end function

function prec(byval op as Symbol) as integer
    select case op
        case unary_minus_sym, unary_plus_sym:  return 100
        case mul_sym, div_sym:                 return  90
        case plus_sym, minus_sym:              return  80
        case else:                             return   0
    end select
end function

function primary as Tree ptr
    dim t as Tree ptr = 0

    select case sym
        case minus_sym, plus_sym
            dim op as Symbol = sym
            getsym()
            t = expr(prec(unary_minus_sym))
            if op = minus_sym then return make_node(unary_minus_sym, t, 0)
            if op = plus_sym  then return make_node(unary_plus_sym,  t, 0)
        case lparen_sym
            getsym()
            t = expr(0)
            if sym <> rparen_sym then error_msg("expecting rparen")
            getsym()
            return t
        case number_sym
            t = make_node(sym, 0, 0)
            t->value = tokenval
            getsym()
            return t
        case else: error_msg("expecting a primary")
    end select
end function

function expr(byval p as integer) as Tree ptr
    dim t as Tree ptr = primary()

    while is_binary(sym) andalso prec(sym) >= p
        dim t1 as Tree ptr
        dim op as Symbol = sym
        getsym()
        t1 = expr(prec(op) + 1)
        t = make_node(op, t, t1)
    wend
    return t
end function

function eval(byval t as Tree ptr) as double
    if t <> 0 then
        select case t->op
            case minus_sym:       return eval(t->leftp) - eval(t->rightp)
            case plus_sym:        return eval(t->leftp) + eval(t->rightp)
            case mul_sym:         return eval(t->leftp) * eval(t->rightp)
            case div_sym:         return eval(t->leftp) / eval(t->rightp)
            case unary_minus_sym: return -eval(t->leftp)
            case unary_plus_sym:  return  eval(t->leftp)
            case number_sym:      return t->value
            case else:            error_msg("unexpected tree node")
        end select
    end if
    return 0
end function

do
    getsym()
    if sym = eof_sym then exit do
    if sym = done_sym then continue do
    dim t as Tree ptr = expr(0)
    print"> "; eval(t)
    if sym = eof_sym then exit do
    if sym <> done_sym then error_msg("unexpected input")
loop
Find all posts by this user
Quote this message in a reply
04-25-2018, 10:03 PM (This post was last modified: 04-25-2018 10:03 PM by Ed Davis.)
Post: #2
RE: Aritmetic evaluator - FB
(04-17-2018 08:55 PM)Aurel Wrote:  include parser..

I really like this one. Mainly because I wrote it :-)

You must have gotten this from Rosetta Code?
Find all posts by this user
Quote this message in a reply
04-25-2018, 11:59 PM (This post was last modified: 04-26-2018 12:02 AM by Aurel.)
Post: #3
RE: Aritmetic evaluator - FB
Yes ..there are some nice versions..
Hi Ed !
How you find this place?
Smile

ahh yeah...from tjp forum link..
anyway ..what you say about my new tokenizer?
Big Grin
Find all posts by this user
Quote this message in a reply
04-26-2018, 01:14 AM (This post was last modified: 04-26-2018 01:20 AM by Ed Davis.)
Post: #4
RE: Aritmetic evaluator - FB
(04-25-2018 11:59 PM)Aurel Wrote:  Yes ..there are some nice versions..
Hi Ed !
How you find this place?
Smile

ahh yeah...from tjp forum link..
anyway ..what you say about my new tokenizer?
Big Grin

It looks pretty good. It will not allow identifiers with numbers in the name, as in "a2". But that is a simple fix. Or maybe that is the way you want it?

I prefer to specifically call out each keyword, in the same way you did symbols:

"if" + "~" + "IF", "while" + "~" + "WHILE", and so on. But that is just my personal preference.

As an aside, here is a simple byte-code compiler I wrote back sometime in the 90's. It is based on the Pascal version of PL/0 - a famous "teaching" language, from Niklaus Wirth, author of Algol-W, Pascal, Modula-2 and Oberon. PL/0 was often used in Compiler courses, as a first compiler to implement. It is very simple, but covers many topics in compiling.

I guess the only good thing about the following code is that it is short, simple and easy to follow. That (hopefully) makes it a good learning vehicle.

As you can see, the lexer - getsym() - is actually pretty similar to yours, except that it returns tokens (symbols) one at a time.

It includes a scanner, parser, code generator, and VM interpreter. No AST is used - when I wrote this, I still had not figured out AST's. They were like Greek to me :-)

It also uses recursive descent for expressions, as I didn't find out about precedence climbing until a bit later.

Code:
/*
PL/0 programing language complier and its virtual machine Based on
program 5.6 in Niklaus Wirth's "Algorithms+Data Structures=Programs",

Changes:
    <> used for not equal operator
    odd operator not implemented
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

enum {nmax=14,           /* max. no. of digits in numbers */
    norw=10,             /* no of reserved words */
    al=16,               /* length of identifier */
    levmax=3,            /* maximum depth of block nesting */
    cxmax=400,           /* size of code array */
    n_opcodes=19,
};

typedef enum {
    constant, variable, procedure,
} Kind;

typedef enum {
    ident, number, plus, minus, times, slash, eqlsym, neqsym, lsssym,
    leqsym, gtrsym, geqsym, lparen, rparen, comma, semicolon, period,
    becomes, beginsym, endsym, ifsym, thensym, whilesym, dosym,
    callsym, constsym, varsym, procsym, colon,
} Symbol;

typedef enum {
    ret, neg, add, sub, mul, dvd, eql, neq, lss, geq, gtr, leq,
    lit, lod, sto, cal, inc, jmp, jpc,
} Opcode;

typedef struct {
  Kind kind;
  int val;
  int level;
  int adr;
  char name[al];
} Symtab;

typedef struct {
  Opcode f;
  int l;
  int a;
} Instruction;

static int errors;
static int ch;      /*last character read */
static Symbol sym;  /* last symbol read */
static char id[al]; // last identifier read
static int num;     // last number read
static int cx;      // code allocation index
static int s[500];  // datastore
static Symtab table[100];
static Instruction code[cxmax];
static char *word[norw+1];  // keywords
static int wsym[norw+1];    // symbolically
static int ssym[128];       // char symbols
static char *mnemonics[n_opcodes];
static FILE *f;

void expression(int lev, int tx);

void error(char msg[]) {
  printf("\nerror: %s\n", msg);
  errors++;
}

void getch(void) {
    ch = fgetc(f);
    if (ch != EOF)
        printf("%c", ch);
}

void get_ident(void) {
    int i = 0;
    while (ch != EOF && isalnum(ch)) {
       if (i < al) {
          id[i] = (char)tolower(ch);
          i++;
       }
       getch();
    }
    id[i] = '\0';
    for (i = norw; i != 0 && strcmp(id, word[i]) != 0; i--)
      ;
    sym = wsym[i];
}

void get_number(void) {
    int i = 0;
    num = 0;
    sym = number;
    do {
         if (i >= nmax)
          error("This number is too large");
         num = 10 * num + (ch - '0');
         i++;
         getch();
    } while (ch != EOF && isdigit(ch));
}

void getsym(void) {
   while (ch <= ' ') {
      if (ch == EOF) {
        sym = period;
        return;
      }
      getch();
   }
   if (isalpha(ch)) {
      get_ident();
   } else if (isdigit(ch)) {
      get_number();
   } else if (ch == ':') {
      sym = colon;
      getch();
      if (ch == '=') {
         sym = becomes;
         getch();
      }
   } else if (ch == '<') {
      sym = lsssym;
      getch();
      if (ch == '=') {
         sym = leqsym;
         getch();
      } else if (ch == '>') {
         sym = neqsym;
         getch();
      }
   } else if (ch == '>') {
      sym = gtrsym;
      getch();
      if (ch=='=') {
         sym =geqsym;
         getch();
       }
   } else {
      sym = ssym[ch];
      getch();
   }
}

int gen(int x, int y, int z) {
    int cx0 = cx;
    if (cx>cxmax)
      error("Program too long");
    else {
      code[cx].f=x;
      code[cx].l=y;
      code[cx].a=z;
    }
    cx++;
    return cx0;
}

void gen_opr(Symbol op) {
    switch (op) {
      case eqlsym: gen(eql,0,0); break;
      case neqsym: gen(neq,0,0); break;
      case lsssym: gen(lss,0,0); break;
      case leqsym: gen(leq,0,0); break;
      case gtrsym: gen(gtr,0,0); break;
      case geqsym: gen(geq,0,0); break;
      case times:  gen(mul,0,0); break;
      case slash:  gen(dvd,0,0); break;
      case plus:   gen(add,0,0); break;
      case minus:  gen(sub,0,0); break;
      default: error("Unknown operator");
    }
}

void listcode(void) {
    int i;
    for (i=0;i<=cx-1;i++) {
      printf("%d ",i);
      if (code[i].f > jpc)
        error("Unknown operator");
      else {
          printf("%s", mnemonics[code[i].f]);
          if (code[i].f >= lit)
              printf(" %d %d\n", code[i].l, code[i].a);
          else
              printf("\n");
      }
    }
}

void enter(int k, int *ptx, int *pdx, int lev) {
   (*ptx)++;
   strcpy(table[*ptx].name, id);
   table[*ptx].kind = k;
   switch (k) {
      case constant: table[*ptx].val = num; break;
      case variable: table[*ptx].level = lev;
                     table[*ptx].adr = *pdx;
                     (*pdx)++;
                     break;
      case procedure:table[*ptx].level = lev; break;
      }
}

int position(char id[], int tx) {
    int i;

    strcpy(table[0].name, id);
    for (i = tx; strcmp(table[i].name, id) != 0; i--)
        ;
    return i;
}

int accept(Symbol s) {
    if (s != sym)
        return 0;
    getsym();
    return 1;
}

int expect(Symbol s, char msg[]) {
    if (accept(s))
        return 1;
    error(msg);
    return 0;
}

void factor(int lev, int tx) {
  int i;

  while (sym==ident||sym==number||sym==lparen) {
    if (sym==ident) {
      i=position(id,tx);
      if (i==0)
        error("Undeclared identifier");
      else {
        if (table[i].kind==constant)
            gen(lit,0,table[i].val);
        else if (table[i].kind==variable)
            gen(lod,lev-table[i].level,table[i].adr);
        else
            error("Expression must not contain a procedure identifier");
      }
      getsym();
    } else if(sym==number) {
      gen(lit,0,num);
      getsym();
    } else if(accept(lparen)) {
      expression(lev,tx);
      expect(rparen, "Right parenthesis missing");
    }
  }
}

void term(int lev, int tx) {
  int mulop;

  factor(lev,tx);
  while(sym==times||sym==slash) {
    mulop=sym;
    getsym();
    factor(lev,tx);
    gen_opr(mulop);
  }
}

void simpleexpression(int lev, int tx) {
  int addop;

  if (sym==plus||sym==minus){
    addop=sym;
    getsym();
    term(lev,tx);
    if (addop==minus)
        gen(neg,0,0);
  } else
    term(lev,tx);
  while (sym==plus||sym==minus) {
    addop=sym;
    getsym();
    term(lev,tx);
    gen_opr(addop);
  }
}

void expression(int lev, int tx) {
  int relop;

  simpleexpression(lev,tx);
  if (sym==eqlsym||sym==neqsym||sym==lsssym||sym==leqsym||sym==gtrsym||sym==geqsym) {
    relop=sym;
    getsym();
    simpleexpression(lev,tx);
    gen_opr(relop);
  }
}

void statement(int lev, int tx) {
  int i, cx1,cx2;

  if (accept(beginsym)) {
    statement(lev,tx);
    while(sym==semicolon||sym==whilesym||
            sym==ifsym||sym==callsym||sym==beginsym) {
      expect(semicolon, "Semicolon between statements is missing");
      statement(lev,tx);
    }
    expect(endsym, "'end' expected");
  } else if (accept(callsym)) {
    if (sym!=ident)
        error("Call must be followed by an identifier");
    else {
      i=position(id, tx);
      if(i==0)
        error("Undeclared identifier");
      else if (table[i].kind==procedure)
        gen(cal,lev-table[i].level, table[i].adr);
      else
        error("Call of a constant or a variable is meaningless");
      getsym();
    }
  } else if (sym==ident){
    i=position(id,tx);
    if(i==0)
        error("Undeclared identifier");
    else if (table[i].kind!=variable) {
      error("Assignment to constant or procedure is not allowed");
      i=0;
    };
    getsym();
    expect(becomes, "Assignment operator := expected");
    expression(lev,tx);
    if (i!=0)
      gen(sto, lev-table[i].level, table[i].adr);
  } else if (accept(ifsym)) {
     expression(lev,tx);
     expect(thensym, "'then' expected");
     cx1=gen(jpc,0,0);
     statement(lev, tx);
     code[cx1].a = cx;
  } else if (accept(whilesym)) {
    cx1=cx;
    expression(lev,tx);
    cx2=gen(jpc,0,0);
    expect(dosym, "'do' expected");
    statement(lev,tx);
    gen(jmp,0,cx1);
    code[cx2].a=cx;
  }
}

void constdeclaration(int lev, int *ptx, int *pdx) {
    if (accept(ident)) {
        if (sym==eqlsym || sym==becomes) {
            if (sym==becomes)
                error("Use = instead of :=");
            getsym();
            if (sym==number)
                enter(constant,ptx,pdx,lev);
            expect(number, "= must be followed by a number");
        } else
            error("Identifier must be followed by =");
    } else
        error("Const must be followed by an identifier");
}

void vardeclaration(int lev, int *ptx, int *pdx) {
    if (sym==ident)
        enter(variable, ptx,pdx,lev);
    expect(ident, "'var' must be followed by an identifier");
}

void block(int lev, int tx) {
  int dx = 3, tx0 = tx;

  table[tx].adr=cx;
  gen(jmp,0,0);
  if (lev>levmax)
    error("Nesting too deep");
  do {
    if (accept(constsym)) {
        do {
          constdeclaration(lev,&tx,&dx);
        } while (accept(comma));
        expect(semicolon, "semicolon missing");
    }

    if (accept(varsym)) {
        do {
          vardeclaration(lev,&tx,&dx);
        } while (accept(comma));
        expect(semicolon, "semicolon missing");
    }

    while (accept(procsym)) {
      if(sym==ident){
        enter(procedure,&tx,&dx,lev);
      }
      expect(ident, "'procedure' must be followed by an identifier");
      expect(semicolon, "semicolon missing");
      block(lev+1, tx);
      expect(semicolon, "semicolon missing");
    }
  } while (sym==constsym||sym==varsym||sym==procsym);

  code[table[tx0].adr].a=cx;
  table[tx0].adr=cx;
  gen(inc,0,dx);
  statement(lev,tx);
  gen(ret,0,0);
}

//find base l levels down
int base(int l, int b) {
  int b1 = b;
  while (l>0) {
    b1=s[b1];
    l--;
  }
  return b1;
}

void interpret(void) {
  int p,b,t; //program-, base-, topstack-registers
  Instruction i; // instruction register

  printf("start PL/0\n");
  t = p = 0;
  b = 1;
  s[1] = s[2] = s[3] = 0;
  do {
    i=code[p];
    switch (i.f) {
      case ret: t=b-1; p=s[t+3]; b=s[t+2]; break;
      case neg: s[t]=-s[t]; p++; break;
      case add: t--; s[t]=s[t]+s[t+1]; p++; break;
      case sub: t--; s[t]=s[t]-s[t+1]; p++; break;
      case mul: t--; s[t]=s[t]*s[t+1]; p++; break;
      case dvd: t--; s[t]=s[t]/s[t+1]; p++; break;
      case eql: t--; s[t]=(s[t]==s[t+1]); p++; break;
      case neq: t--; s[t]=(s[t]!=s[t+1]); p++; break;
      case lss: t--; s[t]=(s[t]<s[t+1]); p++; break;
      case leq: t--; s[t]=(s[t]<=s[t+1]); p++; break;
      case gtr: t--; s[t]=(s[t]>s[t+1]); p++; break;
      case geq: t--; s[t]=(s[t]>=s[t+1]); p++; break;
      case lit: t++; s[t]=code[p].a; p++; break; //lit
      case lod: t++; s[t]=s[base(code[p].l,b)+code[p].a]; p++; break;
      case sto: s[base(code[p].l,b)+code[p].a]=s[t];
              p++; /*printf("%d\n", s[t]);*/ t--; break;
      case cal: /* generate new block mark */
         s[t+1]=base(code[p].l,b); s[t+2]=b; s[t+3]=p+1;
         b=t+1; p=code[p].a; break;
      case inc: t=t+code[p].a; p++; break;
      case jmp: p=code[p].a; break;
      case jpc: if (s[t]==0) p=code[p].a; else p++;
              t--; break;
    }
  } while (p!=0);
  printf(" END PL/0\n");
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Program name required\n");
        exit(2);
    }
    f=fopen(argv[1],"r");
    if (f == NULL) {
        printf("Can't open %s\n", argv[1]);
        exit(2);
    }

    word[0]="";             wsym[0]=ident;
    word[1]="begin";        wsym[1]=beginsym;
    word[2]="call";         wsym[2]=callsym;
    word[3]="const";        wsym[3]=constsym;
    word[4]="do";           wsym[4]=dosym;
    word[5]="end";          wsym[5]=endsym;
    word[6]="if";           wsym[6]=ifsym;
    word[7]="procedure";    wsym[7]=procsym;
    word[8]="then";         wsym[8]=thensym;
    word[9]="var";          wsym[9]=varsym;
    word[10]="while";       wsym[10]=whilesym;

    ssym['+']=plus; ssym['-']=minus; ssym['*']=times; ssym['/']=slash;
    ssym['(']=lparen; ssym[')']=rparen; ssym['=']=eqlsym;
    ssym[',']=comma; ssym['.']=period; ssym[';']=semicolon;

    mnemonics[ret] = "ret"; mnemonics[ret] = "ret"; mnemonics[neg] = "neg";
    mnemonics[add] = "add"; mnemonics[sub] = "sub"; mnemonics[mul] = "mul";
    mnemonics[dvd] = "dvd"; mnemonics[eql] = "eql"; mnemonics[neq] = "neq";
    mnemonics[lss] = "lss"; mnemonics[geq] = "geq"; mnemonics[gtr] = "gtr";
    mnemonics[leq] = "leq"; mnemonics[lit] = "lit"; mnemonics[lod] = "lod";
    mnemonics[sto] = "sto"; mnemonics[cal] = "cal"; mnemonics[inc] = "inc";
    mnemonics[jmp] = "jmp"; mnemonics[jpc] = "jpc";

    ch=' ';
    getsym();
    block(0,0);
    if (sym!=period)
        error("Period expected");
    else {
        listcode();
        if (!errors)
            interpret();
    }
    return 0;
}
Find all posts by this user
Quote this message in a reply
04-26-2018, 01:51 AM
Post: #5
RE: Aritmetic evaluator - FB
Hi Ed

Yes i agree with you it should be a1 allowed
and i can change that because is usefull and easier to remember
var names like myvar1,myvar2...

Heh ,,AST yes it is awkward in fact it is just another
representation of code for easier evaluation ( i guess)
guy from code project do AST and also another guy from
freecode camp create AST to..
both of them use precedence climbing.

when i see this:
Code:
void factor(int lev, int tx) {
  int i;

  while (sym==ident||sym==number||sym==lparen) {
    if (sym==ident) {
      i=position(id,tx);
      if (i==0)
        error("Undeclared identifier");
      else {
        if (table[i].kind==constant)
            gen(lit,0,table[i].val);
        else if (table[i].kind==variable)
            gen(lod,lev-table[i].level,table[i].adr);
        else
            error("Expression must not contain a procedure identifier");
      }
      getsym();
    } else if(sym==number) {
      gen(lit,0,num);
      getsym();
    } else if(accept(lparen)) {
      expression(lev,tx);
      expect(rparen, "Right parenthesis missing");
    }
  }
}

void term(int lev, int tx) {
  int mulop;

  factor(lev,tx);
  while(sym==times||sym==slash) {
    mulop=sym;
    getsym();
    factor(lev,tx);
    gen_opr(mulop);
  }
}

. then i know that is the recursive descent
by the way i am not sure which one is faster for direct
tokens-evaluation ?
I will try to use/modify Charles expression eval for ANI
here is:

Code:
function evalnm(sys *dp, double *v,sys b)
=========================================
b-=48
if dp=0
  v=v*10+b
else
  dp*=10
  v=v+b/dp
end if
end function


function evalop(sys op, double *a,v)
====================================
select op
case 0   : a=v
case "+" : a+=v
case "-" : a-=v
case "*" : a*=v
case "/" : a/=v
'case
end select
end function


function eval(string s) as double
=================================
byte b at (strptr s) 'source string
double a       'accum
double v       'value
sys    op      'operator
sys    ai      'accum index
sys    si      'stack index
sys    vi      'variable index
sys    dp      'decimal point
do
  select b
  case 0          : evalop(op,a,v) : return a
  case 10 to 13   : evalop(op,a,v) : vv[ai]=a : a=0 : v=0 : op=0 : dp=0
  case ":"        : evalop(op,a,v) : vv[ai]=a : a=0 : v=0 : op=0 : dp=0
  case "0" to "9" : evalnm(dp,v,b)
  case "A" to "Z" : vi=lookupv(@@b) : v=vv(vi) : dp=0
  case "a" to "z" : vi=lookupv(@@b) : v=vv(vi) : dp=0
  case "="        : ai=vi
  case "."        : dp=1
  case 42 to 47   : evalop(op,a,v) : op=b : v=0 : dp=0
  case "("        : st[si]=a : sp[si]=op : a=0 : v=0 : op=0 : dp=0 : si++
  case ")"        : evalop(op,a,v) : si-- : v=a : a=st[si] : op=sp[si] : dp=0
  end select
  @b++
end do
end function

print eval("av=32 : bv=16.25 : 2*(av+bv) ") '96.5
oif course i will try to remove tokenized part
because eveluator must interpret tokens array
Find all posts by this user
Quote this message in a reply
04-26-2018, 02:22 AM
Post: #6
RE: Aritmetic evaluator - FB
(04-26-2018 01:51 AM)Aurel Wrote:  ...
by the way i am not sure which one is faster for direct
tokens-evaluation ?

It depends on how they are implemented, and the language they are implemented in.

Theoretically, precedence climbing should be faster, as there isn't as much recursion. This article touches on that: http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

In practice, it probably won't make that much of a difference. Most expressions are simple enough that the recursion doesn't become a factor.

For direct evaluation, the speed is greatly influenced by the speed of your lexer. If you are re-parsing each statement over and over (e.g., no intermediate code), you better make sure you lexer is super fast.

That is why in many compiler texts they created enums for all tokens, instead of just using strings. In most languages, it is _much_ faster to compare integers than to compare strings.

But the best way to know for sure is to bench-mark it. Create a sample input file with millions of records, and run it through your lexer. Change your lexer, and try it again. It is kind of fun to come up with the fastest code you can.
Find all posts by this user
Quote this message in a reply
04-26-2018, 02:32 AM
Post: #7
RE: Aritmetic evaluator - FB
Ed
I have in plan to parse once...
I mean tokenize code just one time to
array of tokens..
when is that part finished then
execute or evaluate tokens.
I think that then i don't need to reparse again .
Also probably i would need some sort of stack operations.
As you know i use oxygen ( don't blame me) Big Grin
and as you know o2 have strange problems with strings which
you cannot found in any other language ( i think)
but from the other side i already know o2 quirks.
Do you agree with that .?
Find all posts by this user
Quote this message in a reply
04-26-2018, 03:39 AM (This post was last modified: 04-26-2018 03:40 AM by Ed Davis.)
Post: #8
RE: Aritmetic evaluator - FB
(04-26-2018 02:32 AM)Aurel Wrote:  Ed
I have in plan to parse once...
I mean tokenize code just one time to
array of tokens..
when is that part finished then
execute or evaluate tokens.
I think that then i don't need to reparse again .
Also probably i would need some sort of stack operations.
...
Do you agree with that .?

Yes and no.

You can't just evaluate tokens. You have to parse them.

For instance, say you have the following code:

Code:
if a = b then
    do_something()
else
    do_something_else()
end if

Your token stream might be:

Code:
if
ident, 'a'
equal
ident, 'b'
ident, 'do_something'
else
ident, 'do_something_else'
endif

You cannot just evaluation those tokens. You have to parse them, as in:

Code:
case IF:                        /* "if" <expression> <statement> */
    next_sym();
    if (expression()) {
        stmts();
        if (accept(ELSE)) {
            skip_stmts();       /* skip else part */
        }
    } else {
        skip_stmts();           /* skip until "else" */
        if (accept(ELSE)) {     /* ... "else" <statement> */
            stmts();
        }
    }
    expect(ENDIF);
    break;

And then expression(), stmts() and skip_stmts() all have to parse and then evaluate the tokens.

So Yes, creating a stream of tokens one time is much faster, but parsing and evaluating those tokens will still be much slower than using some intermediate form (e.g., AST, byte-code, quads, etc). But it is definitely a good start.

In my tests:

Byte code interpreter, highly optimized: 8 to 25 times slower than native code.

Byte code interpreter, no attempt to optimize byte code: 30 to 100 times slower than native code.

AST interpreter 50 to 100 times slower than native code.

Tokenized interpreter (e.g., lexing only once): 140 to 500 times slower than native code.

Pure interpreter: 1000 or more times slower than native code.

In conclusion: Go for it! After all, it is all about coding, creating stuff, and having fun!
Find all posts by this user
Quote this message in a reply
04-26-2018, 04:11 AM (This post was last modified: 04-26-2018 04:29 AM by Aurel.)
Post: #9
RE: Aritmetic evaluator - FB
Quote:You cannot just evaluation those tokens. You have to parse them, as in:

Yes Ed you have a right about that.
Still should be faster than i do in ruben interpreter.
But what if i transform all token commands into integers like this :

" if " -> 20
"else" -> 30
"endif "-> 40

and then in interpreter just read this integers in loop

do

select iTok

case 20

compare (lhs,rhs)
if true continue
if iTok=30 then skipCode

....
,,,,

That is mine silly idea.
What you think about that mumbo-jumbo method ?
...and Ed what is a quads ?
Find all posts by this user
Quote this message in a reply
04-26-2018, 04:44 AM (This post was last modified: 04-26-2018 04:45 AM by Ed Davis.)
Post: #10
RE: Aritmetic evaluator - FB
(04-26-2018 04:11 AM)Aurel Wrote:  
Quote:You cannot just evaluation those tokens. You have to parse them, as in:

Yes Ed you have a right about that.
Still should be faster than i do in ruben interpreter.
But what if i transform all token commands into integers like this :

" if " -> 20
"else" -> 30
"endif "-> 40

and then in interpreter just read this integers in loop

do

select iTok

case 20

compare (lhs,rhs)
if true continue
if iTok=30 then skipCode

....
,,,,

That is mine silly idea.
What you think about that mumbo-jumbo method ?

That is what I assumed you were going to do - use numbers. That is what my example used. In my example, IF maps to 1, ELSE to 2, ENDIF to 3, WHILE to 4, and so on. They use enums - constants in some languages.

Show me your tokens and then pseudo code to process:
Code:
if a = b then
    x = 4
    y = 2
else
    x = 3
    y = 1
end if

Quote:...and Ed what is a quads ?

Just another intermediate form. See: https://www.tutorialspoint.com/compiler_...ations.htm for more information.
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


User(s) browsing this thread: