Operator precedence algorithm for compiler

[Charles Pegge]

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

[Charles Pegge]

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

Code Select Expand


#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