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

Ответ 1

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

Как работают такие системы, это формализация того, как мы понимаем естественные языки. Если я дам вам предложение: "Собака, Ровер, съел свою еду". Первое, что вы делаете, это разбить ее на слова и знаки препинания. "The", "SPACE", "dog", "COMMA", "SPACE", "Rover",... "токенизация" или "лексирование".

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

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

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

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

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

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

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

Удачи!

Ответ 2

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Но легко построить парсер рекурсивного спуска вручную для булевых выражений, который вычисляет и возвращает результаты "оценки" выражения. Такой синтаксический анализатор можно использовать на первом проходе, чтобы определить количество уникальных переменных, где "оценка" означает "курант 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
       }
     ...
  }

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

Ответ 5

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