Разбор сложного логического выражения в pyparsing в двоичном древе

Ответ 1

Попробуйте изменить:

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

в

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

Первым аргументом для operatorPrecedence является примитивный операнд, который будет использоваться с операторами - нет необходимости включать ваш complexExpr в круглые скобки - operatorPrecedence сделает это для вас. Поскольку ваш операнд на самом деле является еще одним более глубоким сравнением, вы можете подумать об изменении:

condition = (expr + operator + expr)

в

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

так что выход operatorPrecedence легче обрабатывать. С этими изменениями синтаксический анализ x > 7 AND x < 8 OR x = 4 дает:

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

который распознает ИЛИ более высокий приоритет и сначала группирует его. (Вы уверены, что хотите этот порядок приоритетов AND и OR? Я думаю, что традиционное упорядочение является обратным, как показано в этой записи в википедии. )

Я думаю, вы также спрашиваете, почему pyparsing и operatorPrecedence не возвращают результаты в вложенных двоичных парах, то есть вы ожидаете, что разбор "A и B и C" вернется:

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

но вы получаете:

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

Это связано с тем, что operatorPrecedence анализирует повторяющиеся операции на одном уровне с использованием повторения, а не рекурсии. См. этот вопрос, который очень похож на ваш, и чей ответ включает в себя действие синтаксического анализа для преобразования вашего повторяющегося дерева разбора в более традиционное двоичное дерево синтаксического анализа. Вы также можете найти примерный логический синтаксический анализатор, реализованный с использованием operatorPrecedence на странице вики файла pyparsing.

ИЗМЕНИТЬ: Чтобы прояснить это, я рекомендую вам уменьшить ваш парсер до:

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")

Если поддержка NOT может также быть чем-то, что вы хотите добавить, это будет выглядеть так:

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

В какой-то момент вам может понадобиться расширить определение comparison_term с более полным арифметическим выражением, определенным его собственным определением operatorPrecedence. Я бы предложил сделать это таким образом, а не создать одно определение монстра opPrec, поскольку вы уже упоминали некоторые из недостатков производительности на opPrec. Если у вас все еще возникают проблемы с производительностью, просмотрите ParserElement.enablePackrat.

Ответ 2

Позвольте мне предложить этот подход синтаксического анализа, исходящий непосредственно из класса Питера Норвига в разработке компьютерных программ по udacity (и настраиваемый для ваших нужд).

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 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")

Выходы:

(['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']]]]], '')

Ответ 3

Вы использовали .setName("operator") для установки имени операторов. Как можно задать имя для логических операторов AND, OR, NOT в pyparsing? Спасибо