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) = a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_{2}x^{2} + a_{1}x + a_{0} where a ∈ ℝ
For example, we might have: f(x) = 3x^{3} + 9x^{2} + x + 4. We might also have 2.5x^{5} + 8x^{3}. Or even (1/3)x^{2}. 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
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:
Let's debug a bit, and make sure this is right.
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:
Let's debug again:
We have a problem though. We can't allow for negative exponents. Let's update the grammar:
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.
Let's do a big test (this will be long).
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
A polynomial of degree n of one variable is a function of the form: f(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_{2}x^{2} + a_{1}x + a_{0} where a ∈ ℝ
For example, we might have: f(x) = 3x^{3} + 9x^{2} + x + 4. We might also have 2.5x^{5} + 8x^{3}. Or even (1/3)x^{2}. 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
← October 2020 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
1 user(s) viewing
1 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)