論理式を解析して構文解析する

Question

これは宿題ではありません。私は構文解析を学びたいと思っています。

次のように私の質問は、私は、(abc or def) or def)

両側が再び中置表現することができ、式そのものであることができるので、私のプログラムは、中置式a or bにたわごとに行くような文を解析しようとしている、ありますパーサーは、再帰の深さに達するまで繰り返され、処理は行われません。以下

コード：

# infix operators are automatically created and dealt with 
infix_operators = ['and', '&', 'or', '|', 'implies', '->'] 

variable = Word(alphas) 
infix_op = oneOf(infix_operators, caseless=True) 

expr   = Forward() 
infix_expr = (expr + infix_op + expr) 
complex_expr = nestedExpr('(', ')', content=expr) 
expr  << (infix_expr | complex_expr | variable) 

print str(expr.parseString("(abc or def) or def)")[0]) 

私の質問は非常に単純です。このような状況で無限ループを回避するにはどうすればいいでしょうか？ 、それはexprになったとき、>​​- >factorからexprは、最終的にtermを通じて再帰的にもかかわらず、左再帰の問題があるため対処される

atom := variable | 'True' | 'False' | '(' expr ')' 
factor := [ 'not' ]... atom 
term := factor [ '&' factor ]... 
expr := term [ '|' term ]... 

：

Answer 1

標準的なソリューションは、このBNFを実装して何かであります。それは最初のでexprは最初の最初のいくつかの他の要素を解析する前にexpr深いを解析する必要がありません「（」リードを解析する必要があります

このBNFのようにpyparsingにほとんど直接変換します。

and_ = Keyword('and') 
or_ = Keyword('or') 
not_ = Keyword('not') 
true_ = Keyword('true') 
false_ = Keyword('false') 

not_op = not_ | '~' 
and_op = and_ | '&' 
or_op = or_ | '|' 

expr = Forward() 

identifier = ~(and_ | or_ | not_ | true_ | false_) + Word(alphas) 
atom = identifier | Group('(' + expr + ')') 
factor = Group(ZeroOrMore(not_op) + atom) 
term = Group(factor + ZeroOrMore(and_op + factor)) 
expr <<= Group(term + ZeroOrMore(or_op + term)) 

それとも、pyparsingのinfixNotationヘルパー使用することができます。

expr = infixNotation(true_ | false_ | identifier, 
    [ 
    (not_op, 1, opAssoc.RIGHT), 
    (and_op, 2, opAssoc.LEFT), 
    (or_op, 2, opAssoc.LEFT), 
    ]) 

infixNotationは（この場合は、どちらかのアルファ変数名またはブールリテラルtrueまたはfalseの1）のベースオペランドで構成されており、オペレータの優先順位の順に与えられた(operator, arity, associativity)タプルのリストが続きます。 infixNotationは、すべての再帰定義、右結合演算子と左結合演算子の解析を行い、演算子がない場合は、指定された優先レベルの演算を余分に入れないようにします。

あなたがpyparsingのrunTestsメソッドを使用して、この式をテストすることができます。

与える

expr.runTests(""" 
    p and not q 
    not p or p 
    r and (p or q) 
    r and p or q 
    not q 
    q 
    """, fullDump=False) 

：D：詳細な回答のため

p and not q 
[['p', 'and', ['not', 'q']]] 

not p or p 
[[['not', 'p'], 'or', 'p']] 

r and (p or q) 
[['r', 'and', ['p', 'or', 'q']]] 

r and p or q 
[[['r', 'and', 'p'], 'or', 'q']] 

not q 
[['not', 'q']] 

q 
['q']