5. Powers

Back Home Up Next

I'm going to finish up this look at parsing expressions by adding in powers of numbers. That should give us a fairly useful expression parser.

Powers

Without further ado and without bothering with left-recursive forms that we'd just throw away, let's look at a right-recurive version of productions needed to evaluate an expression:

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

Again, I recommend that you carefully work through these productions and make sure you understand and agree with them. Test them out on paper with some sample expressions. Just in case ...

A Practice Walkthrough

I'll work one out, right now, just so you can see what I mean.

-2 * ( 5 + 6 ) ^ 2

This one should capture the essence, well. So, let's walk through it. First thing is that we consider our equation to be an expression, so:

expression

Now, an expression only has one option, namely:

term moreterms

So, that's what it is. Since we work left to right, we next see that term is again only one option. Expanding that, we get:

factor morefactors moreterms

Once again, we continue from the left and see that factor has only one option. Expanding it, we get:

item moreitems morefactors moreterms

Now, finally, we're getting to something that doesn't have only one option to select. item has two options. Examining our expression, it's clear that it doesn't start with an open paren. So that means the second option for item is selected. Expanding, we get:

number moreitems morefactors moreterms

We haven't yet defined precisely what a number is, because I said I'd get to that later on. So, let's cheat a little at this point and just recognize that number matches -2, well. I'll denote this by underlining that production:

  -2 * ( 5 + 6 ) ^ 2
  number moreitems morefactors moreterms

Since we've satisfied number, we can proceed to the next unresolved entry, namely moreitems. Again, this has more than one option. However, since there's no way it matches the first one, we have to select the second -- which is nothing at all. In other words, moreitems is also now matched. This gives:

-2 * ( 5 + 6 ) ^ 2
number moreitems morefactors moreterms

Now, we come to <morefactors>. It turns out that the first option here appears to match the next character of the remaining part of the expression. So that option is selected. The expansion now becomes:

-2 * ( 5 + 6 ) ^ 2
number moreitems * factor morefactors moreterms

Looking now at factor, there's only one option, so:

-2 * ( 5 + 6 ) ^ 2
number moreitems * item moreitems morefactors moreterms

I think you get the idea. Here's the rest of the steps:

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( expression ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( term moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( factor morefactors moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( item moreitems morefactors moreterms ) moreitems morefactors
           moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors moreterms ) moreitems morefactors
           moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors moreterms ) moreitems morefactors
           moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors moreterms ) moreitems morefactors
           moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + term moreterms ) moreitems
           morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + item moreitems morefactors
           moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) ^ item moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) ^ number moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) ^ number moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) ^ number moreitems morefactors moreterms

-2 * ( 5 + 6 ) ^ 2
number moreitems * ( number moreitems morefactors + number moreitems morefactors
           moreterms ) ^ number moreitems morefactors moreterms

And that completes it. The expression is quite valid and our set of productions worked fine.

Coding?

Well, it's time to recode this up again and, once again, I've renamed some routines to fit our production rules at the top of this page:

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

END FUNCTION

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

    DIM status AS INTEGER

        LET status = Item(eqpos, eq)
        DO WHILE status
            SkipSpaces eqpos, eq
            IF Match("^", eqpos, eq) THEN
                LET status = Item(eqpos, eq)
            ELSE
                EXIT DO
            END IF
        LOOP

    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_05.ZIP or EQ_05.BAS
An example program that will accept the sum and product expressions, along with powers!

 

Last updated: Saturday, January 14, 2006 00:02