Parse boolean số học bao gồm cả dấu ngoặc đơn với regex?

Question

Có một cụm từ thông dụng duy nhất có thể phân tích một chuỗi (trong Python và/hoặc Javascript, không cần phải là cùng một biểu thức) đại diện cho số học boolean đơn giản? Ví dụ tôi muốn phân tích chuỗi này:

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

Giả sử rằng:
* ngoặc không tổ
* các điều khoản a, b, ..., z không phải là tiểu biểu

Các kết quả thu được nên được nhóm lại bằng dấu ngoặc đơn đầu tiên, sau đó tôi phân tích lại bằng cùng một hoặc một regex đơn giản hơn.

Tôi đã thành công khi viết một regex ngây thơ để phân tích số học boolean mà không có dấu ngoặc đơn.

Bất kỳ ý tưởng nào?

Answer 1

Thông thường bạn sẽ sử dụng ví dụ như một recursive descent parser cho nhiệm vụ này, nhưng bạn có thể lấy tất cả các bộ phận (thẻ) với một 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) 

Các nhà khai thác thường có khác nhau precedence. Dấu ngoặc đơn sẽ được đánh giá trước, sau đó là biểu thức and và cuối cùng là các biểu thức or, với thứ tự từ trái sang phải trong trường hợp ưu tiên bằng nhau. Bạn nói rằng bạn muốn trả về các dấu ngoặc đơn phù hợp đầu tiên, nhưng thực sự những gì bạn thường làm là sử dụng các phần xây dựng một cây biểu thức và đánh giá đệ quy.

Answer 2

Giả sử không có tổ nào đơn giản hóa nó đến mức có thể sử dụng regex. Một regex để phù hợp với đó sẽ là (giả sử và/hoặc duy nhất, có thể dễ dàng mở rộng):

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

phần Bây giờ bạn đã ngoặc như tuples của 3 dây (operand-hành-operand) và phần còn lại của chuỗi dưới dạng chuỗi cho mỗi mã thông báo (toán tử hoặc toán hạng).

Bạn có thể xem qua danh sách, đánh giá từng biểu thức được lồng dấu và thay thế bằng kết quả. Khi đã xong, bạn có thể đi qua lại và đánh giá từ trái sang phải hoặc theo một số quy tắc ưu tiên bạn đặt (ví dụ: tiếp tục đánh giá AND cho đến khi bạn hết AND và sau đó bắt đầu đánh giá OR).

Answer 3

Các Examples page trên wiki pyparsing bao gồm một SimpleBool.py mẫu mà sẽ phân tích và đánh giá các biểu hiện như:

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, không có bất kỳ ví dụ với dấu ngoặc lồng nhau, nhưng những là . hỗ trợ quá)

Các phân tích cú pháp thực tế được xác định trong toàn bộ sử dụng mã này:

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

Phần còn lại của ví dụ cho phép thực hiện BoolNot, BoolOr và BoolAnd. Cấu trúc operatorPrecedence định nghĩa chuỗi các hoạt động, tính chất và tính liên kết của chúng, và tùy chọn một lớp được xây dựng với các phần tử được phân tích cú pháp. operatorPrecedence sau đó sẽ chăm sóc định nghĩa ngữ pháp, bao gồm định nghĩa đệ quy của boolExpr trong ngoặc đơn lồng nhau. Cấu trúc kết quả tương tự như một AST lồng nhau bằng cách sử dụng các lớp BoolXxx đã cho.Những lớp lần lượt xác định eval phương pháp để các biểu thức có thể phân tích và đánh giá sử dụng mã này:

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

pyparsing chính nó là một mô-đun hơi hơi dài, nhưng nó là một tập tin nguồn duy nhất để dấu chân cài đặt của nó là khá nhỏ. Giấy phép MIT cho phép sử dụng thương mại và phi thương mại.