Разбор логической арифметики, включая скобки с регулярным выражением?

Question

Существует ли единственное регулярное выражение, которое может анализировать строку (в Python и / или Javascript, не обязательно должно быть одно и то же выражение), которая представляет простую логическую арифметику? Например, я хочу разобрать эту строку:

a and (b and c) and d or e and (f or g)

Предполагая, что:
* круглые скобки не гнездятся
* термины a, b, ..., z не являются подвыражениями

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

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

Есть идеи?

Answer 1

Обычно для этой задачи вы используете, например, парсер рекурсивного спуска , но вы можете получить все части (токены) с помощью регулярного выражения:

x = 'a and (b and c) and d or e and (f or g)'
import re

matches = re.findall(r'\(.*?\)|\w+', x)
print ','.join(matches)

Операторы обычно имеют различный приоритет . Сначала скобки будут оцениваться, затем выражения and и, наконец, выражения or, с порядком слева направо в случае равного приоритета. Вы говорите, что сначала хотите вернуть совпадения в скобках, но на самом деле вы обычно используете части для построения дерева выражений и рекурсивного вычисления этого значения.

Answer 2

Страница Примеры на вики-сайте pyparsing содержит пример SimpleBool.py, который будет анализировать и оценивать выражения, такие как:

test = ["p and not q",
        "not not p",
        "not(p and q)",
        "q or not p and r",
        "q or not (p and r)",
        "p or q or r",
        "p or q or r and False",
        ]

(Хммм, примеров с вложенными паренами нет, но эти также поддерживаются .)

Фактический синтаксический анализатор полностью определен с использованием этого кода:

boolOperand = Word(alphas,max=1) | oneOf("True False")
boolExpr = operatorPrecedence( boolOperand,
    [
    ("not", 1, opAssoc.RIGHT, BoolNot),
    ("and", 2, opAssoc.LEFT,  BoolAnd),
    ("or",  2, opAssoc.LEFT,  BoolOr),
    ])

В оставшейся части примера приведены реализации BoolNot, BoolOr и BoolAnd. Конструкция operatorPrecedence определяет последовательность операций, их арность и ассоциативность, а также, необязательно, класс, который будет создан с проанализированными элементами. Затем operatorPrecedence позаботится об определении грамматики, включая рекурсивное определение boolExpr во вложенных скобках. Результирующая структура похожа на вложенную AST с использованием данных классов BoolXxx. Эти классы, в свою очередь, определяют eval методы, так что выражения могут быть проанализированы и оценены с использованием этого кода:

p = True
q = False
r = True
for t in test:
    res = boolExpr.parseString(t)[0]
    print t,'\n', res, '=', bool(res),'\n'

pyparsing сам по себе является довольно длинным модулем, но это единственный исходный файл, поэтому его площадь установки довольно мала. Лицензия MIT разрешает некоммерческое и коммерческое использование.

Answer 3

Предполагая, что отсутствие вложений упрощает его до уровня, где можно использовать регулярные выражения. Регулярное выражение для сопоставления, которое будет (при условии и / или только, может быть легко расширено):

>>> expr = 'a and (b and c) and d or e and (f or g)'
>>> regex = re.compile('\((\w+)\s+(and|or)\s+(\w)\)|(\w+)')
>>> results = regex.findall(expr)
>>> results = [i[:3] if i[0] else i[3] for i in results]
>>> results
['a', 'and', ('b', 'and', 'c'), 'and', 'd', 'or', 'e', 'and', ('f', 'or', 'g')]

Теперь у вас есть заключенные в скобки части в виде кортежей из 3 строк (операнд-оператор-операнд) и остальная часть строки в виде строк для каждого токена (оператора или операнда).

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