In this project you will implement a Boolean satisfiability (SAT) solver in OCaml. The program takes as input a string representing a Boolean formula. This formula may involve constants (TRUE and FALSE) and variables (represented by lowercase letters a through z). Each variable may be either TRUE or FALSE. The program should return a list of variable assignments that make the formula true. For instance, to make (and a b) true, both “a” and “b” need to be TRUE. To make (or a b) true, there are three possible solutions, both “a” and “b” are TRUE, or “a” is TRUE, “b” is FALSE, or “b” is TRUE, “a” is FALSE. The grammar for the logical formula in our project is defined below:
1.1 Tree representation of Boolean formula
To begin with, you will first convert the string list into a parse tree. You will write a recursive descent
parser to extract the parse tree from the string list.
For example, the parse tree for string list ( and ( or a b ) TRUE ) with respect to the grammar defined
above is the following: