Como posso construir um gerador de tabela de verdade?

Question

Eu estou olhando para escrever um gerador de tabela de verdade como um projeto pessoal.

Existem várias outras on-line baseado na web aqui e aqui .

(Example screenshot of an existing Truth Table Generator)

Eu tenho as seguintes perguntas:

• Como devo ir sobre análise de expressões como: ((P => Q) e (Q => R)) => (P => R)
• Devo usar um gerador de analisador como antlr ou YACC, ou usar expressões reta regulares?
• Assim que eu tiver a expressão analisada, como devo ir sobre gerar a tabela de verdade? Cada seção das necessidades de expressão para ser dividido em seus componentes menores e re-construído a partir do lado esquerdo da tabela à direita. Como eu iria avaliar algo assim?

Alguém pode me fornecer dicas sobre a análise dessas expressões arbitrárias e eventualmente avaliar a expressão analisada?

Answer 1

Isso soa como um grande projeto pessoal. Você vai aprender muito sobre como as partes básicas de um trabalho compilador. Gostaria que ignorar tentando usar um gerador de analisador; se isto é para sua própria edificação, você vai aprender mais, fazer tudo a partir do zero.

A forma como esses sistemas de trabalho é uma formalização de como entendemos línguas naturais. Se eu lhe der uma frase: "O cão, Rover, comeu sua comida.", A primeira coisa a fazer é dividi-lo em palavras e sinais de pontuação. "A", "Espaço", "cão", "vírgula", "Espaço", "Rover", ... que é "tokenizing" ou "léxico".

A próxima coisa a fazer é analisar o fluxo de token para ver se a sentença é gramatical. A gramática de Inglês é extremamente complicado, mas esta frase é bastante simples. -Sujeito-verbo-objeto aposta. Isto é "análise".

Depois de saber que a sentença é gramatical, você pode, então, analisar a sentença para começar realmente o que significa fora dele. Por exemplo, você pode ver que existem três partes desta frase - o sujeito, o appositive, eo "seu" no objeto - que todos se referem à mesma entidade, ou seja, o cão. Você pode descobrir que o cão é a coisa a fazer o comer, ea comida é a coisa a ser comido. Esta é a fase de análise semântica.

Compiladores, então, uma quarta fase que os humanos não fazem, que é que eles geram código que representa as ações descritas na língua.

Então, fazer tudo isso. Comece por definir o que os sinais da sua linguagem são, definir uma classe base token e um monte de classes derivadas para cada um. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). Em seguida, escrever um método que leva uma string e retorna um IEnumerable'. Esse é o seu lexer.

Em segundo lugar, descobrir o que a gramática da sua língua é, e escrever um analisador descendente recursivo que ir além, um IEnumerable em uma árvore de sintaxe abstrata que representa entidades gramaticais no seu idioma.

Em seguida, escrever um analisador que olha para aquela árvore e figuras coisas fora, como "quantos distintas variáveis ??livre eu tenho?"

Em seguida, escreva um gerador de código que cospe o código necessário para avaliar as tabelas de verdade. Cuspir IL parece um exagero, mas se você quiser ser realmente lustre, você poderia. Pode ser mais fácil deixar a biblioteca árvore de expressão fazer isso por você; você pode transformar sua árvore de análise em uma árvore de expressão, e em seguida, vire a árvore de expressão para um delegado, e avaliar o delegado.

Boa sorte!

Answer 2

Eu acho que um gerador de analisador é um exagero. Você pode usar a idéia de converter uma expressão de postfix e avaliar expressões postfix (ou diretamente a construção de uma árvore de expressão fora da expressão infix e usando isso para gerar a tabela de verdade) para resolver este problema.

Answer 3

Como Mehrdad menciona que você deve ser capaz de rolo mão a análise no mesmo tempo que seria necessário para aprender a sintaxe de um lexer / parser. O resultado final que você quer é alguma Abstract Syntax Tree (AST) da expressão que lhe foi dada.

Você precisa então construir algum gerador de entrada que cria as combinações de entrada para os símbolos definidos na expressão.

Em seguida, iterate em todo o conjunto de entrada, gerando os resultados para cada combinação de entrada, dadas as regras (AST) você analisado na primeira etapa.

Como eu faria isso:

Eu poderia imaginar usando funções lambda para expressar a AST / regras como você analisar a árvore, e construir uma tabela de símbolos como você analisar, então você pode construir o conjunto de entrada, analisar a tabela de símbolos para a árvore de expressão lambda, para calcular os resultados.

Answer 4

Se o seu objetivo é o processamento de expressões booleanas, um gerador de analisador e toda a maquinaria que ir com é um desperdício de tempo, a menos que você quiser aprender como eles funcionam (então qualquer um deles seria ótimo).

Mas é fácil de construir um analisador descendente recursivo à mão para expressões booleanas, que calcula e retorna os resultados de "avaliar" a expressão. Um tal analisador pode ser utilizado em uma primeira passagem para determinar o número de variáveis ??únicas, onde "avaliação" meios "couunt um para cada novo nome da variável". Escrevendo um gerador para produzir todos os valores de verdade possíveis para as variáveis ??N é trivial; para cada conjunto de valores, basta ligar para o analisador novamente e usá-lo para avaliar a expressão, onde Avaliar significa "combinar os valores das subexpressions de acordo com o operador".

Você precisa de uma gramática:

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

O seu pode ser mais complicado, mas para expressões booleanas não pode ser muito mais complicado.

Para cada regra de gramática, escrita 1 sub-rotina que utiliza um índice global "scan" na seqüência que está sendo analisado:

  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 um de suas rotinas de análise será sobre este complicado. A sério.

Answer 5

Você pode obter o código-fonte do programa pyttgen em http: / /code.google.com/p/pyttgen/source/browse/#hg/src Ele gera tabelas de verdade para expressões lógicas. Código baseado na biblioteca ply, por isso é muito simples:)