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

StackOverflow https://stackoverflow.com/questions/1084873

Вопрос

Я собираюсь написать генератор таблиц истинности в качестве личного проекта.

Существует несколько онлайновых веб-сайтов здесь и здесь.

alt text
(Example screenshot of an existing Truth Table Generator)

У меня есть следующие вопросы:

  • Как мне следует приступить к разбору выражений типа: ((P => Q) & (Q => R)) => (P => R)
  • Должен ли я использовать генератор синтаксического анализа, такой как ANTLr или YACC, или использовать прямые регулярные выражения?
  • Как только я проанализирую выражение, как мне следует приступить к созданию таблицы истинности?Каждый раздел выражения необходимо разделить на его наименьшие компоненты и перестроить из левой части таблицы в правую.Как бы я оценил что-то подобное?

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

Это было полезно?

Решение

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

То, как работают такие системы, является формализацией того, как мы понимаем естественные языки.Если я дам тебе предложение:"Собака, Ровер, съела свою еду"., первое, что вы делаете, это разбиваете это на слова и расставляете знаки препинания."The", "SPACE", "собака", "ЗАПЯТАЯ", "КОСМОС", "Ровер", ...Это "токенизация" или "лексизация".

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

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

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

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

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

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

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

Удачи вам!

Другие советы

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

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

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

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

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

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

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

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

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

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 Он генерирует таблицы истинности для логических выражений.Код основан на библиотеке ply, поэтому он очень простой :)

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top