### Author Topic: Operator precedence algorithm for compiler  (Read 6558 times)

0 Members and 1 Guest are viewing this topic.

#### Charles Pegge

• Global Moderator
• Hero Member
• Posts: 670
##### Operator precedence algorithm for compiler
« on: August 01, 2008, 11:18:48 AM »
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
continue with next op pair
end if

otherwise
apply operator and operand to accummulator
continue with next op pair

#### Charles Pegge

• Global Moderator
• Hero Member
• Posts: 670
##### Re: Operator precedence algorithm for compiler
« Reply #1 on: August 01, 2008, 01:26:19 PM »
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]
`#COMPILE EXE#DIM ALLDECLARE FUNCTION nword(BYREF s AS STRING, BYREF i AS LONG) AS STRINGDECLARE FUNCTION compile_expr(s AS STRING, i AS LONG) AS STRINGGLOBAL lct,swd,dtf,ascw,ncase,lowercase AS LONG ' word flagsFUNCTION 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 precedenceFUNCTION 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=tEND FUNCTION'GET NEXT WORDFUNCTION 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=wrEND FUNCTION`
« Last Edit: August 05, 2008, 12:58:08 PM by Charles Pegge »