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

Question

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

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

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

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

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

Любые идеи?

Answer 1

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

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) 

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

Answer 2

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

>>> 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, а затем начните оценивать ORs).

Answer 3

Examples page на 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 в вложенных круглых скобках. Полученная структура похожа на вложенный АСТ с использованием заданных классов 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 разрешает как некоммерческое, так и коммерческое использование.