¿Cómo puedo construir una Tabla de Verdad del Generador?

Question

Yo estoy buscando para escribir una Tabla de Verdad del Generador como un proyecto personal.

Hay varios basada en la web online aquí y aquí.

(Example screenshot of an existing Truth Table Generator)

Tengo las siguientes preguntas:

• ¿Cómo debo ir sobre el análisis de expresiones como: ((P => Q) & (Q => R)) => (P => R)
• Debo usar un parser generator como ANTLr o YACC, o hacia el uso de expresiones regulares?
• Una vez que tenemos la expresión analizada, ¿cómo debo ir acerca de la generación de la tabla de verdad?Cada sección de la expresión debe ser dividido en sus componentes más pequeños y re-construido desde el lado izquierdo de la tabla a la derecha.¿Cómo puedo evaluar algo como eso?

¿Alguien puede proporcionarme con consejos sobre el análisis de estas expresiones arbitrarias y, finalmente, analiza la evaluación de la expresión?

Answer 1

Esto suena como un gran proyecto personal. Vas a aprender mucho acerca de cómo las partes básicas de una obra compilador. Me saltaría tratando de utilizar un generador de analizadores sintácticos; si esto es para su propia edificación, usted aprenderá más por hacerlo todo desde cero.

La forma de estos sistemas de trabajo es una formalización de cómo entendemos las lenguas naturales. Si te doy una frase: "El perro, Rover, se comió su comida.", El primero que se hace es dividirla en palabras y puntuacion. "El", "espacio", "perro", "coma", "espacio", "Rover", ... eso es "tokenizing" o "léxico".

La siguiente cosa que se hace es analizar la corriente de contadores a ver si la frase es gramatical. La gramática del Inglés es extremadamente complicado, pero esta frase es bastante sencillo. OBJETO Appositive-verbo-objeto. Se trata de "parseo".

Una vez que sabe que la oración es gramatical, a continuación, puede analizar la frase para conseguir realmente lo que significa salir de ella. Por ejemplo, se puede ver que hay tres partes de esta frase - del sujeto, la aposición, y el "su" en el objeto - que todos se refieren a la misma entidad, a saber, el perro. Puede darse cuenta de que el perro es lo que hace el comer, y la comida es la cosa de ser comido. Esta es la fase de análisis semántico.

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

Por lo tanto, hacer todo eso. Empezar por definir lo que las señales de la lengua son, definir una clase base de emergencia y un montón de clases derivadas para cada uno. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). A continuación, escribir un método que toma una cadena y devuelve un IEnumerable'. Esa es su léxico.

En segundo lugar, averiguar lo que la gramática de la lengua es, y escribir un analizador sintáctico descendente recursivo que rompe un IEnumerable en un árbol de sintaxis abstracta que representa entidades gramaticales en su idioma.

A continuación, escribir un analizador que mira a ese árbol y cifras materia hacia fuera, al igual que "el número de variables libres distintos tengo?"

A continuación, escribir un generador de código que escupe el código necesario para evaluar las tablas de verdad. Escupiendo IL parece un exceso, pero si quería ser muy aficionado, que podía. Puede ser que sea más fácil dejar que la biblioteca árbol de expresión hacer eso por usted; usted puede transformar su árbol de análisis sintáctico en un árbol de expresión, y luego girar el árbol de expresión en un delegado, y evaluar el delegado.

Buena suerte!

Answer 2

Creo que un generador de análisis es una exageración. Se podría utilizar la idea de convertir una expresión a Postfix y evaluar expresiones postfijos (o directamente la construcción de un árbol de expresión de la expresión infija y utilizarlo para generar la tabla de verdad) para resolver este problema.

Answer 3

Como Mehrdad menciona que debe ser capaz de entregar rodar el análisis en el mismo tiempo que se tardaría en aprender la sintaxis de un analizador léxico / analizador. El resultado final que queremos es un poco de árbol de sintaxis abstracta (AST) de la expresión que se les ha dado.

A continuación, deberá construir algún generador de entrada que crea combinaciones de entradas para los símbolos definidos en la expresión.

A continuación, iterar a través de la entrada de conjunto, la generación de los resultados para cada combo de entrada, dada la reglas (AST) se analiza en el primer paso.

¿Cómo lo haría:

Me podía imaginar usando 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, usted podría entonces construir el conjunto de entrada, análisis de la tabla de símbolos con el árbol de expresión lambda, para calcular los resultados.

Answer 4

Si su objetivo está procesando expresiones booleanas, un generador de analizadores sintácticos y toda la maquinaria que ir con es una pérdida de tiempo, a menos que usted desea aprender cómo funcionan (a continuación, ninguno de ellos estaría bien).

Sin embargo, es fácil construir un analizador sintáctico descendente recursivo por parte de las expresiones booleanas, que calcula y devuelve los resultados de "evaluar" la expresión. un analizador de este tipo podría ser utilizado en un primer paso para determinar el número de variables únicas, donde "evaluación" significa "couunt 1 para cada nuevo nombre de la variable". Escribir un generador para producir todos los posibles valores de verdad para las variables N es trivial; para cada conjunto de valores, simplemente llame al analizador de nuevo y lo utilizan para evaluar la expresión, donde evaluar significa "combinar los valores de las subexpresiones de acuerdo con el operador".

Es necesario una gramática:

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

El suyo puede ser 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. En serio.

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 de una expresión lógica. Código basado en la biblioteca de capas, así que es muy sencilla:)