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

Я хочу написать Truth Table Generator как личный проект.

Здесь и здесь есть несколько онлайн-сайтов.

альтернативный текст
(Example screenshot of an existing Truth Table Generator )

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

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

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

Источник

5 ответов

Решение

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

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

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

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

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

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

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

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

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

Удачи!

Источник

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

Источник

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

Источник
Другие вопросы по тегам