     Context-free Grammar Exploration : Polynomials Leave Comment
I read a pretty cool project idea the other day where you're to read in some polynomial and do operations on it. I figured that this is a pretty nice project to apply my newly acquired knowledge of grammars on. It might be overkill, but it'll be fun none the less.

A polynomial of degree n of one variable is a function of the form: f(x) = anxn + an-1xn-1 + ... + a2x2 + a1x + a0 where a ∈ ℝ

For example, we might have: f(x) = 3x3 + 9x2 + x + 4. We might also have 2.5x5 + 8x3. Or even (1/3)x2. It's versatile, so there's going to need to be some thought put into how it's parsed.

This post will only be concerned with the grammar. Let's get started.

Context-free Grammar

Context-free Grammar said:

A context-free grammar is a 4-tuple (V, Σ, R, S) where
• V is a finite set called the variables
• Σ is a finite set, disjoint from V, called the terminals
• R is a finite set of rules, with each rule being a variable and a string of variables and terminals.
• S ∈ V is the start variable.

Now, we don't have to define the grammar so rigorously. We can simply construct rules with a lefthand side (LHS) and -> and righthand side (RHS) such that some string w may be derived from the rules. Let's consider the coefficient first.

Possible values are (positive, negative) (integer, real). We won't support fractions, or roots, or constants like e and pi.

Let's define coefficient to be:

coefficient -> INT | REAL
INT -> - DIGIT DIGIT* | DIGIT DIGIT*
REAL -> - DIGIT DIGIT* . DIGIT DIGIT* | DIGIT DIGIT* . DIGIT DIGIT*
DIGIT-> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Let's debug a bit, and make sure this is right.

5 = coefficient -> INT -> DIGIT DIGIT* -> 5
5.0 = coefficient -> REAL -> DIGIT DIGIT* . DIGIT DIGIT* -> 5 DIGIT* . DIGIT DIGIT* -> 5 . DIGIT DIGIT* -> 5 . 0 DIGIT* -> 5.0
-5 = coefficient -> INT -> - DIGIT DIGIT* -> - 5 DIGIT* -> -5
-5.3 = coefficient -> REAL -> - DIGIT DIGIT* . DIGIT DIGIT* -> - 5 DIGIT* . DIGIT DIGIT* -> - 5 . DIGIT DIGIT* -> - 5 . 3 DIGIT* -> - 5 . 3
25 = coefficient -> INT -> DIGIT DIGIT* -> 2 DIGIT* -> 2 5 DIGIT* -> 2 5

So, that seems to work. The next thing we care about is polynomial. This is a coefficient x ^ exponent or coefficient x or coefficient. Our updated grammar:

polynomial -> coefficient | coefficient x | coefficient x ^ INT
coefficient -> INT | REAL
INT -> - DIGIT DIGIT* | DIGIT DIGIT*
REAL -> - DIGIT DIGIT* . DIGIT DIGIT* | DIGIT DIGIT* . DIGIT DIGIT*
DIGIT-> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Let's debug again:

3x = polynomial -> coefficient x -> INT x -> DIGIT DIGIT* x -> 3 DIGIT* x -> 3 x
10x^3 = polynomial -> coefficient x ^ INT -> INT x ^ INT -> DIGIT DIGIT* x ^ INT -> 1 DIGIT* x ^ INT -> 1 0 DIGIT* x ^ INT -> 1 0 x ^ INT -> 1 0 x ^ DIGIT DIGIT* -> 1 0 x ^ 3 DIGIT* -> 1 0 x ^ 3

We have a problem though. We can't allow for negative exponents. Let's update the grammar:

polynomial -> coefficient | coefficient x | coefficient x ^ DIGIT DIGIT*
coefficient -> INT | REAL
INT -> - DIGIT DIGIT* | DIGIT DIGIT*
REAL -> - DIGIT DIGIT* . DIGIT DIGIT* | DIGIT DIGIT* . DIGIT DIGIT*
DIGIT-> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

That should solve the problem.

And just to show the process of discovery, I will leave everything as is, and reveal that I should be calling polynomial a term instead. Terms are separated by plus or minus. Let's make that small change first and see where we're at (I really am doing this as I go. I have no grand plan in case you were wondering). This also means that we'll let polynomial handle the plus/minus aspect, but unfortunately INT and REAL still need to support negative because we can have some ax + -b for example.

poly -> term | term + poly | term - poly
term -> coef | coef x | coef x ^ DIGIT DIGIT*
coef -> INT | REAL
INT -> - DIGIT DIGIT* | DIGIT DIGIT*
REAL -> - DIGIT DIGIT* . DIGIT DIGIT* | DIGIT DIGIT* . DIGIT DIGIT*
DIGIT-> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Let's do a big test (this will be long).

-3x^3 + 1.2x^2 - 8x + 5 = poly ->
term + poly ->
coef x ^ DIGIT DIGIT* + poly ->
INT x ^ DIGIT DIGIT* + poly ->
- DIGIT DIGIT* x ^ DIGIT DIGIT* + poly ->
- 3 DIGIT* x ^ DIGIT DIGIT* + poly ->
- 3 x ^ DIGIT DIGIT* + poly ->
- 3 x ^ 3 DIGIT* + poly ->
- 3 x ^ 3 + poly ->
- 3 x ^ 3 + term - poly ->
- 3 x ^ 3 + coef x ^ DIGIT DIGIT* - poly ->
- 3 x ^ 3 + REAL x ^ DIGIT DIGIT* - poly ->
- 3 x ^ 3 + DIGIT DIGIT* . DIGIT DIGIT* x ^ DIGIT DIGIT* - poly ->
- 3 x ^ 3 + 1 DIGIT* . DIGIT DIGIT* x ^ DIGIT DIGIT* - poly ->
- 3 x ^ 3 + 1 . DIGIT DIGIT* x ^ DIGIT DIGIT* - poly ->
- 3 x ^ 3 + 1 . 2 DIGIT* x ^ DIGIT DIGIT* - poly ->
- 3 x ^ 3 + 1 . 2 x ^ DIGIT DIGIT* - poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 DIGIT* - poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - term + poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - coef x + poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - INT x + poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - DIGIT DIGIT* x + poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 DIGIT* x + poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 x + poly ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 x + term ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 x + coef ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 x + INT ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 x + DIGIT DIGIT* ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 x + 5 DIGIT* ->
- 3 x ^ 3 + 1 . 2 x ^ 2 - 8 x + 5

Whew, what a journey.

So What?

We could write a parser to process an input string and determine if what was provided is a polynomial or not. As we parse through it, we can store the data to proper data structures, and then do operations on it as objects.

I'll be attempting to code this in an upcoming post probably, so if this is interesting, look forward to that.

Also, feel free to comment on any errors I've made. Your review is appreciated.

More on context-free grammars:
https://en.wikipedia...xt-free_grammar

S M T W T F S
12345
6789101112
13 141516171819
20212223242526
2728293031

Recent Entries

• • • • • • • • • • 0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)