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

Это звучит как отличный личный проект. Вы многое узнаете о том, как работают основные части компилятора. Я бы не пытался использовать генератор синтаксических анализаторов; если это для вашего собственного назидания, вы узнаете больше, делая все это с нуля.

То, как работают такие системы, — это формализация того, как мы понимаем естественные языки. Если я даю вам предложение: «Собака, Ровер, съел свою еду», первое, что вы делаете, это разбиваете его на слова и ставите знаки препинания. «The», «SPACE», «собака», «COMMA», «SPACE», «Rover», ... Это «токенизация» или «лексинг».

Следующее, что вы делаете, это анализируете поток токенов, чтобы увидеть, является ли предложение грамматическим. Грамматика английского языка чрезвычайно сложна, но это предложение довольно простое. ПОДЛЕЖАЩЕЕ-ПРИЛОЖИТЕЛЬНОЕ-ГЛАГОЛ-ОБЪЕКТ. Это "разбор".

Как только вы узнаете, что предложение является грамматическим, вы можете проанализировать предложение, чтобы на самом деле извлечь из него смысл. Например, вы можете видеть, что в этом предложении есть три части — подлежащее, прилагательное и «его» в дополнении — и все они относятся к одному и тому же объекту, а именно к собаке. Вы можете понять, что собака — это то, что ест, а еда — это то, что едят. Это этап семантического анализа.

Затем у компиляторов есть четвертая фаза, которой нет у людей: они генерируют код, представляющий действия, описанные в языке.

Итак, сделайте все это. Начните с определения токенов вашего языка, определите токен базового класса и набор производных классов для каждого. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken...). Затем напишите метод, который принимает строку и возвращает IEnumerable. Это твой лексер.

Во-вторых, выясните, что такое грамматика вашего языка, и напишите синтаксический анализатор рекурсивного спуска, который разбивает IEnumerable на абстрактное синтаксическое дерево, представляющее грамматические сущности вашего языка.

Затем напишите анализатор, который просматривает это дерево и вычисляет такие вещи, как «сколько различных свободных переменных у меня есть?»

Затем напишите генератор кода, который выдает код, необходимый для оценки таблиц истинности. Плюнуть IL кажется излишним, но если вы хотите быть действительно крутым, вы можете это сделать. Может быть проще позволить библиотеке дерева выражений сделать это за вас; вы можете преобразовать дерево синтаксического анализа в дерево выражений, а затем превратить дерево выражений в делегат и оценить делегат.

Удачи!

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

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

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

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

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

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

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

Но легко вручную создать анализатор рекурсивного спуска для логических выражений, который вычисляет и возвращает результаты «вычисления» выражения. Такой синтаксический анализатор можно использовать при первом проходе для определения количества уникальных переменных, где «оценка» означает «счет 1 для каждого нового имени переменной». Написание генератора для получения всех возможных значений истинности для N переменных тривиально; для каждого набора значений просто снова вызовите синтаксический анализатор и используйте его для оценки выражения, где оценка означает «объединить значения подвыражений в соответствии с оператором».

Вам нужна грамматика:

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

У вас может быть сложнее, но для логических выражений это не может быть намного сложнее.

Для каждого правила грамматики напишите 1 подпрограмму, которая использует глобальный индекс «сканирования» в анализируемой строке:

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

Каждая из ваших подпрограмм синтаксического анализа будет примерно такой сложной. Шутки в сторону.

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