Subscribe to MentalFloss Minutes        RSS Feed
-----

Context-free Grammar Exploration : Polynomials

Icon 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

0 Comments On This Entry

 

December 2018

S M T W T F S
      1
2345678
9101112131415
1617 18 19202122
23242526272829
3031     

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

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