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

StackOverflow https://stackoverflow.com/questions/1084873

Question

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

Il y en a plusieurs en ligne sur le Web et ici .

text alt
(Example screenshot of an existing Truth Table Generator)

J'ai les questions suivantes:

  • Comment dois-je aller sur l'analyse syntaxique des expressions comme: ((P => Q) et (Q => R)) => (P => R)
  • Dois-je utiliser un générateur d'analyseur comme Antlr ou YACC, ou utiliser des expressions régulières droites?
  • Une fois que je suis l'expression analysable, comment dois-je aller sur la génération de la table de vérité? Chaque section de l'expression doit être divisée en ses composants les plus petits et Reconstruit à partir du côté gauche de la table à droite. Comment puis-je évaluer quelque chose comme ça?

Quelqu'un peut-il me donner des conseils concernant l'analyse de ces expressions arbitraires et éventuellement évaluer l'expression analysable?

Était-ce utile?

La solution

Cela ressemble à un grand projet personnel. Vous apprendrez beaucoup de choses sur la façon dont les éléments de base d'un travail de compilateur. Je sauterais essayer d'utiliser un générateur d'analyseur; si cela est pour votre propre édifie, vous en apprendrez plus en faisant tout à partir de zéro.

La façon dont ces systèmes travail 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 la diviser en mots et la ponctuation. "La", "SPACE", "chien", "VIRGULE", "SPACE", "Rover", ... qui est "tokenizing" ou "lexing".

La prochaine chose à faire est d'analyser le flux de jeton pour voir si la phrase est grammaticale. La grammaire de l'anglais est extrêmement compliquée, mais cette phrase est assez simple. OBJET Appositive-verbe-. Ceci est "analyse pas".

Une fois que vous savez que la phrase est grammaticale, vous pouvez alors analyser la phrase pour obtenir effectivement un sens hors de lui. Par exemple, vous pouvez voir qu'il ya trois parties de cette phrase - le sujet, le appositive, et « son » dans l'objet - que tous se réfèrent à la même entité, à savoir, le chien. Vous pouvez comprendre que le chien est la chose à faire le manger, et la nourriture est la chose être mangé. Ceci est la phase d'analyse sémantique.

Compilateurs ont alors une quatrième phase que les humains ne le font pas, ce qui est qu'ils génèrent du code qui représente les actions décrites dans la langue.

Alors, faire tout cela. Commencez par définir ce que les jetons de votre langue sont, définir une classe de base à jeton et un groupe de classes dérivées pour chacun. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). Puis écrire une méthode qui prend une chaîne et retourne un IEnumerable ». C'est votre lexer.

Deuxièmement, comprendre ce que la grammaire de votre langue est, et d'écrire un analyseur de descente récursive qui casse un IEnumerable dans un arbre de syntaxe abstraite qui représente les entités grammaticales dans votre langue.

Ensuite, écrire un analyseur qui ressemble à cet arbre et chiffres trucs, comme « combien de variables libres distinctes dois-je? »

Ensuite, écrivez un générateur de code qui recrache le code nécessaire pour évaluer les tables de vérité. Cracher IL semble exagéré, mais si vous voulez être vraiment mordu, vous pouvez. Il pourrait être plus facile de laisser la bibliothèque d'arbre d'expression faire pour vous; vous pouvez transformer votre arbre d'analyse syntaxique dans un arbre d'expression, puis tourner l'arbre d'expression dans un délégué, et d'évaluer le délégué.

Bonne chance!

Autres conseils

Je pense qu'un générateur d'analyseur syntaxique est un surpuissant. Vous pouvez utiliser l'idée de convertir une expression postfix et évaluation des expressions de Postfix (ou directement la construction d'un arbre d'expression de l'expression infixe et à l'aide que pour générer la table de vérité) pour résoudre ce problème.

Mehrdad vous mentionne devriez pouvoir remettre rouler l'analyse syntaxique dans le même temps qu'il faudrait pour apprendre la syntaxe d'un lexer / parser. Le résultat final que vous voulez est une arbre de syntaxe abstraite (AST) de l'expression que vous avez donné.

Il vous faut ensuite construire une génératrice d'entrée qui crée les combinaisons d'entrée pour les symboles définis dans l'expression.

Alors itérer à travers l'ensemble d'entrée, générer les résultats pour chaque combo d'entrée, compte tenu des règles (AST) vous analysables dans la première étape.

Comment je le ferais:

Je pourrais imaginer d'utiliser les fonctions lambda pour exprimer l'AST / règles que vous Parse l'arbre et la construction d'une table de symboles que vous analysez, alors vous pourriez construire l'ensemble d'entrée, l'analyse de la table des symboles à l'arbre d'expression lambda, pour calculer les résultats.

Si votre objectif 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, sauf si vous voulez savoir comment ils fonctionnent (alors l'un d'eux serait bien).

Mais il est facile de construire un analyseur récursif-descente à la main pour les expressions booléennes, qui calcule et renvoie les résultats de « l'évaluation » l'expression. Un tel analyseur peut être utilisé sur une première passe pour déterminer le nombre de variables uniques, où « l'évaluation » signifie « couunt 1 pour chaque nouveau nom de variable ». L'écriture d'un générateur pour produire toutes les valeurs possibles de vérité pour les variables N est trivial; pour chaque ensemble de valeurs, il suffit d'appeler à nouveau l'analyseur et 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 ")" ;

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

Pour chaque règle de grammaire, d'écriture 1 sous-programme qui utilise un indice global « scan » dans la chaîne en cours d'analyse: 

  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
       }
     ...
  }

Chacun de vos routines parse sera sur ce complexe. 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 la bibliothèque de plis, il est donc très simple:)

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top