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

je cherche à écrire un générateur de table de vérité comme un projet personnel.

il existe plusieurs sites Web en ligne ici et ici.

alt text

(Example screenshot of an existing Truth Table Generator)

j'ai les questions suivantes:

  • Comment dois-je procéder pour analyser des expressions comme: ((P => Q) ET (Q => R)) => (P => R)
  • devrais-je utiliser un générateur de parseurs comme ANTLr ou YACC,ou utiliser des expressions régulières?
  • une fois que j'ai l'expression analysée, Comment dois-je procéder pour générer la table de vérité? Chaque section de l'expression doit être divisé en plus petits composants et re-construit à partir du côté gauche de la table à droite. Comment pourrais-je évaluer quelque chose comme ça?

quelqu'un Peut-il me fournir des conseils concernant l'analyse de ces expressions arbitraires et finalement l'évaluation de l'analyse expression?

14
demandé sur rahul 2009-07-06 01:40:44

5 réponses

cela ressemble à un grand projet personnel. Vous en apprendrez beaucoup sur le fonctionnement des éléments de base d'un compilateur. Je sauterais d'essayer d'utiliser un analyseur générateur; si c'est pour votre propre édification, vous en apprendrez plus en le faisant tout à partir de zéro.

la façon dont ces systèmes fonctionnent est une formalisation de la façon dont nous comprenons les langues naturelles. Si je vous donne une phrase: "le chien, Rover, a mangé sa nourriture.", la première chose que vous faites est de le découper en mots et en ponctuation. "espace", "chien", "virgule", "espace", "Rover",... C'est" tokenizing "ou"lexing".

La prochaine chose à faire est d'analyser le jeton stream pour voir si la phrase est grammaticale. La grammaire de l'anglais est extrêmement compliqué, mais cette phrase est assez simple. SUJET-APPOSITIF-VERBE-OBJET. C'est "analyse".

une fois que vous savez que la phrase est grammaticale, vous pouvez alors analyser la phrase pour en tirer réellement un sens. Par exemple, vous pouvez voir qu'il y a trois parties de cette phrase-le sujet, l'appositif, et le "sien" dans l'objet-qui font toutes référence à la même entité, à savoir, le chien. Vous pouvez comprendre que le chien est la chose qui mange, et la nourriture est la chose qui est mangée. C'est l'analyse sémantique de la phase.

les compilateurs ont alors une quatrième phase que les humains n'ont pas, c'est-à-dire qu'ils génèrent du code qui représente les actions décrites dans le langage.

Donc, faire tout ce qui. Commencez par définir ce que les tokens de votre langue sont, définissez un Token de classe de base et un tas de classes dérivées pour chacun. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken...). Ensuite, écrivez une méthode qui prend une chaîne et retourne un IEnumerable'. C'est votre analyseur lexical.

Deuxièmement, trouvez Quelle est la grammaire de votre langue, et écrivez un analyseur de descente récursif qui décompose un IEnumerable en un arbre de syntaxe abstrait qui représente les entités grammaticales dans votre langue.

alors écrivez un analyseur qui regarde cet arbre et trouve des trucs, comme "combien de variables libres distinctes ai-je?"

Ensuite écrire un générateur de code qui crache le code nécessaire pour évaluer la vérité des tableaux. Cracher ça semble exagéré, mais si tu veux être vraiment costaud, tu peux. Il pourrait être plus facile de laisser la bibliothèque de l'arbre d'expression faire cela pour vous; vous pouvez transformer votre arbre d'analyse en arbre d'expression, puis transformer l'expression former un délégué et évaluer le délégué.

Bonne chance!

22
répondu Eric Lippert 2009-07-05 22:34:17

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.

2
répondu Mehrdad Afshari 2017-05-23 12:09:55

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.

1
répondu Simeon Pilgrim 2009-07-05 22:39:39

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.

1
répondu Ira Baxter 2009-08-22 11:57:55

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 :)

0
répondu RANUX 2010-05-14 20:19:25