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

Bean · 2011-02-02 07:36

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

David Betz · 2011-02-02 07:38

Well, I'm not Mike of course but I believe he just uses recursive function calls to parse and evaluate expressions. This is the same technique that is used by my xbasic interpreter. You essentially have one function for each level of operator precedence and call lower level functions recursively to parse the operands of each operator.

Bean · 2011-02-02 07:40

The last time I looked at the FemtoBasic code, I only remember seeing two level. That's why I'm confused. I can't do recursion with PropBasic. I don't think spin can either (can it ?).

Bean

David Betz · 2011-02-02 07:44

The expression evaluator is in the functions factor, shifts, bitFactor, bitTerm, term, arithExpr, compare, logicNot, logicAnd, expr. Starting with expr, each calls the previous to implement operator precedence.

Mike Green · 2011-02-02 08:09

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.

Bean · 2011-02-02 08:28

Okay,
Thanks Mike. I must have missed or forgotten about that post.

Bean

David Betz · 2011-02-02 08:51

Bean: Is there some reason why you can't do recursive descent expression parsing in your embedded basic? Is there support for recursive function calls in PropBasic?

Bean · 2011-02-02 09:12

David,
No. PropBasic does CALLs the same way as PASM. So no recursion.

Bean

David Betz · 2011-02-02 09:18

Okay, now I understand why you're looking for a non-recursive solution. I'm intrigued by the shunting yard algorithm as well. I can do recursive calls in C but I'd like my compiler to run on space constrained systems where recursion might be risky. Better to have an explicit stack where you can do bounds checking.

Heater. · 2011-02-02 09:50

No reason you can't do some bounds checking when using the recursive solution, just increment and decrement a counter as you enter and leave the recurring functions and check for max depth as you go.

David Betz · 2011-02-02 09:57

True but then you need to be very careful of how you set that max depth to make sure it really matches the actual stack size. And you need to adjust it if you port to a different platform with different memory sizes.

Bean · 2011-02-03 06:51

Mike,
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

Mike Green · 2011-02-03 07:24

Yes, it's legal to have A * - B or C * + D

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.

Bean · 2011-02-03 07:26

Okay, that makes sense.
Thanks Mike.

Bean

Bean · 2011-02-03 11:46

Okay, Thanks much Mike.

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

Bean · 2011-02-04 05:14

What precedence should functions have ? Like PEEK and RND ?

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

Mike Green · 2011-02-04 06:35

RND would be a unary operator and, most commonly, these have high precedence, so "RND 5+10" is equivalent to "(RND 5)+10"

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

Duane C. Johnson · 2011-02-04 09:10

Hi Mike;

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

Mike Green · 2011-02-04 10:03

Please do not hijack someone else's thread. If you have a question unrelated to an existing thread, start your own thread.

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.

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

Comments