Mike Green, Can you explain how FemtoBasic does expression evaluation ?

Mike,
I'm working on an embedded basic for the propeller that is written in PropBasic (for fast speed).
http://forums.parallax.com/showthread.php?123678-Embedded-BASIC-interpreter
I am a confused about how to write the expression evaluator. Right now it works strictly from left to right.
Can you explain a little how FemtoBasic does it's expression evaluation ?
Thanks,
Bean
I'm working on an embedded basic for the propeller that is written in PropBasic (for fast speed).
http://forums.parallax.com/showthread.php?123678-Embedded-BASIC-interpreter
I am a confused about how to write the expression evaluator. Right now it works strictly from left to right.
Can you explain a little how FemtoBasic does it's expression evaluation ?
Thanks,
Bean
Comments
Bean
I posted the scheme for an expression evaluator using two stacks (data and operator) and no recursive calls in your embedded Basic thread starting at post #6. Have a look at that. It's really pretty straightforward. Try it on paper. This scheme is what's taught (or used to be taught) in most introductory compiler courses.
As David mentioned, FemtoBasic uses a recursive descent parser for expressions which uses the Spin call stack instead of an explicit operator stack. Expr is the main routine for FemtoBasic's expression evaluation. It returns the value of the expression that should be next in the input line and it handles a sequence of OR operators. Similarly, logicAnd handles a sequence of AND operators, logicNot handles the unary NOT, compare handles a sequence of comparison operators, arithExpr handles the binary addition operators (+ and -), etc. The recursion comes in where the factor function calls expr to handle an expression within parentheses.
Thanks Mike. I must have missed or forgotten about that post.
Bean
No. PropBasic does CALLs the same way as PASM. So no recursion.
Bean
I think I got it working, but I'm not sure how to implement unary minus. Would I check if the last push was to the operator stack ? Is it legal to do 5*-3 ?
DEVICE P8X32A, XTAL1, PLL16X FREQ 80_000_000 ' Values stack Values HUB LONG(100) ValuesPos VAR LONG = -1 ' Operations stack Ops HUB BYTE(100) OpsPrec HUB BYTE(100) OpsPos VAR LONG = -1 ' General variables Value1 VAR LONG Value2 VAR LONG Ascii HUB STRING(20) ' Subroutines PushValue SUB 1 PopValue FUNC 0 PushOp SUB 2 ' Operator, Precedence ShowAll SUB 0 PROGRAM Start Start: ' Initialize TX pin HIGH 30 ' Give user time to start PST PAUSE 5000 ' Evaluate 30+12*6+50/(2+3) = 112 PushValue 30 ShowAll PushOp "+", 10 ShowAll PushValue 12 ShowAll PushOp "*", 11 ShowAll PushValue 6 ShowAll PushOp "+", 10 ShowAll PushValue 50 ShowAll PushOp "/", 11 ShowAll PushOp "(", 0 ShowAll PushValue 2 ShowAll PushOp "+", 10 ShowAll PushValue 3 ShowAll PushOp ")", 0 ShowAll PushOp ",", 0 ShowAll END ' ----------------------------------------- SUB PushValue INC valuesPos WRLONG Values(ValuesPos), __param1 ENDSUB FUNC PopValue RDLONG Values(ValuesPos), __param1 DEC ValuesPos RETURN __param1 ENDFUNC SUB PushOp ' Operator, Precedence newOp VAR LONG newPrec VAR LONG newOp = __param1 newPrec = __param2 IF newOp <> "(" THEN IF OpsPos >= 0 THEN DO IF newOp <> ")" THEN ' Peek at top operator precedence RDBYTE OpsPrec(OpsPos), __param3 IF newPrec >= __param3 THEN EXIT ENDIF RDBYTE Ops(OpsPos), __param3 DEC OpsPos IF __param3 = "(" AND newOp = ")" THEN EXIT ENDIF Value2 = PopValue Value1 = PopValue IF __param3 = "+" THEN Value1 = Value1 + Value2 ELSEIF __param3 = "-" THEN Value1 = Value1 - Value2 ELSEIF __param3 = "*" THEN Value1 = Value1 * Value2 ELSEIF __param3 = "/" THEN Value1 = Value1 / Value2 ENDIF PushValue Value1 LOOP UNTIL OpsPos < 0 ENDIF ENDIF IF newOp <> "," AND newOp <> ")" THEN ' Save op on stack INC OpsPos WRBYTE Ops(OpsPos), newOp WRBYTE OpsPrec(OpsPos), newPrec ENDIF ENDSUB SUB ShowAll IF OpsPos >= 0 THEN FOR __param1 = 0 TO OpsPos RDBYTE Ops(__param1), __param2 SEROUT 30, T115200, __param2 NEXT ENDIF IF ValuesPos >= 0 THEN FOR __param1 = 0 TO ValuesPos RDLONG Values(__param1), __param2 ascii = STR __param2, 5, 3 SEROUT 30, T115200, ascii NEXT ENDIF SEROUT 30, T115200, 13 ENDSUB
Bean
You check for a unary operator by having a Boolean flag that gets set whenever the scanner / parser sees an operator and cleared when it sees a constant or variable. It's set at the beginning of a statement, after most keywords or an open parenthesis or subscript bracket. It's cleared after a closing parenthesis or closing subscript bracket. When the scanner / parser is starting to classify something as an operator, this flag is used to tell whether it's unary or not.
Thanks Mike.
Bean
I think I got it all working.
I was surprised, the actual expression evaluator really isn't that much code.
This program shows it's progress on PST (Parallax Serial Terminal) at 115200 baud.
If anyone has time to check some expressions and let me know if you find anything wrong I would appreciate it.
The next step is to incorporate this code into the Embedded Basic program.
Bean
For example how should "IF RND 5+10 = value THEN" work ? Should it do the addition first, then RND 15, or should it do the RND 5 and then add 10 ?
And can someone explain "Associativity" ???
Bean
Associativity applies to binary operators. If you have "a - b - c" and the subtraction is left associative, you get "(a - b) - c". If it were right associative, you'd get "a - (b - c)" which is not what you want.
The Wikipedia is your friend: here
Help, I can't get it to work.
I have just made 2 versions of the PropStick on a plug board.
No peripherals connected to porta except for the EEPROM and serial.
They run great in all ways running PropForth so I know their wired
correctly.
I'm loading DongleBasic.spin to the EEPROM.
It runs and communicates well with TeraTerm3.13.
The problem is I can't get outa nor ina to do anything.
outa [1]=1
should set pin 1 to output and set it to hi.
However, the pin remains as an input.
All 28 pins remain as inputs except for pins 10 to 12 which
are outputting highs no mater what I try.
What am I doing wrong?
Duane
(651)426-4766
DongleBasic works. OUTA works, but, when the Basic program ends and you get "OK", any output pins from 0-15 are reset to inputs. Try entering something like
100 OUTA[ 1 ] = 1
110 PAUSE 10000
RUN
This sets I/O pin 1 to output high, lets it stay that way for 10 seconds, then the program ends and the I/O pin gets set back to input mode.
I don't know why pins 10 to 12 output high. There's no reason in DongleBasic for these pins to be treated any differently from any other I/O pins. I suspect there's some kind of hardware problem.