Wie kann ich eine Wahrheitstabelle Generator bauen?

Question

Ich suche eine Wahrheitstabelle Generator als ein persönliches Projekt zu schreiben.

Es gibt mehrere Web-basierte Online diejenigen hier und hier .

(Example screenshot of an existing Truth Table Generator)

Ich habe folgende Fragen:

• Wie soll ich gehen über Ausdrücke wie Parsen: ((P => Q) & (Q => R)) => (P => R)
• Sollte ich einen Parser-Generator wie antlr oder YACC, oder verwenden Sie gerade reguläre Ausdrücke?
• Sobald ich den Ausdruck analysiert, wie soll ich mich über die Wahrheitstabelle zu erzeugen? Jeder Abschnitt des Ausdrucks werden muss, in seine kleinsten Bestandteile aufgeteilt und von der linken Seite der Tabelle auf der rechten Seite wieder aufgebaut. Wie würde ich bewerten so etwas?

Kann jemand gibt mir Tipps, um das Parsen dieser beliebigen Ausdrücke in Bezug auf und schließlich den analysierte Auswertung des Ausdrucks?

Answer 1

Das klingt wie ein großes persönliches Projekt. Hier finden Sie eine Menge darüber, wie die grundlegenden Teile eines Compilers Arbeit lernen. versucht, einen Parser-Generator zu verwenden, würde ich überspringen; wenn dies für den eigenen Erbauung ist, werden Sie mehr lernen, indem sie alle von Grund auf zu tun.

Die Art und Weise solche Systeme Arbeit ist eine Formalisierung, wie wir natürliche Sprachen verstehen. Wenn ich Ihnen einen Satz geben: „Der Hund, Rover, aß sein Essen.“, Das erste, was Sie tun, ist es brechen in Worte und Interpunktion. "Der", "SPACE", "Hund", "Komma", "SPACE", "Rover", ... Das ist "Tokenisieren" oder "lexing".

Das nächste, was Sie tun, ist das Token-Stream analysieren, um zu sehen, ob der Satz grammatisch ist. Die Grammatik der englischen Sprache ist extrem kompliziert, aber dieser Satz ist ziemlich einfach. FACH appositive-Verb-Objekt. Dies wird als "Parsen".

Sobald Sie wissen, dass der Satz grammatisch ist, können Sie dann den Satz analysieren tatsächlich aus ihm heraus Sinn. siehe zum Beispiel, können Sie, dass es drei Teile dieses Satzes - das Thema, das appositive und „sein“ in dem Objekt - dass alle auf die gleiche Einheit beziehen, nämlich der Hund. Sie können herausfinden, dass der Hund das Ding ist, das Essen zu tun, und das Essen ist die Sache gegessen. Dies ist die semantische Analysephase.

Compiler dann eine vierte Phase hat, dass die Menschen nicht, die sie Code erzeugen, die die Aktionen in der Sprache beschrieben darstellt.

Also, das alles. Beginnen Sie mit der Definition dessen, was die Zeichen Ihrer Sprache sind, definieren Sie eine Basisklasse Token und eine Reihe von abgeleiteten Klassen für jeden. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). Dann schreiben Sie eine Methode, die einen String und gibt eine IEnumerable‘nimmt. Das ist Ihre Lexer.

Zweitens, herauszufinden, was die Grammatik der Sprache ist, und einen rekursiven Abstiegs-Parser schreiben, die eine IEnumerable in einen abstrakten Syntaxbaum aufbricht, die grammatischen Einheiten in Ihrer Sprache darstellt.

Dann einen Analysator schreiben, die Sachen aus, wie auf dem Baum und Zahlen sieht aus „wie viele verschiedene freie Variablen habe ich?“

Dann einen Code-Generator schreiben, die den Code spucken notwendig, um die Wahrheitstabellen zu bewerten. Spucken IL scheint übertrieben, aber wenn Sie wirklich Buff sein wollte, man könnte. Es könnte einfacher sein, die Ausdrucksbaum Bibliothek tun, dass für Sie zu lassen; Sie können Ihren Parse-Baum in einen Ausdrucksbaum, und drehen Sie dann den Ausdrucksbaum in einen Delegaten, und bewerten die Delegierten verwandeln.

Viel Glück!

Answer 2

Ich denke, ein Parser-Generator ist ein Overkill. Man könnte die Idee der Umwandlung eines Ausdrucks zu postfix verwenden und Auswertung postfix Ausdrücke (oder direkt Aufbau eines Ausdrucksbaum aus dem Infix Ausdruck und verwenden, die die Wahrheitstabelle zu erzeugen), dieses Problem zu lösen.

Answer 3

Wie Mehrdad erwähnt sollen Sie in der Lage sein, die Analyse in der gleichen Zeit Hand rollen, wie es dauern würde, die Syntax eines Lexer / Parser zu lernen. Das Endergebnis Sie wollen, ist einige abstrakte Syntaxbaum (AST) der Ausdruck, den Sie erhalten haben.

Sie müssen dann einen Eingabe-Generator bauen, die die Eingangskombinationen für die Symbole definieren in dem Ausdruck erstellt.

Dann über den Eingangssatz iterieren, die Ergebnisse für jeden Eingang Combo zu erzeugen, da die Regeln (AST) Sie im ersten Schritt analysiert.

Wie ich es tun würde:

könnte ich mir vorstellen, Lambda-Funktionen mit dem AST auszudrücken / Regeln, wie Sie den Baum analysieren, und eine Symboltabelle bauen, wie Sie analysieren, können Sie dann den Eingangssatz bauen, die Symboltabelle auf den Lambda-Ausdruck Baum Parsen zu berechnen, die Ergebnisse.

Answer 4

Wenn Ihr Ziel Booleschen Ausdrücken verarbeitet, ein Parser-Generator und alle Maschinen, die mit gehen, ist eine Verschwendung von Zeit, es sei denn, Sie lernen möchten, wie sie funktionieren (dann jeder von ihnen wäre in Ordnung).

Aber es ist leicht, einen rekursiven Abstieg Parser von Hand für Boolesche Ausdrücke zu bauen, die die Ergebnisse der „Auswertung“ der Ausdruck berechnet und zurückgibt. Ein solcher Parser auf einem ersten Durchgang verwendet werden, um die Anzahl der eindeutigen Variablen, um zu bestimmen, wobei „Auswertung“ bedeutet „couunt 1 für jede neue Variablenname“. Schreibe einen Generator alle Werte möglich Wahrheit für N Variablen zu erzeugen, ist trivial; für jeden Satz von Werten, einfach wieder den Parser aufrufen und verwenden Sie es um den Ausdruck auszuwerten, wo bedeutet „die Werte der Teilausdrücke nach dem Operator verbinden“ zu bewerten.

Sie müssen eine Grammatik:

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

Mit freundlichen Grüßen kann komplizierter sein, aber für Booleschen Ausdrücken kann es nicht so viel komplizierter sein.

Für jede Grammatikregel, schreiben 1 Unterprogramm, das einen globalen „Scan“ Index in die Zeichenfolge verwendet analysiert werden:

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

Jeder Ihrer Parsing-Routinen zu diesem kompliziert sein. Im Ernst.

Answer 5

/:

Sie können Quellcode pyttgen Programm unter http bekommen /code.google.com/p/pyttgen/source/browse/#hg/src Es Wahrheitstabellen für logische Ausdrücke erzeugt. Code basierend auf Lagenbibliothek, so dass sie sehr einfach:)