12

これらのような論理式を解析するために pyparsing を使用しようとしています 

x
FALSE
NOT x
(x + y <= 5) AND (y >= 10) OR NOT (z < 100 OR w)

(A=True OR NOT (G < 8) => S = J) => ((P = A) AND not (P = 1) AND (B = O)) => (S = T)

((P = T) AND NOT (K =J) AND (B = F)) => (S = O) AND
 ((P = T) OR (k and b => (8 + z <= 10)) AND NOT (a + 9 <= F)) => (7 = a + z)

私が以下に書いたコードは問題なく動作するように見えますが、非常に遅いです (例えば、上記の最後の例では数秒かかります)。効率の悪い方法で文法を構成しましたか? operatorPrecedence の代わりに再帰を使用する必要がありますか? それをスピードアップする方法はありますか？ 

identifier = Group(Word(alphas, alphanums + "_")  +  Optional("'"))
num = Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?")
operator = Regex(">=|<=|!=|>|<|=")
operand = identifier |  num  
aexpr = operatorPrecedence(operand,
                           [('*',2,opAssoc.LEFT,),
                            ('+',2,opAssoc.LEFT,),
                            (operator,2,opAssoc.LEFT,)
                            ])

op_prec = [(CaselessLiteral('not'),1,opAssoc.RIGHT,),
           (CaselessLiteral('and'),2,opAssoc.LEFT ,),
           (CaselessLiteral('or'), 2,opAssoc.LEFT ,),
           ('=>', 2,opAssoc.LEFT ,),
           ]
sentence = operatorPrecedence(aexpr,op_prec)
return sentence
4

2 に答える 2

8

私も同じ問題を抱えていました。ここで解決策を見つけました ( parserElement.enablePackrat()): https://github.com/pyparsing/pyparsing

次のコードが即座に解析されるようになりました (対 60 秒前)

ParserElement.enablePackrat()

integer  = Word(nums).setParseAction(lambda t:int(t[0]))('int')
operand  = integer | variable('var')

# Left precedence
eq    = Literal("==")('eq')
gt    = Literal(">")('gt')
gtEq  = Literal(">=")('gtEq')
lt    = Literal("<")('lt')
ltEq  = Literal("<=")('ltEq')
notEq = Literal("!=")('notEq')
mult  = oneOf('* /')('mult')
plus  = oneOf('+ -')('plus')

_and  = oneOf('&& and')('and')
_or   = oneOf('|| or')('or')

# Right precedence
sign     = oneOf('+ -')('sign')
negation = Literal('!')('negation')

# Operator groups per presedence
right_op = negation | sign 

# Highest precedence
left_op_1 = mult 
left_op_2 = plus 
left_op_3 = gtEq | ltEq | lt | gt
left_op_4 = eq   | notEq
left_op_5 = _and
left_op_6 = _or
# Lowest precedence

condition = operatorPrecedence( operand, [
     (right_op,   1, opAssoc.RIGHT),
     (left_op_1,  2, opAssoc.LEFT),
     (left_op_2,  2, opAssoc.LEFT),
     (left_op_3,  2, opAssoc.LEFT),
     (left_op_4,  2, opAssoc.LEFT),
     (left_op_5,  2, opAssoc.LEFT),
     (left_op_6,  2, opAssoc.LEFT)
    ]
)('computation')
于 2014-03-04T18:27:49.283 に答える
4

私はあなたのコードを小さなプログラムに入れました

from sys import argv
from pyparsing import *

def parsit(aexpr):
    identifier = Group(Word(alphas, alphanums + "_")  +  Optional("'"))
    num = Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?")
    operator = Regex(">=|<=|!=|>|<|=")
    operand = identifier |  num
    aexpr = operatorPrecedence(operand,
                               [('*',2,opAssoc.LEFT,),
                                ('+',2,opAssoc.LEFT,),
                                (operator,2,opAssoc.LEFT,)
                                ])

    op_prec = [(CaselessLiteral('not'),1,opAssoc.RIGHT,),
               (CaselessLiteral('and'),2,opAssoc.LEFT ,),
               (CaselessLiteral('or'), 2,opAssoc.LEFT ,),
               ('=>', 2,opAssoc.LEFT ,),
               ]
    sentence = operatorPrecedence(aexpr,op_prec)
    return sentence

def demo02(arg):
    sent = parsit(arg)
    print arg, ":", sent.parseString(arg)

def demo01():
    for arg in ["x", "FALSE", "NOT x",
                  "(x + y <= 5) AND (y >= 10) OR NOT (z < 100 OR w)",
                  "(A=True OR NOT (G < 8) => S = J) => ((P = A) AND not (P = 1) AND (B = O)) => (S = T)",
                  "((P = T) AND NOT (K =J) AND (B = F)) => (S = O) AND ((P = T) OR (k and b => (8 + z <= 10)) AND NOT (a + 9 <= F)) => (7 = a + z)"
                  ]:
        demo02(arg)


if len(argv) <= 1:
    demo01()
else:
    for arg in argv[1:]:
        demo02(arg)

そして駆け抜けたcProfile

$ python -m cProfile pyparsetest.py

多くの 呼び出しが見つかりますparseImplが、出力の途中にあります

2906500/8   26.374    0.000   72.667    9.083 pyparsing.py:913(_parseNoCache)
212752/300    1.045    0.000   72.608    0.242 pyparsing.py:985(tryParse)

合計から計算された72.667時間72です。

したがって、私は、「キャッシング」が良い手段を提供すると推測します。

http://pyparsing-public.wikispaces.com/FAQs を有効にするだけでは役に立ちませんでした。行を追加しました

import pyparsing
pyparsing.usePackrat = True

ランタイムは同じでした。

Number-Regex も私には問題ないように見えます。かなり標準的だと思います。たとえば、次のように置き換えます

#num = Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?")
num = Regex(r"8|1|10|100|5")

も助けにはなりませんでした。私の単純なバリアントには「空の一致」はありません。これは問題になる可能性があると推測しましたが、そうではないようです。

最後に、結果パーサーを次のように見てみましょう。

....
sentence = operatorPrecedence(aexpr,op_prec)
print sentence 
return sentence
....

そして… なんと… 長い！

まあ、あなたの最初のものを使わないoperatorPrecedence方がはるかに高速ですが、算術演算ではもう機能しません.

したがって、2 種類の式 (ブール式と算術式) をさらに分離しようとしていると思います。多分それはそれを改善します。私も調べてみます、興味があります。

于 2012-11-28T11:12:53.013 に答える