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

Question

Я ищу, чтобы написать Генератор Таблицы Прав в качестве личного проекта.

Количество веб-сайтов: онлайн-магазины here и here.

(Example screenshot of an existing Truth Table Generator)

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

Удачи вам!

Answer 2

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

Answer 3

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

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

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

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

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

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

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

Answer 5

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