4. Times/Divide

It's time to add in multiplication and division.

Multiplication and Division

Here's a shot at it with those nasty left-recusion form of productions:

element := number | ( expression )
term := element | term * element | term / element
expression :=  term | expression + term | expression - term

Of course, we can't use them in this form. But it may help to see them, anyway.

There's a new thing going on here, now -- binding priority. We want the multiplication and division to take place before any addition or subtraction, in the absence of parenthesis. (Or, we will if we ever get around to actually calculating values.) So, initially, we start out considering every algebriac expression as an expression. An expression can then be some combination of plus and minus terms, not times and divide -- not yet, anyway. Only in a term do we find multiplication and division. By layering the productions this way we can achieve the priority we want.

Look at a possible example and see if you can see how it matches up with the above productions::

2 + 6 * 5 - 5 / 3

Since we already know those productions are going to be a problem, I won't bother breaking it down, step by step. Hopefully, you can see that it probably works ... except for the left-recusion problem.

So, let's just hop over to a right-recursive form we can use to code a useful predictive recursive descent parser. (What a mouthful, eh?)

morefactors :=  * factor morefactors | / factor morefactors | <null>
factor := ( expression ) | number
moreterms := + term moreterms | - term moreterms | <null>
term : factor morefactors
expression := term moreterms

Take a close look at the above productions. The basic idea is that an expression is groups of things added and subtracted from each other and that each of those things are groups of still other things multiplied or divided together. By thinking this way, the multiplications and divisions are automatically given priority over additions and subtractions.

You may also notice the similarity of the new productions. I've again renamed them, though. I hope you won't mind. In any case, there's a pattern here you can recognize.

Coding?

Well, I think you can probably guess about how we might code up something to fit the above productions:

FUNCTION Factor% (eqpos AS INTEGER, eq AS STRING)

    DIM status AS INTEGER

        SkipSpaces eqpos, eq
        IF Match("(", eqpos, eq) THEN
            LET status = Expression(eqpos, eq)
            IF status THEN
                SkipSpaces eqpos, eq
                LET status = Match(")", eqpos, eq)
            END IF
        ELSE
            LET status = Number(eqpos, eq)
        END IF

    LET Factor = status

END FUNCTION

FUNCTION Term% (eqpos AS INTEGER, eq AS STRING)

    DIM status AS INTEGER

        LET status = Factor(eqpos, eq)
        DO WHILE status
            SkipSpaces eqpos, eq
            IF Match("*/", eqpos, eq) THEN
                LET status = Factor(eqpos, eq)
            ELSE
                EXIT DO
            END IF
        LOOP

    LET Term = status

END FUNCTION

FUNCTION Expression% (eqpos AS INTEGER, eq AS STRING)

    DIM status AS INTEGER

        LET status = Term(eqpos, eq)
        DO WHILE status
            SkipSpaces eqpos, eq
            IF Match("+-", eqpos, eq) THEN
                LET status = Term(eqpos, eq)
            ELSE
                EXIT DO
            END IF
        LOOP

    LET Expression = status

END FUNCTION

I've prepared a newly modified source file to illustrate:

EQ_04.ZIP or EQ_04.BAS: An example program that will accept the sum and product expressions.

Let's finish this up, adding in powers.

Last updated: Friday, January 13, 2006 23:59