Как я могу создать Генератор Таблицы истинности?

Я считаю, что генератор синтаксического анализатора - это излишество. Для решения этой проблемы вы можете использовать идею преобразования выражения в постфикс и вычисления постфиксных выражений (или непосредственного построения дерева выражения из инфиксного выражения и использования его для создания таблицы истинности).

Как упоминает Мердад, у вас должна быть возможность вручную выполнить синтаксический анализ за то же время, которое потребуется для изучения синтаксиса лексера / анализатора. Конечным результатом, который вам нужен, является некоторое абстрактное синтаксическое дерево (AST) данного выражения.

Затем вам необходимо создать некоторый генератор ввода, который создает входные комбинации для символов, определенных в выражении.

Затем повторите итерацию. во входном наборе, генерируя результаты для каждой входной комбинации, учитывая правила (AST), которые вы проанализировали на первом этапе.

Как бы я это сделал:

Я мог бы представить использование лямбда-функций для выражения AST / правил при синтаксическом анализе дерева и построении таблицы символов при синтаксическом анализе вы можете построить входной набор, анализируя таблицу символов до дерева лямбда-выражения, чтобы вычислить результаты.

Если ваша цель - обработка логических выражений, генератор синтаксического анализатора и весь связанный с ним механизм - пустая трата времени, если вы не хотите узнать, как они работают (тогда подойдет любое из них

Но легко создать синтаксический анализатор с рекурсивным спуском вручную для логических выражений, который вычисляет и возвращает результаты "оценки" выражения. Такой синтаксический анализатор можно использовать на первом проходе для определения количества уникальных переменных, где «оценка» означает «couunt 1 для каждого нового имени переменной». Writing a generator to produce all possible truth values for N variables is trivial; for each set of values, simply call the parser again and use it to evaluate the expression, where evaluate means "combine the values of the subexpressions according to the operator".

You need a grammar:

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

Yours can be more complicated, but for boolean expressions it can't be that much more complicated.

For each grammar rule, write 1 subroutine that uses a global "scan" index into the string being parsed:

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

Each of your parse routines will be about this complicated. Seriously.

Вы можете получить исходный код программы pyttgen на http://code.google.com/p/pyttgen/source/browse/#hg/src Она генерирует таблицы истинности для логических выражений. Код основан на библиотеке ply, поэтому он очень прост :)