parsing algebraic expressions in GF(2)

Question

I would write a function which can parse the multiplication of 2 algebraic expressions in GF(2), i.e any variable in the expression only take on 2 possible values 0 or 1, so a^2 = a,(0^2 = 0, 1^2 = 1)

As an example, if we expand (a+b)*(a+c) in GF(2), we should get

(a + b)*(a + c) = a^2 + a*b + a*c + b*c = a + a*b + a*c + b*c.

However, I am not sure how to start about the parsing of 2 algebraic expressions using strings. Any suggestion/ help is appreciated. Thanks!

Although you apparently have a special purpose in mind, nothing in your examples actually uses the fact that the terms are to be understood over GF(2). To my understanding, you mean to parse expressions over a field. — Codor, Jan 06 '16 at 08:00
@Codor: Your understanding is correct! I have updated my example for a better understanding. Thanks for your attention. — meta_warrior, Jan 06 '16 at 08:17

score 0 · Answer 1 · answered Jan 10 '16 at 14:35

I would recommend taking a look at OMeta, by Alex Warth, and/or PetitParser, by Lucas Rengli. Both are excellent frameworks for writing parsers. The first one is for JS, the second for Smalltalk.

Here are some few initial lines of code showing how to write your parser in PetitParser. Every fragment is a method of your own subclass of PPCompositeParser.

constant
    ˆ$0 asParser / $1 asParser

variable
    ^#letter asParser

timesOp
    ^#blank asParser star , $* asParser, #blank asParser star

sumOp
    ^#blank asParser star, $* asParser, #blank asParser star

element
    ^self constant / self variable

term
   ^self element , (self timesOp , self element) star

etc.

I'm not saying this is trivial. I'm only saying that this is where I would start. Note also that once you have your grammar in place you might want to subclass it so you can generate more appropriate productions, etc.

score 0 · Answer 2 · edited May 23 '17 at 11:44

Writing parsers for big complicated languages can be hard. But writing parsers for algebraic expressions (GF(2) or otherwise) is pretty easy. See my SO answer on how to write such parsers easily: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?

The GF(2) bit is about semantic interpretation of what such a formula means. It doesn't matter at all for parsing, which is purely about syntax. Where meaning comes into play is when you want to interpret the formula. At some point, you may want to evaluate the expression using values for the variables. To do that, you have to capture the formula as a data structure (usually called an (abstract) syntax tree), and then walk that tree to compute the desired result. That link also discusses how to do that.

If you want to manipulate the formula symbolically, you're in an entirely different ball game. Parsing is still easy, but formula manipulation is not, and you'll want to use tools that are designed to do such symbolic manipulation; they generally define thier own parsing machinery (and make it easy to use) to ensure that the captured parse can be manipulated. And of course, you'll have to define what the rules of you symbolic manipulation are.

You can see an example of how to write something pretty close to your needs at Symbolic Algebra with a program transformation system. (This a tool that my company builds).

parsing algebraic expressions in GF(2)

2 Answers2