Как применить закон Моргана к анализируемой строке? (трансформирование строки или парсекция)

Question

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

Мне удалось оценить, правильно ли сформирована формула или нет:

from pyparsing import *
from string import lowercase

def fbf():

    atom = Word(lowercase, max=1) #alfabeto minusculas
    op = oneOf('^ V => <=>') #Operadores
    identOp = oneOf('( [ {')
    identCl = oneOf(') ] }')
    form = Forward() #Iniciar de manera recursiva
    #Gramatica
    form << ( (Group(Literal('~') + form)) | ( Group(identOp + form + op + form + identCl) ) | ( Group(identOp + form + identCl) ) | (atom) )

    return form

#Haciendo todo lo que se debe
entrada = raw_input("Entrada: ")
try:
    print fbf().parseString(entrada, parseAll=True)
except ParseException as error: #Manejando error
    print error.markInputline()
    print error
print

Теперь мне нужно преобразовать отрицательную форумную форму в соответствии с Законом Монргана, БНФ Закона Моргана, примерно так:

~((form) V (form)) = (~(form) ^ ~(form))
~((form) ^ (form)) = (~(form) V ~(form))

http://en.wikipedia.org/wiki/De_Morgans_laws

Разбор должен быть рекурсивным; Я читал о Parseactions, но я не совсем понимаю, что я новичок в Python и очень неквалифицированный.

Может кто-нибудь помочь мне, как заставить это работать?

Answer 1

Хуан Хосе -

Вы просите много работы со стороны этой аудитории, понимаете ли вы это или нет. Вот несколько советов о том, как добиться прогресса в решении этой проблемы:

• Признайте, что анализ входных данных - это только первый шаг в этой общей программе. Вы не можете просто написать парсер, который проходит через ввод, а затем объявить себя готовым к следующему шагу. Вы должны предугадать, что вы будете делать с проанализированным выводом, и попытаться проанализировать данные таким образом, чтобы он подготовил вас к следующему шагу - который в вашем случае состоит в том, чтобы выполнить некоторые логические преобразования для применения законов DeMorgans. На самом деле, вам лучше всего работать в обратном направлении - предположим, у вас есть парсер, с чем вам понадобится код преобразования, как будет выглядеть выражение и как вы будете выполнять само преобразование? Это естественным образом структурирует ваше мышление в предметной области и даст вам целевой формат результата, когда вы начнете писать анализатор.

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

• Найдите время, чтобы написать BNF для синтаксиса, который вы будете анализировать. Напишите несколько примеров тестовых строк, которые вы могли бы проанализировать, чтобы предвидеть проблемы с синтаксисом. Является ли "~~p ^ q V r" допустимой строкой? Могут ли идентификаторы состоять из нескольких символов, или вы будете ограничиваться только одним символом (с одним будет легче работать в начале, а потом вы сможете легко его расширить)? Сохраняйте синтаксис простым, если можете, например, просто поддерживая () для группировки, вместо любой соответствующей пары (), [] или {}.

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

• В качестве совета по реализации ознакомьтесь с использованием помощника operatorPrecedence, так как он специально разработан для этих типов задач анализа. Посмотрите, как он используется в SimpleBool.py для создания иерархии объектов, которая отражает структуру входной строки. Затем подумайте, что объекты будут делать в процессе трансформации.

Удачи!