This is a basic algorithm for applying operator precedence when evaluating an expression.
example:
a + b * c - d
a + (b *c) - d
pseudocode:
We have an accummulator, an operand register, a stack.
A series of operator-operand pairs form the expression to be processed
reapeat until end of expression
get operator and operand pair
and get the next operator after these to compare precedence
if no operand then end expression
if no operator specified then operator=load
if operators are present on stack
compare pushed operator with this operator
if precedence equal or greater then
transfer accummulator to operand register
pop operator
pop accummulator
apply operator and operand to accummulator
continue with current op pair
end if
end if
compare next operator with this operator
if precedence grater then
push accumulator
push this operator
load operand to accumulator
continue with next op pair
end if
otherwise
apply operator and operand to accummulator
continue with next op pair
This is a simple model implementing the precedence algorithm:
- compiles to assembler source code using the FPU, assuming the variables are all double precision.
the nword function is a word reader, to support the operation.
PowerBasic
#COMPILE EXE
#DIM ALL
DECLARE FUNCTION nword(BYREF s AS STRING, BYREF i AS LONG) AS STRING
DECLARE FUNCTION compile_expr(s AS STRING, i AS LONG) AS STRING
GLOBAL lct,swd,dtf,ascw,ncase,lowercase AS LONG ' word flags
FUNCTION PBMAIN () AS LONG
DIM s AS STRING
'
s="a + b * c - d"
'
MSGBOX s+$CR+$CR+compile_expr(s,1)
END FUNCTION
' Compile expression using operator precedence
FUNCTION compile_expr(s AS STRING, i AS LONG) AS STRING
LOCAL w,op,np,ins,t AS STRING
LOCAL prec,stk AS LONG
' stack arrays
DIM sprec(15) AS LONG ' precedence
DIM sop(15) AS STRING ' operator
DO
w=nword(s,i)
IF w="" THEN EXIT DO
op="":ins=""
IF w="+" THEN op="fadd qword ":prec=5
IF w="-" THEN op="fsub qword ":prec=5
IF w="*" THEN op="fmul qword ":prec=6
IF w="/" THEN op="fdiv qword ":prec=6
IF LEN(op) THEN w=nword(s,i)
IF op="" THEN op="fld qword ":prec=7
np=nword(s,i) ' next operator
IF (stk>0)AND(sprec(stk-1)>=prec) THEN
DECR stk
ins= _
"fst qword [esi]"+$CR _
+"fld qword ptr [esi-8]"+$CR _
+sop(stk)+"[esi]"+$CR _
+ "sub esi,8"+$CR
END IF
i=swd ' restore reader position
IF ((np="*")OR(np="/"))AND(prec<6) THEN
ins= _
"fstp qword [esi]"+$CR _
+"add esi,8"+$CR
sprec(stk)=prec:sop(stk)=op: op="fld qword "
INCR stk
END IF
t=t+ins+op+w+$CR
LOOP
FUNCTION=t
END FUNCTION
'GET NEXT WORD
FUNCTION nword(BYREF s AS STRING, BYREF i AS LONG) AS STRING
' s source
' i position in source
' swd start of word position
' a ascii code
' b general purpose
' wr word
LOCAL a,b,v AS LONG
DIM wr AS STRING
DO ' skip leading white space and blank lines
a=ASC(s,i)
IF a<=0 THEN EXIT DO
'if a=10 then lct+=1
IF a>32 THEN EXIT DO
INCR i
LOOP
swd=i:dtf=0
ascw=a
DO
a=ASC(s,i)
IF a<33 THEN EXIT DO
INCR i
IF (a=34)OR(a=39)OR(a=96) THEN
IF i>swd+1 THEN EXIT DO ' as terminating symbol
b=a
DO
a=ASC(s,i)
INCR i
IF (a=b)OR(a=0) THEN EXIT DO
LOOP
a=ASC(s,i)
IF a<>46 THEN EXIT DO
END IF
IF a=46 THEN
IF dtf=0 THEN dtf=i-swd
ITERATE
END IF
IF (a>96)AND(a<123) THEN ITERATE
IF (a>64)AND(a<91) THEN ITERATE
IF (a>47)AND(a<58) THEN ITERATE
IF (a=35)OR(a=95) THEN ITERATE ' # _
IF a>126 THEN ITERATE ' higher ascii
IF i>swd+1 THEN DECR i' symbol as delimiter
EXIT DO
LOOP
wr=MID$(s,swd,i-swd)
IF (ncase AND lowercase) THEN
IF b=0 THEN wr=LCASE$(wr)
END IF
FUNCTION=wr
END FUNCTION