phân tích cú pháp một biểu thức logic phức tạp trong pyparsing theo kiểu cây nhị phân

Question

Tôi đang cố gắng phân tích biểu thức logic phức tạp như biểu thức dưới đây;

x > 7 AND x < 8 OR x = 4 

và nhận chuỗi được phân tích cú pháp dưới dạng cây nhị phân. Đối với biểu thức ở trên, biểu thức được phân tích cú pháp được mong đợi sẽ trông giống như

[['x', '>', 7], 'AND', [['x', '<', 8], 'OR', ['x', '=', 4]]] 

Toán tử logic 'OR' có ưu tiên cao hơn toán tử 'AND'. Dấu ngoặc đơn có thể ghi đè quyền ưu tiên mặc định. Nói chung hơn, biểu thức được phân tích cú pháp sẽ trông giống như;

<left_expr> <logical_operator> <right_expr> 

Một ví dụ khác sẽ

input_string = x > 7 AND x < 8 AND x = 4 
parsed_expr = [[['x', '>', 7], 'AND', ['x', ',', 8]], 'AND', ['x', '=', 4]] 

Cho đến nay tôi đã đưa ra giải pháp này đơn giản mà thật đáng buồn không thể tạo biểu phân tích cú pháp theo kiểu cây nhị phân. operatorPrecedence dường như không giúp tôi ở đây, nơi có cùng một toán tử lô-gic liên tiếp như trong ví dụ trước.

import pyparsing as pp 
complex_expr = pp.Forward() 
operator = pp.Regex(">=|<=|!=|>|<|=").setName("operator") 
logical = (pp.Keyword("AND") | pp.Keyword("OR")).setName("logical") 
vars = pp.Word(pp.alphas, pp.alphanums + "_") | pp.Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?") 
condition = (vars + operator + vars) 
clause = pp.Group(condition^(pp.Suppress("(") + complex_expr + pp.Suppress(")"))) 

expr = pp.operatorPrecedence(clause,[ 
          ("OR", 2, pp.opAssoc.LEFT,), 
          ("AND", 2, pp.opAssoc.LEFT,),]) 

complex_expr << expr 
print complex_expr.parseString("x > 7 AND x < 8 AND x = 4") 

Mọi đề xuất hoặc hướng dẫn đều được đánh giá cao.

BNF cho biểu thức (không có dấu ngoặc đơn) có thể là

<expr>  -> <expr> | <expr> <logical> <expr> 
<expr>  -> <opnd> <relational> <opnd> 
<opnd>  -> <variable> | <numeric> 
<relational> -> <'>'> | <'='> | <'>='> | <'<='> | <'!='> 

Answer 1

Hãy thử thay đổi:

expr = pp.operatorPrecedence(clause,[ 
          ("OR", 2, pp.opAssoc.LEFT,), 
          ("AND", 2, pp.opAssoc.LEFT,),]) 

tới:

expr = pp.operatorPrecedence(condition,[ 
          ("OR", 2, pp.opAssoc.LEFT,), 
          ("AND", 2, pp.opAssoc.LEFT,),]) 

Đối số đầu tiên để operatorPrecedence là toán hạng nguyên thủy để được sử dụng với các toán tử - không cần phải bao gồm complexExpr của bạn dấu ngoặc đơn - operatorPrecedence sẽ làm điều đó cho bạn. Kể từ khi toán hạng của bạn thực sự là một sự so sánh sâu hơn, bạn có thể xem xét thay đổi:

condition = (expr + operator + expr) 

tới:

condition = pp.Group(expr + operator + expr) 

để đầu ra của operatorPrecedence là dễ dàng hơn để xử lý. Với những thay đổi này, phân tích x > 7 AND x < 8 OR x = 4 cho:

[[['x', '>', '7'], 'AND', [['x', '<', '8'], 'OR', ['x', '=', '4']]]] 

công nhận ưu tiên và nhóm nó cao hơn OR đầu tiên. (Bạn có chắc là bạn muốn thứ tự này của AND và OR được ưu tiên không? Tôi nghĩ rằng thứ tự truyền thống là ngược lại, như được hiển thị trong this wikipedia entry.)

Tôi nghĩ bạn cũng hỏi tại sao pyparsing và operatorPrecedence không trả về kết quả trong lồng nhau cặp nhị phân, nghĩa là bạn mong đợi phân tích cú pháp "A và B và C" sẽ quay trở lại:

[['A', 'and', 'B'] 'and', 'C'] 

nhưng những gì bạn nhận được là:

['A', 'and', 'B', 'and', 'C'] 

đó là bởi vì operatorPrecedence phân tích cú pháp lặp đi lặp lại hoạt động ở cùng độ ưu tiên mức sử dụng lại kiến nghị, không đệ quy.Xem this question rất giống với của bạn và câu trả lời của bạn bao gồm một hành động phân tích cú pháp để chuyển đổi cây phân tích cú pháp lặp lại thành cây phân tích cú pháp nhị phân truyền thống. Bạn cũng có thể tìm thấy a sample boolean expression parser implemented using operatorPrecedence trên trang wiki pyparsing.

EDIT: Để làm rõ, đây là những gì tôi khuyên bạn nên giảm bớt phân tích cú pháp của bạn để:

import pyparsing as pp 

operator = pp.Regex(">=|<=|!=|>|<|=").setName("operator") 
number = pp.Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?") 
identifier = pp.Word(pp.alphas, pp.alphanums + "_") 
comparison_term = identifier | number 
condition = pp.Group(comparison_term + operator + comparison_term) 

expr = pp.operatorPrecedence(condition,[ 
          ("AND", 2, pp.opAssoc.LEFT,), 
          ("OR", 2, pp.opAssoc.LEFT,), 
          ]) 

print expr.parseString("x > 7 AND x < 8 OR x = 4") 

Nếu hỗ trợ cho KHÔNG cũng có thể là một cái gì đó mà bạn muốn thêm, thì đây sẽ như thế nào:

expr = pp.operatorPrecedence(condition,[ 
          ("NOT", 1, pp.opAssoc.RIGHT,), 
          ("AND", 2, pp.opAssoc.LEFT,), 
          ("OR", 2, pp.opAssoc.LEFT,), 
          ]) 

Tại một thời điểm nào đó, bạn có thể muốn mở rộng định nghĩa comparison_term bằng biểu thức số học hoàn chỉnh hơn, được định nghĩa với định nghĩa operatorPrecedence của riêng nó. Tôi sẽ khuyên bạn nên làm theo cách này, thay vì tạo ra một định nghĩa quái vật opPrec, vì bạn đã ám chỉ một số nhược điểm về hiệu suất là opPrec. Nếu bạn vẫn gặp sự cố về hiệu suất, hãy xem ParserElement.enablePackrat.

Answer 2

Hãy để tôi đề xuất phương pháp phân tích cú pháp này, trực tiếp đến từ lớp của Peter Norvig trong thiết kế các chương trình máy tính tại udacity (và được điều chỉnh theo nhu cầu của bạn).

from functools import update_wrapper 
from string import split 
import re 

def grammar(description, whitespace=r'\s*'): 
    """Convert a description to a grammar. Each line is a rule for a 
    non-terminal symbol; it looks like this: 
     Symbol => A1 A2 ... | B1 B2 ... | C1 C2 ... 
    where the right-hand side is one or more alternatives, separated by 
    the '|' sign. Each alternative is a sequence of atoms, separated by 
    spaces. An atom is either a symbol on some left-hand side, or it is 
    a regular expression that will be passed to re.match to match a token. 

    Notation for *, +, or ? not allowed in a rule alternative (but ok 
    within a token). Use '\' to continue long lines. You must include spaces 
    or tabs around '=>' and '|'. That's within the grammar description itself. 
    The grammar that gets defined allows whitespace between tokens by default; 
    specify '' as the second argument to grammar() to disallow this (or supply 
    any regular expression to describe allowable whitespace between tokens).""" 
    G = {' ': whitespace} 
    description = description.replace('\t', ' ') # no tabs! 
    for line in split(description, '\n'): 
     lhs, rhs = split(line, ' => ', 1) 
     alternatives = split(rhs, ' | ') 
     G[lhs] = tuple(map(split, alternatives)) 
    return G 

def decorator(d): 
    def _d(fn): 
     return update_wrapper(d(fn), fn) 
    update_wrapper(_d, d) 
    return _d 

@decorator 
def memo(f): 
    cache = {} 
    def _f(*args): 
     try: 
      return cache[args] 
     except KeyError: 
      cache[args] = result = f(*args) 
      return result 
     except TypeError: 
      # some element of args can't be a dict key 
      return f(args) 
    return _f 

def parse(start_symbol, text, grammar): 
    """Example call: parse('Exp', '3*x + b', G). 
    Returns a (tree, remainder) pair. If remainder is '', it parsed the whole 
    string. Failure iff remainder is None. This is a deterministic PEG parser, 
    so rule order (left-to-right) matters. Do 'E => T op E | T', putting the 
    longest parse first; don't do 'E => T | T op E' 
    Also, no left recursion allowed: don't do 'E => E op T'""" 

    tokenizer = grammar[' '] + '(%s)' 

    def parse_sequence(sequence, text): 
     result = [] 
     for atom in sequence: 
      tree, text = parse_atom(atom, text) 
      if text is None: return Fail 
      result.append(tree) 
     return result, text 

    @memo 
    def parse_atom(atom, text): 
     if atom in grammar: # Non-Terminal: tuple of alternatives 
      for alternative in grammar[atom]: 
       tree, rem = parse_sequence(alternative, text) 
       if rem is not None: return [atom]+tree, rem 
      return Fail 
     else: # Terminal: match characters against start of text 
      m = re.match(tokenizer % atom, text) 
      return Fail if (not m) else (m.group(1), text[m.end():]) 

    # Body of parse: 
    return parse_atom(start_symbol, text) 

Fail = (None, None) 

MyLang = grammar("""expression => block logicalop expression | block 
block => variable operator number 
variable => [a-z]+ 
operator => <=|>=|>|<|= 
number => [-+]?[0-9]+ 
logicalop => AND|OR""", whitespace='\s*') 

def parse_it(text): 
    return parse('expression', text, MyLang) 

print parse_it("x > 7 AND x < 8 AND x = 4") 

Đầu ra:

(['expression', ['block', ['variable', 'x'], ['operator', '>'], ['number', '7']], ['logicalop', 'AND'], ['expression', ['block', ['variable', 'x'], ['operator', '<'], ['number', '8']], ['logicalop', 'AND'], ['expression', ['block', ['variable', 'x'], ['operator', '='], ['number', '4']]]]], '')