バイナリツリー形式でpyparsingで複雑な論理式を構文解析する

Question

以下のような複雑な論理式を解析しようとしています。

x > 7 AND x < 8 OR x = 4 

を取得し、解析された文字列をバイナリツリーとして取得します。上記の発現のために期待される解析された式は、論理演算子は「AND」演算子よりも優先順位が高い

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

のように見える「OR」すべきです。括弧はデフォルトの優先順位を上書きすることができます。より一般的には、解析された式は次のようになります。

<left_expr> <logical_operator> <right_expr> 

別の例は、

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

これまでのところ、私は悲しげに、バイナリツリー形式で解析された表現を生成することはできません。この簡単な解決策を考え出しただろう。 operatorPrecedenceは、前の例と同じ論理演算子が連続しているところで私を助けてくれているようではありません。

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

ご意見やご指摘はありがとうございます。 （括弧なし）を発現させるため

BNF

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

Answer 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を解析することは与える：第1のORの優先順位が高いとグループそれを認識し

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

。 （あなたは必ずANDとORの優先順位のこの注文をしたいされていますか？私はthis wikipedia entryに示すように、伝統的な順序は、逆だと思う。）

私はあなたにもpyparsingとoperatorPrecedenceは、ネストされた中で結果を返さない理由を求めていると思いますバイナリのペアは、つまり、あなたは、「AとBとCが」戻ってくるの解析を期待：

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

しかし、何を得ることです：

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

operatorPrecedenceが同じ優先順位で繰り返し動作を解析しているためであること再使用してレベル請願、再帰ではない。あなたと非常に似ており、繰り返し構文解析ツリーをより伝統的なバイナリ構文解析ツリーに変換する解析アクションが含まれています。this questionを参照してください。また、pyparsing wikiページでa sample boolean expression parser implemented using operatorPrecedenceを見つけることもできます。

EDIT： 明確にするために、これは私はあなたがあなたのパーサを減らすことをお勧めです：

：サポートも追加したい何かかもしれませ用の場合

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

、これは次のようになります。

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

は、ある時点で、あなたは、独自のoperatorPrecedence定義で定義された、より完全な算術式、とcomparison_termの定義を拡張することもできます。パフォーマンスの面では、opPrecの部分を暗示しているので、私はこの方法で、1つのモンスターopPrecの定義を作成するのではなく、そうすることをお勧めします。引き続きパフォーマンスの問題が発生した場合は、ParserElement.enablePackratをご覧ください。

Answer 2

Peter Norvigのコンピュータプログラムの設計では、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'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") 

出力：

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