How to create grammar for applying De Morgan's theorem to an expression using yacc?

Question

I would like to apply Demorgan's theorem to an input using yacc and lex.

The input could be any expression such as a+b, !(A+B) etc:

• The expression a+b should result in !a∙!b
• The expression !(a+b) should result in a+b

I think the lex part is done but I'm having difficulty with the yacc grammar needed to apply the laws to an expression.

What I'm trying to implement is the following algorithm. Consider the following equation as input: Y = A+B

After applying De Morgan's law it becomes: !Y = !(A+B)

Finally, expanding the parentheses should result in !Y = !A∙!B

here lex code:

%{
#include <stdio.h>
#include "y.tab.h"

extern int yylval;
int yywrap (void);
%}

%%
[a-zA-Z]+   {yylval = *yytext; return ALPHABET;}
"&&"        return AND;
"||"        return OR;
"="     return ('=');
[\t]        ;
\n      return 0;
.       return yytext[0];
"0exit"     return 0;
%%

int yywrap (void)
{
    return 1;
}

Here is my yacc code:

%{
#include <stdio.h>

int yylex (void);
void yyerror (char *);
extern FILE* yyin;
%}

%token ALPHABET
%left '+''*'
%right '=' '!' NOT

%left AND OR
%start check

%%
check : expr  {printf("%s\n",$$);}
      ; 
expr : plus
     |plus '+' plus {$$ = $1 + $3;}
     ;
plus : times
     |times '*' times   {$$ = $1 * $3;}
     ;
times : and_op
      |and_op AND and_op{$$ = $1 && $3;}
      ;
and_op : or_op
       |or_op OR or_op  {$$ = $1 || $3;}
       ;
or_op : not_op
      |'!' not_op   {$$ = !$2;}
      ;
not_op : paren
       |'(' paren ')'   {$$ = $2;}
       ;
paren : 
      |ALPHABET     {$$ = $1;}
      ;

/*  
 E: E '+' E     {$$ = $1 + $3;}
  |E '*' E  {$$ = $1 * $3;}
  |E '=' E  {$$ = $1 = $3;}
  |E AND E  {$$ = ($1 && $3);}
  |E OR E   {$$ = ($1 || $3);}
  |'(' E ')'    {$$ = $2;}
  |'!' E %prec NOT {$$ = !$2;}
  |ALPHABET     {$$ = $1;}
  ;*/
%%

int main()
{
    char filename[30];
    char * line = NULL;
    size_t len = 0;
    printf("\nEnter filename\n");
    scanf("%s",filename);
    FILE *fp = fopen(filename, "r");
    if(fp == NULL)
    {
        fprintf(stderr,"Can't read file %s\n",filename);
        exit(EXIT_FAILURE);
    }
    yyin = fp;
//  while (getline(&line, &len, fp) != -1)
//  {
//      printf("%s",line);
//  }
//  printf("Enter the expression:\n");
    do
    {
        yyparse();
    }while(!feof(yyin)); 

    return 0;   
}

Answer 1

You are trying to build a computer algebra system.

Your task is conceptually simple:

1. Define a lexer for the atoms of your "boolean" expressions
2. Define a parser for propositional logic in terms of the lexemes
3. Build a tree that stores the expressions
4. Define procedures that implement logical equivalences (DeMorgan's theorem is one), that find a place in the tree where it can be applied by matching tree structure, and then modifying the tree accordingly
5. Run those procedures to achieve the logic rewrites you want
6. Prettyprint the final AST as the answer

But conceptually simple doesn't necessarily mean easy to do and get it all right.

(f)lex and yacc are designed to help you do steps 1-3 in a relatively straightforward way; their documentation contains a pretty good guide. They won't help with steps 4-6 at all, and this is where the real work happens. (Your grammar looks like a pretty good start for this part).

(You can do 1-3 without flex and yacc by building a recursive descent parser that also happens to build the AST as it goes).

Step 4 can be messy, because you have to decide what logical theorems you wish to use, and then write a procedure for each one to do tree matching, and tree smashing, to achieve the desired result. You can do it; its just procedural code that walks up and down the tree comparing node types and relations to children for a match, and then delinking nodes, deleting nodes, creating nodes, and relinking them to effect the tree modification. This is just a bunch of code.

A subtley of algebraic rewrites is now going to bite you: (boolean) algebra has associative and commutative operators. What this means is that some algebra rules will apply to parts of the tree that are arbitrarily far apart. Consider this rule:

    a*(b + !a) =>  a*(b)

What happens when the actual term being parsed looks like:

    q*(a + b + c + ... !q ... + z)

"Simple" procedural code to look at the tree now has to walk arbitrarily far down on of the subtrees to find where the rule can apply. Suddenly coding the matching logic isn't so easy, nor is the tree-smash to implement the effect.

If we ignore associative and commutative issues, for complex matches and modifications, the code might be a bit clumsy to write and hard to read; after you've done it once this will be obvious. If you only want to do DeMorgan-over-or, you can do it relatively easily by just coding it. If you want to implement lots of boolean algebras rules for simplification, this will start to be painful. What you'd ideally like to do is express the logic rules in the same notation as your boolean logic so they are easily expressed, but now you need something that can read and interpret the logic rules. That is complex piece of code, but if done right, you can code the logic rules something like the following:

 rule deMorgan_for_or(t1:boolexp, t2:boolexp):boolexp->boolexp
   " ! (\t1 + \t2) " ->   " !\t1 * !\t2 ";

A related problem (step 5) is, where do you want apply the logic rules? Just because you can apply DeMorgan's law in 15 places in a very big logic term, doesn't mean you necessarily want to do that. So somewhere you need to have a control mechanism that decides which of your many rules should apply, and where they should apply. This gets you into metaprogramming, a whole new topic.

If your rules are "monotonic", that is, they in effect can only be applied once, you can simply run them all everywhere and get a terminating computation, if that monotonic answer is the one you want. If you have rules that are inverses (e.g., !(x+y) => !x * !y, and !a * !b => !(a+b)), then your rules may run forever repeatedly doing and undoing a rewrite. So you have to be careful to ensure you get termination.

Finally, when you have the modified tree, you'll need to print it back out in readable form (Step 6). See my SO answer on how to build a prettyprinter.

Doing all of this for one or two rules by yourself is a great learning exercise.

Doing it with the idea of producing a useful tool is a whole different animal. There what you want is a set of infrastructure that makes this easy to express: a program transformation system. You can see a complete example of this what it looks like for a system doing arithmetic rather than boolean computations using surface syntax rewrite rules, including the handling the associative and commutative rewrite issues. In another example, you can see what it looks like for boolean logic (see simplify_boolean near end of page), which shows a real example for rules like I wrote above.