Come posso creare un generatore di tabelle di verità?

Question

Sto cercando di scrivere un generatore di tabelle della verità come un progetto personale.

Ci sono diversi online online here e here.

(Example screenshot of an existing Truth Table Generator)

Ho le seguenti domande:

• Come devo fare per l'analisi di espressioni come: ((P => Q) & (Q => R)) => (P => R)
• Devo utilizzare un generatore di parser come ANTLr o YACC o utilizzare le espressioni regolari diritte?
• Una volta che ho analizzato l'espressione, come devo fare per generare la tabella di verità? Ogni sezione dell'espressione deve essere divisa nei suoi componenti più piccoli e ricostruita dal lato sinistro del tavolo a destra. Come potrei valutare qualcosa del genere?

Qualcuno può fornirmi suggerimenti sull'analisi di queste espressioni arbitrarie e alla fine valutare l'espressione analizzata?

Answer 1

Questo suona come un grande progetto personale. Imparerai molto su come funzionano le parti di base di un compilatore. Vorrei saltare cercando di usare un generatore di parser; se questo è per la tua edificazione, imparerai di più facendo tutto da zero.

Il modo in cui tali sistemi funzionano è una formalizzazione di come intendiamo i linguaggi naturali. Se ti do una frase: "Il cane, Rover, mangiò il suo cibo". La prima cosa che fai è scomporla in parole e punteggiatura. "Il", "SPAZIO", "cane", "COMMA", "SPAZIO", "Rover", ... Questo è "tokenizing" o "lexing".

La prossima cosa da fare è analizzare il flusso di token per vedere se la frase è grammaticale. La grammatica dell'inglese è estremamente complicata, ma questa frase è piuttosto semplice. OGGETTO appositiva-VERB-OGGETTO. Questo è "parsing".

Una volta che la frase è grammaticale, è possibile analizzare la frase per ricavarne effettivamente il significato. Ad esempio, puoi vedere che ci sono tre parti di questa frase - il soggetto, l'appositivo e il "suo" nell'oggetto - che si riferiscono tutte alla stessa entità, cioè il cane. Puoi capire che il cane è la cosa che fa mangiare e il cibo è la cosa che viene mangiata. Questa è la fase di analisi semantica.

I compilatori hanno quindi una quarta fase che gli umani non fanno, ovvero generano codice che rappresenta le azioni descritte nella lingua.

Quindi, fare tutto questo. Inizia definendo quali sono i token della tua lingua, definisci un token di classe base e un gruppo di classi derivate per ognuno. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). Quindi scrivi un metodo che accetta una stringa e restituisce un oggetto IEnumerable '. Questo è il tuo lexer.

In secondo luogo, capire qual è la grammatica della propria lingua e scrivere un parser di discesa ricorsivo che suddivida un oggetto IEnumerable in un albero di sintassi astratto che rappresenta le entità grammaticali nella propria lingua.

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

Quindi scrivere un generatore di codice che sputa il codice necessario per valutare le tabelle di verità. Sputare IL sembra eccessivo, ma se volessi essere davvero appassionato, potresti farlo. Potrebbe essere più semplice lasciare che la libreria dell'albero delle espressioni lo faccia per te; è possibile trasformare il proprio albero di analisi in un albero di espressioni, quindi trasformare l'albero delle espressioni in delegato e valutare il delegato.

Buona fortuna!

Answer 2

Penso che un generatore di parser sia eccessivo. È possibile utilizzare l'idea di convertire un'espressione in postfix e evaluating postfix expressions (o creare direttamente un albero di espressioni dall'espressione infix e utilizzarla per generare la tabella di verità) per risolvere questo problema.

Answer 3

Come menziona Mehrdad, dovresti essere in grado di eseguire il parsing nello stesso tempo necessario per imparare la sintassi di un lexer/parser. Il risultato finale che vuoi è un Abstract Syntax Tree (AST) dell'espressione che ti è stata data.

È quindi necessario creare un generatore di input che crei le combinazioni di input per i simboli definiti nell'espressione.

Quindi iterare attraverso il set di input, generando i risultati per ogni combinazione di input, in base alle regole (AST) analizzate nel primo passaggio.

Come lo farei:

potevo immaginare utilizzando le funzioni lambda per esprimere l'AST/regole, come si analizza l'albero, e la costruzione di una tabella dei simboli come si analizza, poi potuto costruire il set di input , analizzando la tabella dei simboli sull'albero delle espressioni lambda, per calcolare i risultati.

Answer 4

Se il tuo obiettivo è l'elaborazione di espressioni booleane, un generatore di parser e tutti i macchinari necessari sono una perdita di tempo, a meno che tu non voglia imparare come funzionano (quindi nessuno di essi andrebbe bene).

Ma è facile creare un parser di discesa ricorsiva a mano per le espressioni booleane, che calcola e restituisce i risultati di "valutare" l'espressione. Tale parser potrebbe essere utilizzato su una prima passata per determinare il numero di variabili univoche, dove "valutazione" significa "couunt 1 per ogni nuovo nome di variabile". Scrivere un generatore per produrre tutti i possibili valori di verità per le variabili N è banale; per ogni set di valori, basta richiamare di nuovo il parser e utilizzarlo per valutare l'espressione, dove valutare significa "combinare i valori delle sottoespressioni in base all'operatore".

È necessario una grammatica:

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

Distinti 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 viene analizzata:

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

Ognuno di vostra routine di parsing sarà su questo complicato. Sul serio.

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 le espressioni logiche.Codice basato sulla libreria di strati, quindi è molto semplice :)