¿Cómo puedo construir un Truth Table Generator?

Question

Estoy buscando escribir Truth Table Generator como un proyecto personal.

Hay varios online en línea here y here.

(Example screenshot of an existing Truth Table Generator)

Tengo las siguientes preguntas:

• ¿Cómo debo ir sobre análisis de expresiones como: ((P => Q) & (Q => R)) => (P => R)
• ¿Debo usar un generador de analizadores como ANTLr o YACC, o usar expresiones regulares rectas?
• Una vez que haya analizado la expresión, ¿cómo debo generar la tabla de verdad? Cada sección de la expresión debe dividirse en sus componentes más pequeños y reconstruirse desde el lado izquierdo de la tabla a la derecha. ¿Cómo evaluaría algo así?

¿Alguien me puede dar consejos sobre el análisis de estas expresiones arbitrarias y, finalmente, la evaluación de la expresión analizada?

Answer 1

Esto suena como un gran proyecto personal. Aprenderá mucho sobre cómo funcionan las partes básicas de un compilador. Me saltaría el intentar usar un generador de analizador sintáctico; si esto es para su propia edificación, aprenderá más haciendo todo desde cero.

La forma en que funcionan estos sistemas es una formalización de cómo entendemos los lenguajes naturales. Si le doy una oración: "El perro, Rover, se comió su comida", lo primero que debe hacer es dividirlo en palabras y signos de puntuación. "The", "SPACE", "dog", "COMMA", "SPACE", "Rover", ... Eso es "tokenizing" o "lexing".

Lo siguiente que debes hacer es analizar la secuencia del token para ver si la oración es gramatical. La gramática del inglés es extremadamente complicada, pero esta frase es bastante sencilla. SUJETO-APLICATIVO-VERBO-OBJETO. Esto es "analizar".

Una vez que sepa que la oración es gramatical, puede analizar la oración para extraerle significado. Por ejemplo, puede ver que hay tres partes de esta oración, el sujeto, el apositivo y el "su" en el objeto, que todos se refieren a la misma entidad, es decir, el perro. Puedes darte cuenta de que el perro es el que hace la comida, y la comida es lo que se come. Esta es la fase de análisis semántico.

Los compiladores tienen una cuarta fase que los humanos no tienen, es decir, generan un código que representa las acciones descritas en el lenguaje.

Entonces, haz todo eso. Comience definiendo cuáles son los tokens de su idioma, defina un Token de clase base y un grupo de clases derivadas para cada uno. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). Luego escribe un método que toma una cadena y devuelve un IEnumerable '. Esa es tu Lexer.

En segundo lugar, descubra cuál es la gramática de su idioma y escriba un analizador de descenso recursivo que descompone un IEnumerable en un árbol de sintaxis abstracta que representa entidades gramaticales en su idioma.

Luego escribe un analizador que mira ese árbol y calcula cosas, como "¿cuántas variables libres distintas tengo?"

Luego escriba un generador de código que escuche el código necesario para evaluar las tablas de verdad. Escupir IL parece exagerado, pero si querías ser realmente aficionado, podrías. Puede ser más fácil dejar que la biblioteca del árbol de expresiones lo haga por usted; puede transformar su árbol de análisis sintáctico en un árbol de expresiones, y luego convertir el árbol de expresiones en un delegado y evaluar al delegado.

¡Buena suerte!

Answer 2

Creo que un generador de analizador es una exageración. Puede usar la idea de convertir una expresión a postfix y evaluating postfix expressions (o crear directamente un árbol de expresiones a partir de la expresión infija y usar eso para generar la tabla de verdad) para resolver este problema.

Answer 3

Como Mehrdad menciona, debería poder pasar el análisis a mano en el mismo tiempo que llevaría aprender la sintaxis de un lexer/analizador. El resultado final que desea es un Árbol de sintaxis abstracta (AST) de la expresión que le han dado.

Luego necesita construir un generador de entrada que cree las combinaciones de entrada para los símbolos definidos en la expresión.

Luego itere a través del conjunto de entrada, generando los resultados para cada combo de entrada, dadas las reglas (AST) que analizó en el primer paso.

¿Cómo lo haría:

que podía imaginar el uso de las funciones lambda para expresar la AST/reglas a medida que analizar el árbol, y la construcción de una tabla de símbolos a medida que analizar sintácticamente, a continuación, podría construir el conjunto de entrada , analizando la tabla de símbolos en el árbol de expresiones lambda, para calcular los resultados.

Answer 4

Si su objetivo es procesar expresiones booleanas, un generador de analizador y toda la maquinaria que lo acompaña es una pérdida de tiempo, a menos que desee saber cómo funcionan (entonces cualquiera de ellos estaría bien).

Pero es fácil construir un analizador de descenso recursivo a mano para expresiones booleanas, que calcula y devuelve los resultados de "evaluar" la expresión. Tal analizador podría usarse en una primera pasada para determinar el número de variables únicas, donde "evaluación" significa "couunt 1 para cada nuevo nombre de variable". Escribir un generador para producir todos los valores de verdad posibles para N variables es trivial; para cada conjunto de valores, simplemente llame al analizador nuevamente y úselo para evaluar la expresión, donde evaluar significa "combinar los valores de las subexpresiones según el operador".

Usted necesita una gramática:

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

te es más complicado, pero para expresiones booleanas no puede ser mucho más complicado.

Para cada regla gramatical, escribir 1 subrutina que utiliza un índice global "exploración" en la cadena que se está analizando:

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

Cada una de las rutinas de análisis sintáctico habrá sobre este complicado. Seriamente.

Answer 5

Puede obtener el código fuente del programa pyttgen en http://code.google.com/p/pyttgen/source/browse/#hg/src Genera tablas de verdad para expresiones lógicas.Código basado en la biblioteca de capas, por lo que es muy simple :)