5

My goal is to write a function that will take a logical expression (eg: A OR NOT(B AND C)) and convert that into disjunctive normal form. (A OR NOT B OR NOT C)

I have written a grammar that will generate logical expressions

S => !S
S => (S)
S => S op S
S => W
op => AND | OR
W => A | B | C | ... | Z

This is my algorithm

  1. Given an expression S
  2. recursively parse the expression using the grammar above and build the corresponding parse tree
  3. Convert the expression to DNF by recursively "simplifying" any NOT operators on the tree.
  4. Recursively go through final parse tree and output the DNF logical expression.

With a parse tree I can simplify NOT operators by checking the current node's parent, and pushing it down the tree or re-arranging the tree (in the case of NOT NOT). Then it is trivial to flatten the tree.

This works on paper, but now I'm stuck with the actual parser. How can I convert these rules into a parser class? I don't want to use external libraries and want to write the parser from scratch.

MxLDevs
  • 19,048
  • 36
  • 123
  • 194
  • If you do not want to use external tools I recommend this book - the "bible" of compiler construction: http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886 – Casper Oct 27 '12 at 16:55
  • Also this is a great series: http://www.rubyinside.com/writing-a-compiler-in-ruby-1222.html – Casper Oct 27 '12 at 16:56
  • And: http://stackoverflow.com/questions/1669/learning-to-write-a-compiler – Casper Oct 27 '12 at 16:58
  • I'm sort of wondering whether a compiler-like thing is necessary for something like this. I guess the process would be pretty much what a compiler does since I would have to do lexical and semantic analysis of sorts but maybe there is an easy way out and use stuff that is built into ruby like perhaps something to do with instance_evals or writing something like a DSL... – MxLDevs Oct 27 '12 at 17:02
  • 1
    Oh I could probably just use something like a recursive descent parser. – MxLDevs Oct 27 '12 at 17:37

1 Answers1

1

Have a look at Treetop, which might do what you want. http://treetop.rubyforge.org/

Benjamin Tan Wei Hao
  • 9,621
  • 3
  • 30
  • 56
  • 1
    [citrus](https://github.com/mjijackson/citrus) is another member of that family. Neither will work if recursive descent is needed, but the grammar may be able to be massaged into an appropriate form for the gems. – x1a4 Oct 27 '12 at 17:08