Come faccio a costruire una tabella generatore di verità?

Question

Sto cercando di scrivere una tabella generatore Verità come un progetto personale.

Ci sono diversi quelli on-line web-based qui e qui .

(Example screenshot of an existing Truth Table Generator)

Ho le seguenti domande:

• Come dovrei andare circa parsing di espressioni come: ((P => Q) & (Q => R)) => (P => R)
• Dovrei usare un generatore di parser come ANTLR o YACC, o utilizzare le espressioni regolari rette?
• Una volta che ho analizzato l'espressione, come devo fare per generare la tabella di verità? Ogni sezione dell'espressione deve essere suddiviso nelle sue componenti più piccoli e ricostruito dal lato sinistro della tabella a destra. Come faccio a valutare una cosa del genere?

Qualcuno può fornire me con punte per quanto riguarda il parsing di queste espressioni arbitrarie e, infine, valutare l'espressione analizzato?

Answer 1

Questo suona come un grande progetto personale. Imparerete molto su come le parti fondamentali di un lavoro del compilatore. Ho saltato cercando di utilizzare un generatore parser; se questo è per la vostra edificazione, imparerete di più facendo tutto da zero.

Il modo in cui questi sistemi di lavoro è una formalizzazione di come capiamo lingue naturali. Se ti do una frase: "Il cane, Rover, ha mangiato il suo cibo.", La prima cosa da fare è suddividerlo in parole e la punteggiatura. "La", "spazio", "cane", "virgola", "spazio", "Rover", ... che è "creazione di token" o "lexing".

La prossima cosa che devi fare è analizzare il flusso di token per vedere se la frase è grammaticale. La grammatica della lingua inglese è estremamente complicato, ma questa frase è abbastanza semplice. OGGETTO appositiva-VERB-OGGETTO. Questo è "Analisi".

Una volta che sai che la frase è grammaticale, è possibile analizzare la frase per ottenere effettivamente senso fuori di esso. Per esempio, si può vedere che ci sono tre parti di questa frase - il soggetto, l'appositivo, e la "sua" nell'oggetto - che si riferiscono tutti alla stessa entità, vale a dire, il cane. Si può capire che il cane è la cosa che fa il mangiare, e il cibo è la cosa di essere mangiati. Questa è la fase di analisi semantica.

I compilatori poi hanno una quarta fase che gli esseri umani non lo fanno, che è generano codice che rappresenta le azioni descritte nella lingua.

Quindi, fare tutto questo. Inizia definendo ciò che i segni della lingua sono, definire una classe base token e un gruppo di classi derivate per ciascuno. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). Quindi scrivere un metodo che prende una stringa e restituisce un IEnumerable'. Questo è il tuo lexer.

In secondo luogo, capire che cosa la grammatica del linguaggio è, e scrivere un parser discesa ricorsiva che rompe un IEnumerable in un albero di sintassi astratta che rappresenta entità grammaticali nella tua lingua.

Quindi scrivere un analizzatore che guarda quell'albero e figure roba, come "quante variabili libere distinte ho?"

Quindi scrivere un generatore di codice che sputa fuori il codice necessario per valutare le tabelle di verità. Sputare IL sembra eccessivo, ma se si voleva essere davvero appassionato, si potrebbe. Potrebbe essere più facile lasciare che la libreria di albero di espressione farlo per voi; è possibile trasformare il vostro albero sintattico in un albero di espressione, e poi girare l'albero di espressione in un delegato, e valutare il delegato.

In bocca al lupo!

Answer 2

Credo che un generatore di parser è un peso inutile. È possibile utilizzare l'idea di convertire un'espressione per Postfix e la valutazione di espressioni postfisse (o direttamente la costruzione di un albero di espressione fuori l'espressione infissa e l'utilizzo che per generare la tabella di verità) per risolvere questo problema.

Answer 3

Come Mehrdad menziona si dovrebbe essere in grado di mano rotolare il parsing nello stesso tempo che ci vuole per imparare la sintassi di un lexer / parser. Il risultato finale che si desidera è un po 'Abstract Syntax Tree (AST) dell'espressione ti è stato dato.

È quindi necessario costruire qualche generatore di input che crea le combinazioni di input per i simboli definiti nell'espressione.

Poi iterazioni attraverso il set di input, generando i risultati per ogni combinazione di ingresso, data la regole (AST) si analizzato nel primo passaggio.

Come lo farei:

potevo immaginare utilizzando le funzioni lambda per esprimere l'AST / regole, come si analizzare l'albero, e la costruzione di una tabella dei simboli come si analizza, quindi si potrebbe costruire il set di input, l'analisi della tabella dei simboli per l'albero di espressione lambda, per calcolare i risultati.

Answer 4

Se il vostro obiettivo è l'elaborazione espressioni booleane, un generatore di parser e tutto il macchinario che andare con è una perdita di tempo, a meno che non si vuole imparare come funzionano (poi nessuno di loro andrebbe bene).

Ma è facile costruire un parser ricorsivo-discesa a mano per le espressioni booleane, che calcola e restituisce i risultati di "valutare" l'espressione. Tale parser potrebbe essere utilizzata in un primo passaggio per determinare il numero di variabili uniche, dove "valutazione" significa "couunt 1 per ogni nuova variabile". Scrivendo un generatore per la produzione di tutti i possibili valori di verità per le variabili N è banale; per ogni insieme di valori, è sufficiente chiamare nuovamente il parser e utilizzarlo per valutare l'espressione, dove valutare significa "combinare i valori delle sottoespressioni secondo l'operatore".

Hai bisogno di una grammatica:

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

Il tuo può essere più complicato, ma per le espressioni booleane non può essere che molto più complicato.

Per ogni regola grammaticale, scrivere 1 subroutine che utilizza un indice globale "scan" nella stringa di essere analizzato:

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

Ogni della vostra routine di parsing sarà su questo complicato. Scherzi a parte.

Answer 5

È possibile ottenere il codice sorgente del programma pyttgen a http: / /code.google.com/p/pyttgen/source/browse/#hg/src genera tabelle di verità per espressioni logiche. Codice basato sulla libreria strati, quindi è molto semplice:)