用正则表达式解析包含括号的布尔运算？

Question

有没有一种正则表达式，可以用来解析一个字符串（在Python和/或JavaScript中，不一定要是同一个表达式），这个字符串表示简单的布尔运算？比如，我想解析这个字符串：

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

假设：
* 括号不嵌套
* 变量a、b、...、z不是子表达式

解析的结果应该先按括号分组，然后我再用同样的或更简单的正则表达式进行进一步解析。

我之前成功写过一个简单的正则表达式，用来解析没有括号的布尔运算。

有没有什么想法？

Answer 1

在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类构建的嵌套抽象语法树（AST）。这些类又定义了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 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')]

现在你有了用括号括起来的部分，这些部分可以看作是三个字符串的元组（操作数-运算符-操作数），而字符串的其余部分则是每个符号（运算符或操作数）的字符串。

你可以遍历这个列表，计算每个括号内的表达式，并用结果替换它。一旦完成这个步骤，你可以再遍历一次，根据你设定的规则从左到右计算，或者按照某些优先级规则进行计算（例如，先计算所有的与运算，直到没有与运算为止，然后再开始计算或运算）。

Answer 3

通常情况下，你会使用一种叫做递归下降解析器的工具来完成这个任务，但你也可以用正则表达式来获取所有的部分（也就是“标记”）：

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表达式。如果优先级相同，就从左到右计算。你提到想先返回括号匹配的部分，但实际上，通常的做法是用这些部分构建一个表达式树，然后递归地计算这个树。