title: Parsing predicate logic in bison c++
body: <p>I am developing a software to simplify a formula in <a href="http://en.wikipedia.org/wiki/First-order_logic" rel="nofollow">predicate logic</a> notation, applying some logical laws to output the formula in a <strong>conjunctive normal form</strong>. <em>I will try to explain everything as clearly as possible.</em> I know that this is not a mathematic site, but I have to explain a bit some concepts to get concret answers.</p>
  
  <hr>
  
  <h2>What will the software do?</h2>
  
  <p>The software will have an entry in which the user can insert a formula and the program will process until reach its conjunctive normal form. So I have to do a parser that can handle the input and put each token in some structure an then thansform it as needed. I will use the following tools:</p>
  
  <ul>
  <li>C++.</li>
  <li>Qt framework.</li>
  <li>Bison and Flex.</li>
  </ul>
  
  <h2>How to get the <a href="http://en.wikipedia.org/wiki/Conjunctive_normal_form" rel="nofollow">conjunctive normal form</a> of a formula?</h2>
  
  <ul>
  <li><code>F=!(a &amp;&amp; b)</code>, then the output will be <code>F[cnf]=!a || !b</code> (applying <a href="http://en.wikipedia.org/wiki/De_Morgan%27s_laws" rel="nofollow">De Morgan's law</a>).</li>
  <li><code>F=(a &amp;&amp; b)</code>, then the output will be <code>F[cnf]=a &amp;&amp; b</code> (the same, because the input is already in this form).</li>
  <li><code>F=a &amp;&amp; (b || c)</code>, then <code>F[cnf]= (a || b) &amp;&amp; (a || c)</code> (<a href="http://en.wikipedia.org/wiki/Distributivity" rel="nofollow">distributive law</a>). </li>
  </ul>
  
  <p>So, basically is the same formula but separated by the <code>&amp;&amp;</code> token. </p>
  
  <h2>Construction status</h2>
  
  <p>The first problem that I had when I was trying to manipulate the parts of the input formula was handle the recursion my grammar rules.</p>
  
  <p>Suppose the following rules:</p>
  
  <pre><code>expr:
           SYMBOL                                  { cout &lt;&lt; " 0 "; }
      |    LEFT_PARENTHESES expr RIGHT_PARENTESES  { cout &lt;&lt; " 1 "; }
      |    expr AND expr                           { cout &lt;&lt; " 2 "; }
  ;
  </code></pre>
  
  <p>and the input <code>(a &amp;&amp; b)</code> then the program prints: <code>0 - 0 - 1 - 2</code>, this is: from the last rule executed to the first. I've realize that using a <code>queue</code> and inserting each token with the <code>push_back()</code> method, then I can get all my tokens ordered by these rules. But I want to operate with these expressions, not only verify her syntax and print the tokens, so I had to create a more complex structure (<em>not so complex</em>), a <a href="http://en.wikipedia.org/wiki/Binary_tree" rel="nofollow">binary tree</a> to simulate an <a href="http://en.wikipedia.org/wiki/Abstract_syntax_tree" rel="nofollow">abstract syntax tree</a> and then transform it. Suppose now the formula <code>a &amp;&amp; b || c</code>, represented in my tree it will be:</p>
  
  <pre><code>      &amp;&amp;
       /  \
      a    ||
          /  \
         b    c
  </code></pre>
  
  <p>this is, the parent is always an operator, and the childs are the operands or some expressions. If I have an expression like <code>a &amp;&amp; (b || c)</code>, then I have to include the parentheses:</p>
  
  <pre><code>      &amp;&amp;
       /  \
      a    (
            \
            ||
           /  \
          b    c
  </code></pre>
  
  <p>in that way, all the tokens in the right side of <code>(</code> will be enclosed in one group. So, I can do it with <em>simple formulas</em>(binary or multiple operations with the <code>not</code>, <code>and</code>, <code>||</code> and <code>()</code> operators; I can resolve nested formulas too and apply De Morgan's laws) and this works very good :D.</p>
  
  <h2>So, whats the problem?</h2>
  
  <p>Ok, as I say above, it only works with simple formulas. But what happen if the input have the operators <code>-&gt;</code> (implies) or <code>&lt;-&gt;</code> (if and only if)? (...) the program does't work. All I have to do is apply the definitions of that logic operators:</p>
  
  <ul>
  <li><code>P-&gt;Q</code>: <code>!P || Q</code> (1)</li>
  <li><code>P&lt;-&gt;Q</code>: <code>(P-&gt;Q) &amp;&amp; (Q-&gt;P)</code>: <code>(!P || Q) &amp;&amp; (!Q || P)</code> (2)</li>
  </ul>
  
  <p>So, the first thing I have to do is to transform the <code>-&gt;</code> and <code>&lt;-&gt;</code> operations using the rules (1) and (2). Once I have all the expressions with the elementals operators (<code>&amp;&amp;</code>, <code>||</code>, <code>!</code> and <code>()</code>), I have to distribute the <code>!</code> operators using De Morgan's laws and distibute the <code>||</code> to returns its conjunctive normal form. It sounds simple to do, but it is not (at least not for me).</p>
  
  <p>Do you remember when I mentioned that the rules are not executed in the order of arrival of tokens?. In this case, I can apply the <code>-&gt;</code> operator: let <code>a-&gt;b</code> adding a <code>!</code> in the left expression (<code>a</code>) and inserting <code>||</code> between these two expressions (<code>a</code> and <code>b</code>). I can do this adding a parent in my tree (<code>!</code>), a right child <code>a</code>, a <code>||</code> parent and another child <code>b</code>:</p>
  
  <pre><code>      ||
       /  \
      !    b
       \   
        a  
  </code></pre>
  
  <p>So, in this case works, but I can't do the same with the <code>&lt;-&gt;</code> operator!</p>
  
  <p>So, my question is: how I can solve these problems?, do you recommend using another structure to store tokens?, do you know any techniques to do this?</p>
  
  <hr>
  
  <h2>The code</h2>
  
  <p><em>parser.y</em></p>
  
  <pre><code>%{
      #include &lt;iostream&gt;
      #include "parsingtree.h"
  
      using namespace std;
  
      #define YYSTYPE string
  
      int yylex(void);
      void yyerror(char *);
  
      ParsingTree tree;
  %}
  
  %token  LEFT_PAR
          RIGHT_PAR
          SYMBOL
          END
          NOT
          DIST
  
  %left   AND
          OR
          THEN
          IFF
  
  %start input
  
  %%
  
  input:
          /* empty */
      |   input expr
  ;
  
  expr:
          SYMBOL {
              $$ = $1;
              cout &lt;&lt; "ACA ENTRO A LA REGLA 0" &lt;&lt; endl;
              tree.pushSymbol($1);
          }
      |   LEFT_PAR expr RIGHT_PAR {
              $$ = $2;
              tree.pushLogicOperator("()");
          }
      |   NOT expr {
              $$ = $2;
              tree.pushLogicOperator("!");
          }
      |   DIST expr RIGHT_PAR {
              $$ = $2;
              tree.pushLogicOperator("!");
          }
      |   expr AND expr {
              tree.pushLogicOperator("&amp;&amp;");
          }
      |   expr OR expr {
              tree.pushLogicOperator("||");
          }
      |   expr THEN expr {
              tree.pushLogicOperator("||");
              tree.pushLogicOperator("!");
          }
  ;
  
              tree.pushLogicOperator("||");
              tree.pushLogicOperator("!");
  
          }
      |   SYMBOL THEN expr {
              tree.pushSymbol($1);
              tree.pushLogicOperator("||");
              tree.pushLogicOperator("!");
          }
  %%
  
  void yyerror(char *s) {
  
  }
  </code></pre>
  
  <p><em>scanner.l</em></p>
  
  <pre><code>%option noyywrap
  %{
      #include &lt;iostream&gt;
      #include "parser.tab.c"
      using namespace std;
  %}
  
  %%
  
  [a-zA-Z0-9&lt;&gt;=]+  {
      yylval = strdup(yytext);
      return SYMBOL;
  }
  
  "&amp;&amp;" {
      return AND;
  }
  
  "||" {
      return OR;
  }
  
  "!" {
      return NOT;
  }
  
  "!(" {
      return DIST;
  }
  
  [ \0\0] {
      return END;
  }
  
  "("     {
      return LEFT_PAR;
  }
  
  ")"     {
      return RIGHT_PAR;
  }
  
  "-&gt;"    {
      return THEN;
  }
  
  "&lt;-&gt;"   {
      return IFF;
  }
  
  %%
  </code></pre>
  
  <p><em>main.cpp</em></p>
  
  <pre><code>#include "parsingtree.h"
  #include "lex.yy.c"
  
  typedef yy_buffer_state *YY_BUFFER_STATE;
  extern int yyparse();
  extern YY_BUFFER_STATE yy_scan_string(char *, size_t);
  
  int main(int argc, char *argv[]) {
      yy_scan_string("(a&amp;&amp;(d-&gt;g))-&gt;(b&amp;&amp;c)\0\0");
      yyparse();
  
      tree.printTree();
  }
  </code></pre>
  
  <p><em>parsingtree.h</em></p>
  
  <pre><code>#ifndef PARSINGTREE_H
  #define PARSINGTREE_H
  #include &lt;QString&gt;
  #include &lt;QList&gt;
  #include &lt;QDebug&gt;
  #include &lt;iostream&gt;
  
  using namespace std;
  
  class ParsingTree
  {
  public:
      ParsingTree();
      void pushSymbol(string data);
      void pushLogicOperator(string data);
      void printTree();
  
  private:
      struct treeNode
      {
          string data;
          treeNode* leftNode;
          treeNode* rightNode;
      };
      QList&lt;treeNode*&gt; auxList; //guarda el arbol en formación
      treeNode* tree; //pedir el ultimo elemento de la lista, ese es el arbol
  
      void printTree(treeNode* rTree);
      string latest(treeNode* rTree);
  };
  
  #endif // PARSINGTREE_H
  </code></pre>
  
  <p><em>parsingtree.cpp</em></p>
  
  <pre><code>#include "parsingtree.h"
  
  ParsingTree::ParsingTree()
  {
      tree= NULL;
  }
  
  void ParsingTree::pushSymbol(string data)
  {
      treeNode* node = new treeNode;
      node-&gt;data = data;
      node-&gt;leftNode = NULL;
      node-&gt;rightNode= NULL;
      auxList.push_back(node);
  }
  
  void ParsingTree::pushLogicOperator(string data)
  {
      //binarios
      if ((data == "||") || (data == "&amp;&amp;"))
      {
           treeNode* node = new treeNode;
           node-&gt;data = data;
           node-&gt;rightNode=auxList.last();
           auxList.removeLast();
           node-&gt;leftNode=auxList.last();
           auxList.removeLast();
           auxList.push_back(node);
      }
      //unarios
      if ((data == "!") || (data == "()"))
      {
          treeNode* node = new treeNode;
          node-&gt;data = data;
          node-&gt;rightNode=auxList.last();
          auxList.removeLast();
          node-&gt;leftNode= NULL;
          auxList.push_back(node);
      }
  }
  
  void ParsingTree::printTree()
  {
      tree = auxList.last();
      printTree(tree);
  }
  
  void ParsingTree::printTree(ParsingTree::treeNode* rTree)
  {
      if (rTree != NULL)
      {
  
          printTree(rTree-&gt;leftNode);
          if (rTree-&gt;data == "()")
          {
              cout &lt;&lt; "$(";
              printTree(rTree-&gt;rightNode);
              cout &lt;&lt; ")$";
          }
          else
          {
              cout &lt;&lt; rTree-&gt;data + " ";
              printTree(rTree-&gt;rightNode);
          }
      }
  }
  </code></pre>
  
  <p>Thanks! :D</p>
  
  <p><em>PS: if I wrote something wrong or there is something that you can not understand, please ask me so I can express myself better; My English is very poor (I'm from Argentina) and I find this problem very difficult to explain, so I hope you've understood.</em></p>