Parse boolean arithmetic including parentheses?

Question

Is there a single regular expression that can parse a string (in Python and Javascript, does not need to be the same expression) that represents simple boolean arithmetic? For example I want to parse this string:

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

Assuming that:
* parentheses do not nest
* the terms a, b, ..., z are not sub-expressions

The resulting captures should be grouped by parentheses first, which I then parse again with the same or a simpler regex.

I've had success writing a naive regex for parsing boolean arithmetic without parentheses.

Any ideas?

Answer 1

Normally you would use for example a recursive descent parser for this task, but you can grab all the parts (tokens) with a regex:

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)

The operators usually have different precedence. Parentheses would be evaluated first, then and expressions, and finally or expressions, with left-to-right order in case of equal precedence. You say you want to return the parentheses matches first, but actually what you would normally do is to use the parts build an expression tree and evalulate that recursively.

Answer 2

Assuming no nesting simplifies it to a level where regex can be used. A regex to match that would be (assuming and/or only, can be easily extended):

>>> 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')]

Now you have parenthesized parts as tuples of 3 strings (operand-operator-operand) and the rest of the string as strings for each token (operator or operand).

You can walk through the list, evaluate each parenthesized expression, and replace it with the result. Once that is done, you can walk through it again and evaluate either from left to right or according to some precedence rules you set (e.g. keep evaluating ANDs only until you run out of ANDs, then start evaluating ORs).

Answer 3

The Examples page on the pyparsing wiki includes a sample SimpleBool.py that will parse and evaluate expressions such as:

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",
        ]

(Hmmm, there aren't any examples with nested parens, but these are supported too.)

The actual parser is defined in its entirety using this code:

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),
    ])

The remainder of the example gives the implementations of BoolNot, BoolOr, and BoolAnd. The operatorPrecedence construct defines the sequence of operations, their arity and associativity, and optionally a class to be constructed with the parsed elements. operatorPrecedence then takes care of defining the grammar, including recursive definition of boolExpr's within nested parentheses. The resulting structure is similar to a nested AST using the given BoolXxx classes. These classes in turn define eval methods so that the expressions can parsed and evaluated using this code:

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

pyparsing itself is a somewhat longish module, but it is a single source file so its installation footprint is pretty small. MIT license permits both noncommercial and commercial use.