Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Writing a parser that takes a grammar and generates a parse tree

Tags:

ruby

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.

like image 288
MxLDevs Avatar asked Nov 12 '22 19:11

MxLDevs


1 Answers

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

like image 113
Benjamin Tan Wei Hao Avatar answered Dec 30 '22 05:12

Benjamin Tan Wei Hao