2. Add/Subtract

I hope the last explanations made sense. Let's expand on what we've already done, including addition and subtraction, now.

Addition and Subtraction

What would a general specification look like for addition and subtraction? How about something like this?

expression := term | expression + term | expression - term
term := number | ( expression )

The second production above, term, recalls our earlier production for expression. But instead of referring to itself within the parens, that entry now links over to a new production (the first production mentioned above) designed to cover addition and subtraction and also, of course, a simple term.

Notice how these two productions refer to each other and let's now follow a path dictated by the logic of our productions, so that we can see how it works. Here are a few possible text expressions, together with the applied production rules:

5               := expression
                :=    term
                :=   number

( 6 )           :=   expression
                :=      term
                := ( expression )
                := (    term    )
                := (   number   )

2 + 3           :=     expression
                := expression + term
                :=    term    + term
                :=   number   + term
                :=   number   + number

2 - 3           :=     expression
                := expression - term
                :=    term    - term
                :=   number   - term
                :=   number   - number

2 - 3 - 5       :=             expression
                :=     expression      -  term
                := expression -  term  -  term
                :=    term    -  term  -  term
                :=   number   -  term  -  term
                :=   number   - number -  term
                :=   number   - number - number

2 - ( 3 - 5 )   :=         expression
                := expression -          term
                :=    term    -          term
                :=   number   -          term
                :=   number   - (     expression      )
                :=   number   - ( expression -  term  )
                :=   number   - (    term    -  term  )
                :=   number   - (   number   -  term  )
                :=   number   - (   number   - number )

You should try this out with a lot more examples to see if it always appears to work out satisfactorily. You can read this in reverse order to how I listed them, too -- grouping them back up to the abstract expression. For example, in the next-to-last example, you can simply see that it is a number, minus, number, minus, and number. Then, looking at the productions, you can see that a number can also be an term, so you make that adjustment to all of them. Then, you can see that an term can be an expression, so you change the first one. That allows the expression, the plus, and the term to be seen as just an expression, itself. And so on.

Make sure you feel comfortable with this, working through a few examples on your own until you feel you are ready to continue.

Coding?

Well, let's try our hand at a version that replications our productions at the top of the page, here. You will note that the function called Term is very similar to the function called Expression we worked out on the previous page. Here is a first cut:

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

    DIM status AS INTEGER

        LET status = Term(eqpos, eq)
        IF NOT status THEN
            LET status = Expression(eqpos, eq)
            IF status THEN
                SkipSpaces eqpos, eq
                IF Match("+", eqpos, eq) THEN
                    LET status = Term(eqpos, eq)
                ELSEIF Match("-", eqpos, eq) THEN
                    LET status = Term(eqpos, eq)
                ELSE
                    LET status = 0
                END IF
            END IF
        END IF

    LET Expression = status

END FUNCTION

FUNCTION Term% (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 Term = status

END FUNCTION

This example shows that Expression function (which emulates the expression production) first tries to see if the term production fits -- just as shown in the first entry of that production. If it does, then it quits with a successful status. If not, it goes on to try and fit the expression production (itself), then either a plus or minus character, then finally an term production.

However, there is a big problem. If we try the equation, 5+3, the first test made by calling the function Term will match the value 5 and yield success because it is a number. Thus Expression will suddenly quit saying it was successful, but it will do so without ever bothering to check the rest of the equation. So, if we supply 5*3, which shouldn't be a valid production just yet, it will still return successful because once it find that Term works, it's just done. It doesn't check the other alternatives, first.

Bad news. So, let's re-arrange this so that Expression is checked first. That way, maybe, we'll only check Term after all else has failed. (I'll just provide the changes to the Expression function here and leave out the Term function, since it is already shown above):

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

    DIM status AS INTEGER

        IF Expression(eqpos, eq) THEN
            SkipSpaces eqpos, eq
            IF Match("+", eqpos, eq) THEN
                LET status = Term(eqpos, eq)
            ELSEIF Match("-", eqpos, eq) THEN
                LET status = Term(eqpos, eq)
            ELSE
                LET status = 0
            END IF
        ELSE
            LET status = Term(eqpos, eq)
        END IF

    LET Expression = status

END FUNCTION

Now, at least, we won't get a false-positive from trying Term first. But now we've got another problem. It's that we call Expression right away. But that's a recursive call. So, on entry to Expression, it calls Expression; which calls Expression; which calls Expression... Etc. This will bring a computer to its knees and either kill or crash the program. We never get a chance to actually see if an expression production fits, because it keeps calling itself to find out.

We've got a serious problem here -- infinite recursion.

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