Comment puis-je construire un générateur de table de vérité?

je pense qu'un analyseur générateur est inutile. Vous pourriez utiliser l'idée de convertir une expression en postfix et l'évaluation de postfix expressions (ou en construisant directement un arbre d'expression à partir de l'expression infix et en l'utilisant pour générer la table de vérité) pour résoudre ce problème.

comme Mehrdad le mentionne, vous devriez être capable de lancer l'analyse à la main en même temps qu'il faudrait pour apprendre la syntaxe d'un lexer/parser. Le résultat final que vous voulez est un arbre de syntaxe abstraite (AST) de l'expression qui vous a été donnée.

vous devez ensuite construire un générateur d'entrées qui crée les combinaisons d'entrées pour les symboles définis dans l'expression.

puis itérer à travers le jeu d'entrées, générant les résultats pour chaque combo d'entrées, étant donné les règles (AST) vous avez analysé dans la première étape.

Comment je pourrais faire:

je pourrais imaginer l'utilisation des fonctions lambda pour exprimer les AST / règles pendant que vous parsez l'arbre, et la construction d'une table de symbole pendant que vous parsez, vous pourriez alors construire le jeu d'entrée, en parsant la table de symbole à l'arbre d'expression lambda, pour calculer les résultats.

si votre but est le traitement des expressions booléennes, un générateur d'analyseur et toutes les machines qui vont avec est une perte de temps, à moins que vous vouliez apprendre comment ils fonctionnent (alors l'un d'eux serait très bien).

mais il est facile de construire un analyseur de descente récursive à la main pour les expressions booléennes, qui calcule et renvoie les résultats de "l'évaluation" de l'expression. Un tel analyseur pourrait être utilisé sur un premier passage pour déterminer le nombre de variables uniques, où "évaluation" signifie "couunt" 1 pour chaque nouveau nom de variable". Écrire un générateur pour produire toutes les valeurs de vérité possibles pour n variables est trivial; pour chaque ensemble de VALEURs, il suffit de rappeler l'analyseur et de l'utiliser pour évaluer l'expression, où évaluer signifie "combiner les valeurs des sous-expressions selon l'opérateur".

Vous avez besoin d'une grammaire:

formula = disjunction ;
disjunction = conjunction 
              | disjunction "or" conjunction ;
conjunction = term 
              | conjunction "and" term ;
term = variable 
       | "not" term 
       |  "(" formula ")" ;

la Vôtre peut être plus compliqué, mais pour les expressions booléennes il ne peut pas être beaucoup plus compliqué.

Pour chaque grammaire règle, écrire 1 sous-programme qui utilise un index global" scan " dans la chaîne de caractères:

  int disjunction()
 // returns "-1"==> "not a disjunction"
 // in mode 1:
 // returns "0" if disjunction is false
 // return  "1" if disjunction is true
 { skipblanks(); // advance scan past blanks (duh)
   temp1=conjunction();
   if (temp1==-1) return -1; // syntax error
   while (true)
     { skipblanks();
       if (matchinput("or")==false) return temp1;
       temp2= conjunction();
       if (temp2==-1) return temp1;
       temp1=temp1 or temp2;
     }
  end

  int term()
  { skipblanks();
    if (inputmatchesvariablename())
       { variablename = getvariablenamefrominput();
         if unique(variablename) then += numberofvariables;
         return lookupvariablename(variablename); // get truthtable value for name
       }
     ...
  }

chacune de vos routines de parse sera sur ce compliqué. Sérieusement.

vous pouvez obtenir le code source du programme pyttgen à http://code.google.com/p/pyttgen/source/browse/#hg/src il génère des tables de vérité pour les expressions logiques. Code basé sur les plis de la bibliothèque, de sorte que son très simple :)